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-HzbMATH Open0754.68065MaRDI QIDQ1176232FDOQ1176232
Publication date: 25 June 1992
Published in: Theoretical Computer Science (Search for Journal in Brave)
Recommendations
- A regular characterization of graph languages definable in monadic second-order logic
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- scientific article; zbMATH DE number 17791
- Monadic second-order definable graph transductions: a survey
- scientific article; zbMATH DE number 1136093
- Developments in Language Theory
- scientific article; zbMATH DE number 1223635
- scientific article
- scientific article; zbMATH DE number 2079025
- scientific article; zbMATH DE number 1290983
Formal languages and automata (68Q45) 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
- Title not available (Why is that?)
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Initial Algebra Semantics and Continuous Algebras
- Title not available (Why is that?)
- Title not available (Why is that?)
- The Recognition of Series Parallel Digraphs
- Weak Second‐Order Arithmetic and Finite Automata
- The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
- On Some Variants of the Bandwidth Minimization Problem
- Title not available (Why is that?)
- 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
- Tree acceptors and some of their applications
- Title not available (Why is that?)
- Algebraic automata and context-free sets
- Equivalences and transformations of regular systems - applications to recursive program schemes and grammars
- Graph expressions and graph rewritings
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (60)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Definability equals recognizability of partial 3-trees
- Weighted tree automata and weighted logics
- Uniform and nonuniform recognizability.
- A regular characterization of graph languages definable in monadic second-order logic
- The monadic second-order logic of graphs. VII: Graphs as relational structures
- A Retrospective on (Meta) Kernelization
- Recognizability, hypergraph operations, and logical types
- Title not available (Why is that?)
- The monadic second-order logic of graphs. X: Linear orderings
- Computing with graph rewriting systems with priorities
- NP-completeness of \(k\)-connected hyperedge-replacement languages of order \(k\)
- Shelah-Stupp's and Muchnik's iterations revisited
- Rule-based top-down parsing for acyclic contextual hyperedge replacement grammars
- The monadic second-order logic of graphs, II: Infinite graphs of bounded width
- Basic notions of universal algebra for language theory and graph grammars
- Fixed-Parameter Tractability of Treewidth and Pathwidth
- Monadic second-order definable text languages
- The monadic second-order logic of graphs. XI: Hierarchical decompositions of connected graphs
- Nondeterministic operations on finite relational structures
- Title not available (Why is that?)
- Rationality in algebras with a series operation
- Towards a language theory for infinite N-free pomsets.
- Monadic second-order definable graph transductions: a survey
- A comparison of tree transductions defined by monadic second order logic and by attribute grammars
- Recognizability equals definability for partial k-paths
- Towards a characterization of order-invariant queries over tame graphs
- On Several Proofs of the Recognizability Theorem
- The monadic second-order logic of graphs. XV: On a conjecture by D. Seese
- Title not available (Why is that?)
- Recognising \(k\)-connected hypergraphs in cubic time
- Title not available (Why is that?)
- Recognizable sets of graphs of bounded tree-width
- Recognizability equals definability for graphs of bounded treewidth and bounded chordality
- Title not available (Why is that?)
- Regular Subgraphs in Graphs and Rooted Graphs and Definability in Monadic Second - Order Logic
- Logical description of context-free graph languages
- The obstructions of a minor-closed set of graphs defined by hyperedge replacement can be constructed
- Monadic second-order evaluations on tree-decomposable graphs
- wMSO theories as grammar formalisms
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- MSO definable text languages
- The definition in monadic second-order logic of modular decompositions of ordered graphs
- On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
- Causality in Bounded Petri Nets is MSO Definable
- Weighted parsing for grammar-based language models over multioperator monoids
- Formalization and correctness of predictive shift-reduce parsers for graph grammars based on hyperedge replacement
- Recognizable sets of graphs: equivalent definitions and closure properties
- Title not available (Why is that?)
- The monadic second order logic of graphs. VI: On several representations of graphs by relational structures
- Title not available (Why is that?)
- Regular-factors in the complements of partial k-trees
- The monadic second-order logic of graphs. VIII: Orientations
- Prefix-Recognizable Graphs and Monadic Logic
- The monadic second-order logic of graphs. IV: Definability properties of equational graphs
- The use of tree transducers to compute translations between graph algebras
- The obstructions of a minor-closed set of graphs defined by a context-free grammar
- Characterization and complexity of uniformly nonprimitive labeled 2-structures
- Definability equals recognizability for \(k\)-outerplanar graphs and \(l\)-chordal partial \(k\)-trees
This page was built for publication: The monadic second-order logic of graphs. V: On closing the gap between definability and recognizability
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1176232)
