The monadic second-order logic of graphs. V: On closing the gap between definability and recognizability
From MaRDI portal
(Redirected from Publication:1176232)
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; zbMATH DE number 4106286
- scientific article; zbMATH DE number 2079025
- scientific article; zbMATH DE number 1290983
Cites work
- scientific article; zbMATH DE number 3882430 (Why is no real title available?)
- scientific article; zbMATH DE number 3885965 (Why is no real title available?)
- scientific article; zbMATH DE number 3829278 (Why is no real title available?)
- scientific article; zbMATH DE number 4049099 (Why is no real title available?)
- scientific article; zbMATH DE number 4049150 (Why is no real title available?)
- scientific article; zbMATH DE number 4081531 (Why is no real title available?)
- scientific article; zbMATH DE number 3615891 (Why is no real title available?)
- scientific article; zbMATH DE number 1142314 (Why is no real title available?)
- scientific article; zbMATH DE number 1142315 (Why is no real title available?)
- Algebraic automata and context-free sets
- 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
- Graph expressions and graph rewritings
- Initial Algebra Semantics and Continuous Algebras
- On Some Variants of the Bandwidth Minimization Problem
- Resolution of equations in algebraic structures. Volume II: Rewriting techniques
- The Recognition of Series Parallel Digraphs
- The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- The monadic second-order logic of graphs. IV: Definability properties of equational graphs
- The structure of the models of decidable monadic theories of graphs
- Tree acceptors and some of their applications
- Weak Second‐Order Arithmetic and Finite Automata
Cited in
(64)- 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
- scientific article; zbMATH DE number 7559390 (Why is no real title available?)
- Recognizability, hypergraph operations, and logical types
- A Retrospective on (Meta) Kernelization
- The monadic second-order logic of graphs. X: Linear orderings
- Computing with graph rewriting systems with priorities
- scientific article; zbMATH DE number 4124985 (Why is no real title available?)
- 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
- Monadic second-order definable text languages
- Nondeterministic operations on finite relational structures
- The monadic second-order logic of graphs. XI: Hierarchical decompositions of connected graphs
- scientific article; zbMATH DE number 809155 (Why is no real title available?)
- A Büchi-Elgot-Trakhtenbrot theorem for automata with MSO graph storage
- 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
- The monadic second-order logic of graphs. XV: On a conjecture by D. Seese
- Causality in bounded Petri nets is MSO definable
- On Several Proofs of the Recognizability Theorem
- scientific article; zbMATH DE number 17791 (Why is no real title available?)
- Recognising \(k\)-connected hypergraphs in cubic time
- scientific article; zbMATH DE number 2143018 (Why is no real title available?)
- Recognizable sets of graphs of bounded tree-width
- Recognizability equals definability for graphs of bounded treewidth and bounded chordality
- Regular Subgraphs in Graphs and Rooted Graphs and Definability in Monadic Second - Order Logic
- Logical description of context-free graph languages
- scientific article; zbMATH DE number 7204410 (Why is no real title available?)
- Monadic second-order evaluations on tree-decomposable graphs
- The obstructions of a minor-closed set of graphs defined by hyperedge replacement can be constructed
- wMSO theories as grammar formalisms
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Weighted parsing for grammar-based language models over multioperator monoids
- MSO definable text languages
- The definition in monadic second-order logic of modular decompositions of ordered graphs
- Formalization and correctness of predictive shift-reduce parsers for graph grammars based on hyperedge replacement
- On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
- Recognizable sets of graphs: equivalent definitions and closure properties
- scientific article; zbMATH DE number 4049098 (Why is no real title available?)
- A logic on subobjects and recognizability
- A non-regular language of infinite trees that is recognizable by a sort-wise finite algebra
- The monadic second order logic of graphs. VI: On several representations of graphs by relational structures
- scientific article; zbMATH DE number 3928955 (Why is no real title available?)
- Regular-factors in the complements of partial k-trees
- The monadic second-order logic of graphs : Definable sets of finite graphs
- The monadic second-order logic of graphs. VIII: Orientations
- The monadic second-order logic of graphs. IV: Definability properties of equational graphs
- Definability equals recognizability for \(k\)-outerplanar graphs
- Prefix-Recognizable Graphs and Monadic Logic
- 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
- Fixed-parameter tractability of treewidth and pathwidth
- Characterization and complexity of uniformly nonprimitive labeled 2-structures
- Definability equals recognizability of partial 3-trees
- 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)
