The monadic second-order logic of graphs. V: On closing the gap between definability and recognizability
From MaRDI portal
Publication:1176232
DOI10.1016/0304-3975(91)90387-HzbMath0754.68065MaRDI QIDQ1176232
Publication date: 25 June 1992
Published in: Theoretical Computer Science (Search for Journal in Brave)
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (46)
Monadic second-order definable graph transductions: a survey ⋮ Towards a language theory for infinite N-free pomsets. ⋮ A Retrospective on (Meta) Kernelization ⋮ The monadic second order logic of graphs. VI: On several representations of graphs by relational structures ⋮ Regular-factors in the complements of partial k-trees ⋮ Fixed-Parameter Tractability of Treewidth and Pathwidth ⋮ Unnamed Item ⋮ Recognizability equals definability for graphs of bounded treewidth and bounded chordality ⋮ Monadic second-order definable text languages ⋮ Recognizable sets of graphs: equivalent definitions and closure properties ⋮ Weighted tree automata and weighted logics ⋮ The monadic second-order logic of graphs. X: Linear orderings ⋮ Definability equals recognizability for \(k\)-outerplanar graphs and \(l\)-chordal partial \(k\)-trees ⋮ Recognizability equals definability for partial k-paths ⋮ The obstructions of a minor-closed set of graphs defined by a context-free grammar ⋮ Logical description of context-free graph languages ⋮ Recognizable sets of graphs of bounded tree-width ⋮ MSO definable text languages ⋮ Formalization and correctness of predictive shift-reduce parsers for graph grammars based on hyperedge replacement ⋮ The monadic second-order logic of graphs. XI: Hierarchical decompositions of connected graphs ⋮ Basic notions of universal algebra for language theory and graph grammars ⋮ Characterization and complexity of uniformly nonprimitive labeled 2-structures ⋮ The use of tree transducers to compute translations between graph algebras ⋮ The obstructions of a minor-closed set of graphs defined by hyperedge replacement can be constructed ⋮ The definition in monadic second-order logic of modular decompositions of ordered graphs ⋮ The monadic second-order logic of graphs. VII: Graphs as relational structures ⋮ Recognising \(k\)-connected hypergraphs in cubic time ⋮ Monadic second-order evaluations on tree-decomposable graphs ⋮ NP-completeness of \(k\)-connected hyperedge-replacement languages of order \(k\) ⋮ The monadic second-order logic of graphs. XV: On a conjecture by D. Seese ⋮ Recognizability, hypergraph operations, and logical types ⋮ Unnamed Item ⋮ Towards a characterization of order-invariant queries over tame graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Computing with graph rewriting systems with priorities ⋮ Weighted parsing for grammar-based language models over multioperator monoids ⋮ Causality in Bounded Petri Nets is MSO Definable ⋮ Nondeterministic operations on finite relational structures ⋮ A comparison of tree transductions defined by monadic second order logic and by attribute grammars ⋮ The monadic second-order logic of graphs. VIII: Orientations ⋮ Uniform and nonuniform recognizability. ⋮ Rationality in algebras with a series operation ⋮ The monadic second-order logic of graphs. IV: Definability properties of equational graphs ⋮ Shelah-Stupp's and Muchnik's iterations revisited ⋮ Rule-based top-down parsing for acyclic contextual hyperedge replacement grammars
Cites Work
- The monadic second-order logic of graphs. IV: Definability properties of equational graphs
- The structure of the models of decidable monadic theories of graphs
- An algorithm to decide whether a rational subset of \({\mathbb{N}}^ k\) is recognizable
- Equivalences and transformations of regular systems - applications to recursive program schemes and grammars
- Tree acceptors and some of their applications
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Weak Second‐Order Arithmetic and Finite Automata
- On Some Variants of the Bandwidth Minimization Problem
- Graph expressions and graph rewritings
- The Recognition of Series Parallel Digraphs
- The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
- Initial Algebra Semantics and Continuous Algebras
- Algebraic automata and context-free sets
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: The monadic second-order logic of graphs. V: On closing the gap between definability and recognizability
