The monadic second-order logic of graphs. IV: Definability properties of equational graphs

DOI10.1016/0168-0072(90)90027-YMaRDI QIDQ807611zbMATH OpenOpenAlexFDO

Authors Bruno Courcelle

Publication date 1990

Published in Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0168-0072(90)90027-y

zbMATH Keywords

equational graphmonadic second-order logic of countable graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Decidability of theories and sets of sentences (03B25) Second- and higher-order model theory (03C85)

Recommendations

• scientific article; zbMATH DE number 4124985
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• The monadic second-order logic of graphs, II: Infinite graphs of bounded width
• A regular characterization of graph languages definable in monadic second-order logic
• The monadic second-order logic of graphs. V: On closing the gap between definability and recognizability

Cites work

• scientific article; zbMATH DE number 3885965 (Why is no real title available?)
• scientific article; zbMATH DE number 3492660 (Why is no real title available?)
• scientific article; zbMATH DE number 1142315 (Why is no real title available?)
• scientific article; zbMATH DE number 3339435 (Why is no real title available?)
• An axiomatic approach to the Korenjak-Hopcroft algorithms
• An axiomatic definition of context-free rewriting and its application to NLC graph grammars
• Decidability of Second-Order Theories and Automata on Infinite Trees
• Equivalences and transformations of regular systems - applications to recursive program schemes and grammars
• Fundamental properties of infinite trees
• Graph expressions and graph rewritings
• Infinite hypergraphs. I: Basic properties
• Least fixed point of a functor
• The monadic second-order logic of graphs, II: Infinite graphs of bounded width
• 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 theory of order
• Weak Second‐Order Arithmetic and Finite Automata

Cited in

(23)

• A regular characterization of graph languages definable in monadic second-order logic
• The monadic second-order logic of graphs. VII: Graphs as relational structures
• Infinite hypergraphs. II: Systems of recursive equations
• The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
• scientific article; zbMATH DE number 2080202 (Why is no real title available?)
• scientific article; zbMATH DE number 4124985 (Why is no real title available?)
• Infinite hypergraphs. I: Basic properties
• Automatic graphs and D0L-sequences of finite graphs
• The monadic second-order logic of graphs. XII: Planar graphs and planar maps
• The monadic second-order logic of graphs, II: Infinite graphs of bounded width
• \(L(A)=L(B)\)? decidability results from complete formal systems
• Automorphism groups of context-free graphs
• Deciding the isomorphism problem in classes of unary automatic structures
• Isomorphisms and algorithmic properties of structures with two equivalences
• Regular Subgraphs in Graphs and Rooted Graphs and Definability in Monadic Second - Order Logic
• The modular decomposition of countable graphs. Definition and construction in monadic second-order logic
• On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
• scientific article; zbMATH DE number 4049098 (Why is no real title available?)
• Simple monadic theories and partition width
• The monadic second-order logic of graphs. V: On closing the gap between definability and recognizability
• Querying probabilistic business processes for sub-flows
• The monadic second-order logic of graphs. VIII: Orientations
• The monadic second-order logic of graphs. IX: Machines and their behaviours

This page was built for publication: The monadic second-order logic of graphs. IV: Definability properties of equational graphs

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