The monadic second-order logic of graphs. X: Linear orderings
From MaRDI portal
Publication:1366538
DOI10.1016/0304-3975(95)00083-6zbMath0877.68087OpenAlexW2059287145MaRDI QIDQ1366538
Publication date: 18 September 1997
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(95)00083-6
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (24)
Trees, grids, and MSO decidability: from graphs to matroids ⋮ Induced betweenness in order-theoretic trees ⋮ Monadic second-order definable text languages ⋮ Vertex-minors, monadic second-order logic, and a conjecture by Seese ⋮ Definability equals recognizability for \(k\)-outerplanar graphs and \(l\)-chordal partial \(k\)-trees ⋮ Spined categories: generalizing tree-width beyond graphs ⋮ A monadic second-order definition of the structure of convex hypergraphs. ⋮ Clique-width of countable graphs: A compactness property. ⋮ The monadic second-order logic of graphs. XI: Hierarchical decompositions of connected graphs ⋮ Upper bounds to the clique width of graphs ⋮ The monadic second-order logic of graphs. IX: Machines and their behaviours ⋮ Circle graphs and monadic second-order logic ⋮ The modular decomposition of countable graphs. Definition and construction in monadic second-order logic ⋮ GETGRATS ⋮ Computer science and the fine structure of Borel sets ⋮ The monadic second-order logic of graphs. XV: On a conjecture by D. Seese ⋮ Computations by fly-automata beyond monadic second-order logic ⋮ Towards a characterization of order-invariant queries over tame graphs ⋮ Pomset Languages of Finite Step Transition Systems ⋮ Nondeterministic operations on finite relational structures ⋮ The monadic second-order logic of graphs. XII: Planar graphs and planar maps ⋮ The recognizability of sets of graphs is a robust property ⋮ Counting modulo quantifiers on finite structures ⋮ Linear time and the power of one first-order universal quantifier
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Asynchronous mappings and asynchronous cellular automata
- Separating subgraphs in k-trees: Cables and caterpillars
- An axiomatic definition of context-free rewriting and its application to NLC graph grammars
- Theory of traces
- Complement reducible graphs
- 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
- Monadic second-order definable graph transductions: a survey
- The monadic second order logic of graphs. VI: On several representations of graphs by relational structures
- How to define a linear order on finite models
- Graphs indecomposable with respect to the X-join
- The monadic second-order logic of graphs. VIII: Orientations
- Structural properties of context-free sets of graphs generated by vertex replacement
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Recognizable sets of graphs: equivalent definitions and closure properties
- Logical definability on infinite traces
- MSO definable text languages
This page was built for publication: The monadic second-order logic of graphs. X: Linear orderings