Recognizability, hypergraph operations, and logical types

DOI10.1016/j.ic.2005.11.006zbMath1110.03021OpenAlexW2001654442MaRDI QIDQ2496296

Bruno Courcelle, Achim Blumensath

Publication date: 12 July 2006

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2005.11.006

zbMATH Keywords

monadic second-order logicgraph operationrecognizable setlogical typemonadic second-order transductionequational set

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Second- and higher-order model theory (03C85)

Related Items (11)

Simple monadic theories and partition width ⋮ The rank-width of edge-coloured graphs ⋮ Compact labelings for efficient first-order model-checking ⋮ Graph Operations Characterizing Rank-Width and Balanced Graph Expressions ⋮ $\mathbb F$ -Rank-Width of (Edge-Colored) Graphs ⋮ Counting truth assignments of formulas of bounded tree-width or clique-width ⋮ A model-theoretic characterisation of clique width ⋮ Relational structures constructible by quantifier free definable operations ⋮ Clique-width of point configurations ⋮ Graph operations characterizing rank-width ⋮ The recognizability of sets of graphs is a robust property

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Algorithmic uses of the Feferman-Vaught theorem
• Basic notions of universal algebra for language theory and graph grammars
• Elements of finite model theory.
• 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
• The monadic theory of order
• Monadic second-order definable graph transductions: a survey
• The monadic second order logic of graphs. VI: On several representations of graphs by relational structures
• Logical description of context-free graph languages
• A comparison of tree transductions defined by monadic second order logic and by attribute grammars
• Linear time solvable optimization problems on graphs of bounded clique-width
• Upper bounds to the clique width of graphs
• Handle-rewriting hypergraph grammars
• The recognizability of sets of graphs is a robust property
• Fusion in relational structures and the verification of monadic second-order properties
• Decomposition of Directed Graphs
• Recognizable sets of graphs: equivalent definitions and closure properties
• Handbook of Graph Grammars and Computing by Graph Transformation
• Macro Tree Translations of Linear Size Increase are MSO Definable
• Equivalent definitions of recognizability for sets of graphs of bounded tree-width
• The monadic second-order logic of graphs XVI : Canonical graph decompositions
• Algebraic automata and context-free sets

This page was built for publication: Recognizability, hypergraph operations, and logical types