Recognizable sets of graphs: equivalent definitions and closure properties

DOI10.1017/S0960129500000359MaRDI QIDQ4286529zbMATH OpenOpenAlexFDO

Authors Bruno Courcelle

Publication date 26 April 1994

Published in Mathematical Structures in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1017/s0960129500000359

zbMATH Keywords

recognizability

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Automata and formal grammars in connection with logical questions (03D05) Grammars and rewriting systems (68Q42)

Recommendations

• The recognizability of sets of graphs is a robust property
• Equivalent definitions of recognizability for sets of graphs of bounded tree-width
• Recognizable sets of graphs of bounded tree-width
• Recognizability, hypergraph operations, and logical types
• Developments in Language Theory

Cites work

• scientific article; zbMATH DE number 51770 (Why is no real title available?)
• scientific article; zbMATH DE number 3497806 (Why is no real title available?)
• scientific article; zbMATH DE number 1142315 (Why is no real title available?)
• A comparison of compatible, finite, and inductive graph properties
• Algebraic automata and context-free sets
• An axiomatic definition of context-free rewriting and its application to NLC graph grammars
• Easy problems for tree-decomposable graphs
• Equivalences and transformations of regular systems - applications to recursive program schemes and grammars
• Graph expressions and graph rewritings
• Handle-rewriting hypergraph grammars
• The monadic second-order logic of graphs. V: On closing the gap between definability and recognizability
• The monadic second-order logic of graphs. VII: Graphs as relational structures

Cited in

(11)

• Recognizability, hypergraph operations, and logical types
• The monadic second-order logic of graphs. X: Linear orderings
• On the Recognizability of Arrow and Graph Languages
• Basic notions of universal algebra for language theory and graph grammars
• scientific article; zbMATH DE number 4121455 (Why is no real title available?)
• A confluent reduction for the λ-calculus with surjective pairing and terminal object
• scientific article; zbMATH DE number 475419 (Why is no real title available?)
• Recognizable sets of graphs of bounded tree-width
• scientific article; zbMATH DE number 7204410 (Why is no real title available?)
• The definition in monadic second-order logic of modular decompositions of ordered graphs
• The recognizability of sets of graphs is a robust property

This page was built for publication: Recognizable sets of graphs: equivalent definitions and closure properties

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