Prefix-recognizable graphs and monadic logic

DOI10.1007/3-540-36387-4_15MaRDI QIDQ4412838zbMATH OpenOpenAlexFDO

Authors Martin Leucker

Publication date 16 July 2003

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-36387-4_15

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Automata and formal grammars in connection with logical questions (03D05) Formal languages and automata (68Q45)

Recommendations

• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Graph decompositions definable in monadic second-order logic
• Monadic Second-Order Logic for Graphs: Algorithmic and Language Theoretical Applications
• Graph structure and monadic second-order logic. A language-theoretic approach
• The monadic second-order logic of graphs. V: On closing the gap between definability and recognizability
• scientific article; zbMATH DE number 17791
• Expressive power of monadic logics on words, trees, pictures, and graphs
• Recognizability, hypergraph operations, and logical types
• The structure of the models of decidable monadic theories of graphs
• Graph Structure and Monadic Second-Order Logic: Language Theoretical Aspects

Cited in

(8)

• Recognizability, hypergraph operations, and logical types
• The monadic quantifier alternation hierarchy over grids and graphs
• The monadic quantifier alternation hierarchy over grids and pictures
• The monadic theory of tree-like structures
• A Combinatorial Theorem for Trees
• Mathematical Foundations of Computer Science 2003
• An internal presentation of regular graphs by prefix-recognizable graphs
• Reachability on prefix-recognizable graphs

This page was built for publication: Prefix-recognizable graphs and monadic logic

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