The monadic quantifier alternation hierarchy over grids and graphs

DOI10.1006/inco.2002.2955zbMath1096.03007OpenAlexW2054860648MaRDI QIDQ2506497

Nicole Schweikardt, Oliver Matz, Wolfgang Thomas

Publication date: 10 October 2006

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/f283078df3653e1e5d487234bcd127226f54c0e1

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Automata and formal grammars in connection with logical questions (03D05) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

A logical approach to locality in pictures languages, Existential MSO over two successors is strictly weaker than over linear orders, Arity and alternation: a proper hierarchy in higher order logics, Relating Paths in Transition Systems: The Fall of the Modal Mu-Calculus, Extensions of MSO and the monadic counting hierarchy, Second-order propositional modal logic and monadic alternation hierarchies, Comparing Necessary Conditions for Recognizability of Two-Dimensional Languages, Uniform satisfiability problem for local temporal logics over Mazurkiewicz traces, Message-passing automata are expressively equivalent to EMSO logic, Dot-depth, monadic quantifier alternation, and first-order closure over grids and pictures, On the expressive power of monadic least fixed point logic

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on the number of monadic quantifiers in monadic \(\Sigma ^{1}_{1}\)
• Finite automata and unary languages
• Classifying regular events in symbolic logic
• On monadic NP vs monadic co-NP
• Monadic second-order logic over rectangular pictures and recognizability by tiling systems
• On winning Ehrenfeucht games and monadic NP
• Arity and alternation in second-order logic
• Weak Second‐Order Arithmetic and Finite Automata
• Decision Problems of Finite Automata Design and Related Arithmetics
• Monadic generalized spectra
• Dot-depth, monadic quantifier alternation, and first-order closure over grids and pictures