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

DOI10.1016/0168-0072(90)90027-YzbMATH Open0731.03006OpenAlexW1480506611MaRDI QIDQ807611FDOQ807611

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

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

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)

Cites Work

• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Decidability of Second-Order Theories and Automata on Infinite Trees
• Title not available (Why is that?)
• Fundamental properties of infinite trees
• Weak Second‐Order Arithmetic and Finite Automata
• 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
• Title not available (Why is that?)
• The monadic theory of order
• Title not available (Why is that?)
• An axiomatic definition of context-free rewriting and its application to NLC graph grammars
• Equivalences and transformations of regular systems - applications to recursive program schemes and grammars
• Least fixed point of a functor
• Infinite hypergraphs. I: Basic properties
• Graph expressions and graph rewritings
• Title not available (Why is that?)
• An axiomatic approach to the Korenjak-Hopcroft algorithms

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
• Title not available (Why is that?)
• Title not available (Why is that?)
• Automatic graphs and D0L-sequences of finite graphs
• The monadic second-order logic of graphs. XII: Planar graphs and planar maps
• Infinite hypergraphs. I: Basic properties
• 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
• Title not available (Why is that?)
• 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)