Recognizable sets of graphs: equivalent definitions and closure properties

DOI10.1017/S0960129500000359zbMATH Open0798.68090OpenAlexW2027893394MaRDI QIDQ4286529FDOQ4286529

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

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

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)

Cites Work

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

Cited In (11)

• Recognizability, hypergraph operations, and logical types
• On the Recognizability of Arrow and Graph Languages
• The monadic second-order logic of graphs. X: Linear orderings
• Title not available (Why is that?)
• Basic notions of universal algebra for language theory and graph grammars
• A confluent reduction for the λ-calculus with surjective pairing and terminal object
• Title not available (Why is that?)
• Recognizable sets of graphs of bounded tree-width
• Title not available (Why is that?)
• 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)