scientific article; zbMATH DE number 4049098

MaRDI QIDQ3785987zbMATH OpenFDO

Authors Bruno Courcelle

Publication date 1987

zbMATH Keywords

Context-free graph grammarsdecision problemmonadic second-order logic

Mathematics Subject Classification ID

Equational logic, Mal'tsev conditions (08B05) Formal languages and automata (68Q45) Abstract data types; algebraic specification (68Q65) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• scientific article; zbMATH DE number 17791
• The monadic second-order logic of graphs. IV: Definability properties of equational graphs
• The monadic second-order logic of graphs. VII: Graphs as relational structures
• The monadic second-order logic of graphs. V: On closing the gap between definability and recognizability

Cited in

(29)

• The theory of ends, pushdown automata, and second-order logic
• An axiomatic definition of context-free rewriting and its application to NLC graph grammars
• Metatheorems for decision problems on hyperedge replacement graph languages
• Algorithms for graph problems on BNLC structured garphs
• Algorithms for recognition of regular properties and decomposition of recursive graph families
• Infinite hypergraphs. II: Systems of recursive equations
• Correctness of fixpoint transformations
• On the decidability of certain integer subgraph problems on context-free graph languages
• The translation power of top-down tree-to-graph transducers
• A monadic second-order definition of the structure of convex hypergraphs.
• A comparison of compatible, finite, and inductive graph properties
• Branch-width, parse trees, and monadic second-order logic for matroids.
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Courcelle's theorem for triangulations
• The monadic second-order logic of graphs, II: Infinite graphs of bounded width
• Graphes canoniques de graphes algébriques
• Graph expressions and graph rewritings
• scientific article; zbMATH DE number 4106286 (Why is no real title available?)
• scientific article; zbMATH DE number 17791 (Why is no real title available?)
• scientific article; zbMATH DE number 1507241 (Why is no real title available?)
• scientific article; zbMATH DE number 2086614 (Why is no real title available?)
• scientific article; zbMATH DE number 2102748 (Why is no real title available?)
• scientific article; zbMATH DE number 1418335 (Why is no real title available?)
• The HOMFLY-PT polynomial is fixed-parameter tractable
• Context-Free Graph Properties via Definable Decompositions
• The monadic second-order logic of graphs : Definable sets of finite graphs
• Recursive queries and context-free graph grammars
• Complexity of abstract argumentation under a claim-centric view
• Undecidability of the bandwidth problem on linear graph languages

This page was built for publication:

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