The monadic second-order logic of graphs, II: Infinite graphs of bounded width
From MaRDI portal
Publication:3470112
Recommendations
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- The monadic second-order logic of graphs. XV: On a conjecture by D. Seese
- The monadic second-order logic of graphs. IV: Definability properties of equational graphs
- The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
- The monadic second-order logic of graphs. V: On closing the gap between definability and recognizability
Cites work
- Algebraic semantics
- An axiomatic definition of context-free rewriting and its application to NLC graph grammars
- Decidability of Second-Order Theories and Automata on Infinite Trees
- Equivalences and transformations of regular systems - applications to recursive program schemes and grammars
- Fundamental properties of infinite trees
- Graph expressions and graph rewritings
- scientific article; zbMATH DE number 4008383 (Why is no real title available?)
- scientific article; zbMATH DE number 4049097 (Why is no real title available?)
- scientific article; zbMATH DE number 4049098 (Why is no real title available?)
- scientific article; zbMATH DE number 4106286 (Why is no real title available?)
- scientific article; zbMATH DE number 3492660 (Why is no real title available?)
- scientific article; zbMATH DE number 3057871 (Why is no real title available?)
- Infinite hypergraphs. I: Basic properties
- Initial Algebra Semantics and Continuous Algebras
- 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
- The theory of ends, pushdown automata, and second-order logic
- Tree acceptors and some of their applications
Cited in
(52)- Deterministic finite automata with recursive calls and DPDAs
- \(L(A)=L(B)\)? decidability results from complete formal systems
- Distributive lattices with a decidable monadic second order theory.
- The monadic second-order logic of graphs. VIII: Orientations
- On infinite transition graphs having a decidable monadic theory
- The monadic second-order logic of graphs. XIV: Uniformly sparse graphs and edge set quantifica\-tions.
- Automatic graphs and D0L-sequences of finite graphs
- Regular sets of infinite message sequence charts
- Shelah-Stupp's and Muchnik's iterations revisited
- Graphs and models with finite chains
- Branch-width, parse trees, and monadic second-order logic for matroids.
- The monadic second-order logic of graphs. XV: On a conjecture by D. Seese
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- A logic of reachable patterns in linked data-structures
- Rewriting in the partial algebra of typed terms modulo AC
- Regularity equals monadic second-order definability for quasi-trees
- Monadic structures over an ordered universal random graph and finite automata
- Simple monadic theories and partition width
- Solvability of theories of certain classes of elimination graphs
- Fly-automata for checking monadic second-order properties of graphs of bounded tree-width
- Graph Structure and Monadic Second-Order Logic: Language Theoretical Aspects
- The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
- scientific article; zbMATH DE number 1223635 (Why is no real title available?)
- Automata-based Representations for Infinite Graphs
- Regular Subgraphs in Graphs and Rooted Graphs and Definability in Monadic Second - Order Logic
- scientific article; zbMATH DE number 2080202 (Why is no real title available?)
- An effective version of Stallings' theorem in the case of context-free groups
- scientific article; zbMATH DE number 219229 (Why is no real title available?)
- Order-theoretic Trees: Monadic Second-order Descriptions and Regularity
- Guarded second-order logic, spanning trees, and network flows
- Where first-order and monadic second-order logic coincide
- Monadic second order finite satisfiability and unbounded tree-width
- On spectra of sentences of monadic second order logic with counting
- Algebraic and logical descriptions of generalized trees
- Computer Science Logic
- Leaving Traces: A Note on a Sound and Complete Trace Logic for Concurrent Constraint Programs
- Mathematical Foundations of Computer Science 2003
- On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
- The monadic second-order logic of graphs : Definable sets of finite graphs
- Succinct data structures for bounded clique-width graphs
- Automorphism groups of context-free graphs
- The monadic second-order logic of graphs. IX: Machines and their behaviours
- On the regular structure of prefix rewriting
- Decidable (ac)counting with Parikh and Muller: adding Presburger arithmetic to monadic second-order logic over tree-interpretable structures
- Derivatives on graphs for the positive calculus of relations with transitive closure
- FO logic on cellular automata orbits equals MSO logic
- Decidability of querying first-order theories via countermodels of finite width
- Logical aspects of Cayley-graphs: the group case
- The monadic second-order logic of graphs. IV: Definability properties of equational graphs
- The structure of the models of decidable monadic theories of graphs
- Linearly bounded infinite graphs
- Vertex-minors, monadic second-order logic, and a conjecture by Seese
This page was built for publication: The monadic second-order logic of graphs, II: Infinite graphs of bounded width
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3470112)
