A regular characterization of graph languages definable in monadic second-order logic

DOI10.1016/0304-3975(91)90078-GzbMath0739.68052OpenAlexW1970456124MaRDI QIDQ1177179

Joost Engelfriet

Publication date: 26 June 1992

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(91)90078-g

zbMATH Keywords

monadic second-order logicgraph languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

Monadic second-order definable text languages ⋮ Computability by monadic second-order logic ⋮ Arity and alternation in second-order logic ⋮ Logical description of context-free graph languages ⋮ MSO definable text languages ⋮ Tree-Based Generation of Restricted Graph Languages ⋮ A comparison of tree transductions defined by monadic second order logic and by attribute grammars

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Characterization of \(\omega\)-regular languages by first-order formulas
• Tree acceptors and some of their applications
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Weak Second‐Order Arithmetic and Finite Automata
• Decision Problems of Finite Automata Design and Related Arithmetics
• Generalized finite automata theory with an application to a decision problem of second-order logic
• Decidability of Second-Order Theories and Automata on Infinite Trees