Wed 18 Jan 2023 14:20 - 14:45 at Grand Ballroom A - Logic & Decidability I Chair(s): Zachary Kincaid

Motivated by distributed data processing applications, we introduce a class of labeled directed acyclic graphs constructed using sequential and parallel composition operations, and study automata and logics over them. We show that deterministic and non-deterministic acceptors over such graphs have the same expressive power, which can be equivalently characterized by Monadic Second-Order logic and the graded $\mu$-calculus. We establish closure under composition operations and decision procedures for membership, emptiness, and inclusion. A key feature of our graphs, called \emph{synchronized series-parallel graphs} (SSPG), is that parallel composition introduces a synchronization edge from the newly introduced source vertex to the sink. The transfer of information enabled by such edges is crucial to the determinization construction, which would not be possible for the traditional definition of series-parallel graphs.

SSPGs allow both ordered ranked parallelism and unordered unranked parallelism. The latter feature means that in the corresponding automata, the transition function needs to account for an arbitrary number of predecessors by counting each type of state only up to a specified constant, thus leading to a notion of \emph{counting complexity} that is distinct from the classical notion of state complexity. The determinization construction translates a nondeterministic automaton with $n$ states and $k$ counting complexity to a deterministic automaton with $2^{n^2}$ states and $kn$ counting complexity, and both these bounds are shown to be tight. Furthermore, for nondeterministic automata a bound of 2 on counting complexity suffices without loss of expressiveness.

#### Wed 18 JanDisplayed time zone: Eastern Time (US & Canada) change

 13:30 - 14:45 Logic & Decidability IPOPL at Grand Ballroom A Chair(s): Zachary Kincaid Princeton University 13:3025mTalk Witnessability of Undecidable ProblemsPOPLShuo Ding Georgia Institute of Technology, Qirun Zhang Georgia Institute of Technology DOI 13:5525mTalk On the Expressive Power of String ConstraintsPOPLJoel D. Day Loughborough University, Vijay Ganesh University of Waterloo, Nathan Grewal University of Waterloo, Florin Manea University of Göttingen DOI 14:2025mTalk A Robust Theory of Series Parallel GraphsPOPLRajeev Alur University of Pennsylvania, Caleb Stanford University of California, San Diego; University of California, Davis, Chris Watson University of Pennsylvania DOI