The monadic quantifier alternation hierarchy over grids and graphs

DOI10.1006/INCO.2002.2955MaRDI QIDQ2506497zbMATH OpenOpenAlexFDO

Authors Oliver Matz, Nicole Schweikardt, 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

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

Recommendations

• scientific article; zbMATH DE number 1223636
• Dot-depth, monadic quantifier alternation, and first-order closure over grids and pictures
• Hierarchies of monadic generalized quantifiers
• scientific article; zbMATH DE number 1223635
• scientific article; zbMATH DE number 2080202
• Monadic Second-Order Logic for Graphs: Algorithmic and Language Theoretical Applications
• The structure of the models of decidable monadic theories of graphs
• Prefix-Recognizable Graphs and Monadic Logic
• Graph structure and monadic second-order logic. A language-theoretic approach
• Monadic second-order logic, graph coverings and unfoldings of transition systems

Cites work

• A note on the number of monadic quantifiers in monadic \(\Sigma ^{1}_{1}\)
• Arity and alternation in second-order logic
• Classifying regular events in symbolic logic
• Decision Problems of Finite Automata Design and Related Arithmetics
• Dot-depth, monadic quantifier alternation, and first-order closure over grids and pictures
• Finite automata and unary languages
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 53151 (Why is no real title available?)
• scientific article; zbMATH DE number 3497806 (Why is no real title available?)
• scientific article; zbMATH DE number 1222610 (Why is no real title available?)
• scientific article; zbMATH DE number 1223636 (Why is no real title available?)
• scientific article; zbMATH DE number 1775416 (Why is no real title available?)
• scientific article; zbMATH DE number 803291 (Why is no real title available?)
• scientific article; zbMATH DE number 848148 (Why is no real title available?)
• Monadic generalized spectra
• Monadic second-order logic over rectangular pictures and recognizability by tiling systems
• On monadic NP vs monadic co-NP
• On winning Ehrenfeucht games and monadic NP
• Weak Second‐Order Arithmetic and Finite Automata

Cited in

(17)

• Vectorization hierarchies of some graph quantifiers
• Arity and alternation: a proper hierarchy in higher order logics
• Message-passing automata are expressively equivalent to EMSO logic
• Relating paths in transition systems: the fall of the modal mu-calculus
• A logical approach to locality in pictures languages
• Comparing necessary conditions for recognizability of two-dimensional languages
• A modal perspective on monadic second-order alternation hierarchies
• scientific article; zbMATH DE number 1223636 (Why is no real title available?)
• scientific article; zbMATH DE number 2080202 (Why is no real title available?)
• Second-order propositional modal logic and monadic alternation hierarchies
• Grid structures and undecidable constraint theories
• Dot-depth, monadic quantifier alternation, and first-order closure over grids and pictures
• Extensions of MSO and the monadic counting hierarchy
• A LOCAL view of the polynomial hierarchy
• On the expressive power of monadic least fixed point logic
• Existential MSO over two successors is strictly weaker than over linear orders
• Uniform satisfiability problem for local temporal logics over Mazurkiewicz traces

This page was built for publication: The monadic quantifier alternation hierarchy over grids and graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2506497)