Graph Structure and Monadic Second-Order Logic: Language Theoretical Aspects

DOI10.1007/978-3-540-70575-8_1MaRDI QIDQ3521904zbMATH OpenOpenAlexFDO

Authors Bruno Courcelle

Publication date 28 August 2008

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-70575-8_1

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• 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. X: Linear orderings
• The monadic second-order logic of graphs. VII: Graphs as relational structures
• The monadic second-order logic of graphs, II: Infinite graphs of bounded width

Cited in

(25)

• Treewidth and logical definability of graph products
• A regular characterization of graph languages definable in monadic second-order logic
• The monadic second-order logic of graphs. VII: Graphs as relational structures
• Monadic second-order logic, graph coverings and unfoldings of transition systems
• The Stackelberg minimum spanning tree game on planar and bounded-treewidth graphs
• scientific article; zbMATH DE number 1696755 (Why is no real title available?)
• F-rank-width of (edge-colored) graphs
• Graph structure and monadic second-order logic. A language-theoretic approach
• Logics and Automata for Totally Ordered Trees
• Easy Problems for Grid-Structured Graphs
• Monadic Second-Order Logic for Graphs: Algorithmic and Language Theoretical Applications
• scientific article; zbMATH DE number 4062635 (Why is no real title available?)
• The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
• Courcelle's theorem -- a game-theoretic approach
• scientific article; zbMATH DE number 1223635 (Why is no real title available?)
• scientific article; zbMATH DE number 1290983 (Why is no real title available?)
• scientific article; zbMATH DE number 475615 (Why is no real title available?)
• Prefix-Recognizable Graphs and Monadic Logic
• Descriptive Complexity, Canonisation, and Definable Graph Structure Theory
• An auxiliary logic on trees: on the tower-hardness of logics featuring reachability and submodel reasoning
• An auxiliary logic on trees: on the tower-hardness of logics featuring reachability and submodel reasoning
• Counting on rainbow k-connections
• The monadic second-order logic of graphs. IX: Machines and their behaviours
• T-structures, T-functions, and texts
• Affine optimal k-proper connected edge colorings

This page was built for publication: Graph Structure and Monadic Second-Order Logic: Language Theoretical Aspects

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