Monadic Second-Order Logic for Graphs: Algorithmic and Language Theoretical Applications

DOI10.1007/978-3-642-00982-2_2MaRDI QIDQ3618564zbMATH OpenOpenAlexFDO

Authors Bruno Courcelle

Publication date 2 April 2009

Published in Language and Automata Theory and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-00982-2_2

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10) Automata and formal grammars in connection with logical questions (03D05)

Recommendations

• Graph Structure and Monadic Second-Order Logic: Language Theoretical Aspects
• Graph structure and monadic second-order logic. A language-theoretic approach
• The monadic second-order logic of graphs. VII: Graphs as relational structures
• scientific article; zbMATH DE number 1231484
• Graph operations, graph transformations and monadic second-order logic: a survey

Cites work

• Algorithmic uses of the Feferman-Vaught theorem
• Linear time solvable optimization problems on graphs of bounded clique-width
• Monadic second-order evaluations on tree-decomposable graphs

Cited in

(14)

• Branch-width, parse trees, and monadic second-order logic for matroids.
• A regular characterization of graph languages definable in monadic second-order logic
• The monadic second-order logic of graphs. VII: Graphs as relational structures
• scientific article; zbMATH DE number 4124985 (Why is no real title available?)
• The monadic second-order logic of graphs XVI : Canonical graph decompositions
• Graph structure and monadic second-order logic. A language-theoretic approach
• scientific article; zbMATH DE number 1290983 (Why is no real title available?)
• scientific article; zbMATH DE number 475615 (Why is no real title available?)
• On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
• Graph Structure and Monadic Second-Order Logic: Language Theoretical Aspects
• The monadic quantifier alternation hierarchy over grids and graphs
• Prefix-Recognizable Graphs and Monadic Logic
• scientific article; zbMATH DE number 1696755 (Why is no real title available?)
• The monadic second-order logic of graphs. IX: Machines and their behaviours

This page was built for publication: Monadic Second-Order Logic for Graphs: Algorithmic and Language Theoretical Applications

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