The monadic second-order logic of graphs : Definable sets of finite graphs

DOI10.1007/3-540-50728-0_34OpenAlexW1506761696MaRDI QIDQ6203539FDOQ6203539

Authors Bruno Courcelle 

Publication date 28 February 2024

Published in Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-50728-0_34

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Grammars and rewriting systems (68Q42) Higher-order logic (03B16) Decidability of theories and sets of sentences (03B25)

Recommendations

• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• The monadic second-order logic of graphs. V: On closing the gap between definability and recognizability
• The monadic second-order logic of graphs, II: Infinite graphs of bounded width
• scientific article; zbMATH DE number 4049098
• scientific article; zbMATH DE number 17791

Cites work

• scientific article; zbMATH DE number 3885965 (Why is no real title available?)
• scientific article; zbMATH DE number 3974289 (Why is no real title available?)
• scientific article; zbMATH DE number 4035178 (Why is no real title available?)
• scientific article; zbMATH DE number 4049097 (Why is no real title available?)
• scientific article; zbMATH DE number 4053039 (Why is no real title available?)
• scientific article; zbMATH DE number 4060712 (Why is no real title available?)
• scientific article; zbMATH DE number 4060748 (Why is no real title available?)
• scientific article; zbMATH DE number 4060749 (Why is no real title available?)
• Algebraic automata and context-free sets
• An axiomatic definition of context-free rewriting and its application to NLC graph grammars
• Complexity of Finding Embeddings in a k-Tree
• Equivalences and transformations of regular systems - applications to recursive program schemes and grammars
• Graph expressions and graph rewritings
• Graph minors. V. Excluding a planar graph
• The NP-completeness column: An ongoing guide
• The NP-completeness column: an ongoing guide
• Tree acceptors and some of their applications
• Über eine Eigenschaft der ebenen Komplexe

Cited in

(2)

• Parameterized domination in circle graphs
• Confluence up to garbage

This page was built for publication: The monadic second-order logic of graphs : Definable sets of finite graphs

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