Recognizability, hypergraph operations, and logical types

DOI10.1016/J.IC.2005.11.006MaRDI QIDQ2496296zbMATH OpenOpenAlexFDO

Authors Achim Blumensath, Bruno Courcelle

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

equational setgraph operationlogical typemonadic second-order logicmonadic second-order transductionrecognizable set

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 638367
• Prefix-Recognizable Graphs and Monadic Logic
• Hyperformulae, parallel deductions and intersection types
• scientific article; zbMATH DE number 5872389
• Types as graphs: Continuations in type logical grammar
• Types, Maps and Separation Logic
• scientific article; zbMATH DE number 517080
• Logical relations and the typed λ-calculus
• Higher-Order Logic and Type Theory
• scientific article; zbMATH DE number 6970800

Cites work

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

Cited in

(20)

• Graph operations characterizing rank-width
• Uniform and nonuniform recognizability.
• The rank-width of edge-coloured graphs
• Counting truth assignments of formulas of bounded tree-width or clique-width
• A model-theoretic characterisation of clique width
• The recognizability of sets of graphs is a robust property
• Recognizable series on hypergraphs
• F-rank-width of (edge-colored) graphs
• Simple monadic theories and partition width
• Graph Operations Characterizing Rank-Width and Balanced Graph Expressions
• scientific article; zbMATH DE number 125890 (Why is no real title available?)
• Recognizable sets of graphs: equivalent definitions and closure properties
• scientific article; zbMATH DE number 638367 (Why is no real title available?)
• Prefix-Recognizable Graphs and Monadic Logic
• scientific article; zbMATH DE number 6747949 (Why is no real title available?)
• Relational structures constructible by quantifier free definable operations
• Developments in Language Theory
• Clique-width of point configurations
• Compact labelings for efficient first-order model-checking
• Model checking on interpretations of classes of bounded local cliquewidth

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

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