The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
From MaRDI portal
Publication:2641288
Recommendations
- The monadic second-order logic of graphs. V: On closing the gap between definability and recognizability
- scientific article; zbMATH DE number 17791
- scientific article; zbMATH DE number 4049098
- The monadic second-order logic of graphs, II: Infinite graphs of bounded width
- The monadic second-order logic of graphs. VII: Graphs as relational structures
Cites work
- scientific article; zbMATH DE number 3888893 (Why is no real title available?)
- scientific article; zbMATH DE number 3819693 (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 4049099 (Why is no real title available?)
- scientific article; zbMATH DE number 4060712 (Why is no real title available?)
- scientific article; zbMATH DE number 4060748 (Why is no real title available?)
- scientific article; zbMATH DE number 4060749 (Why is no real title available?)
- scientific article; zbMATH DE number 4081531 (Why is no real title available?)
- scientific article; zbMATH DE number 4106286 (Why is no real title available?)
- scientific article; zbMATH DE number 44213 (Why is no real title available?)
- scientific article; zbMATH DE number 3517129 (Why is no real title available?)
- scientific article; zbMATH DE number 3569855 (Why is no real title available?)
- scientific article; zbMATH DE number 3615891 (Why is no real title available?)
- scientific article; zbMATH DE number 4124985 (Why is no real title available?)
- scientific article; zbMATH DE number 3057871 (Why is no real title available?)
- Algebraic automata and context-free sets
- An axiomatic definition of context-free rewriting and its application to NLC graph grammars
- Automata in general algebras
- Equivalences and transformations of regular systems - applications to recursive program schemes and grammars
- Graph expressions and graph rewritings
- The NP-completeness column: an ongoing guide
- The monadic second-order logic of graphs, II: Infinite graphs of bounded width
- Tree acceptors and some of their applications
- Weak Second‐Order Arithmetic and Finite Automata
Cited in
(only showing first 100 items - show all)- Two strikes against perfect phylogeny
- Structural parameterization for minimum conflict-free colouring
- Coloured Tutte polynomials and Kauffman brackets for graphs of bounded tree width
- Recursive queries and context-free graph grammars
- Kernel bounds for path and cycle problems
- Approximation in (poly-) logarithmic space
- Lower bounds on the complexity of \(\mathsf{MSO}_1\) model-checking
- Ensuring correctness of model transformations while remaining decidable
- Grouped domination parameterized by vertex cover, twin cover, and beyond
- Trees, grids, and MSO decidability: from graphs to matroids
- Compactors for parameterized counting problems
- Minimum eccentricity shortest path problem with respect to structural parameters
- scientific article; zbMATH DE number 7471674 (Why is no real title available?)
- Graph theory in Coq: minors, treewidth, and isomorphisms
- Fully polynomial FPT algorithms for some classes of bounded clique-width graphs
- Branch-width, parse trees, and monadic second-order logic for matroids.
- Crossing number for graphs with bounded pathwidth
- Efficient parallel algorithms for parameterized problems
- Uniform and nonuniform recognizability.
- Practical algorithms for MSO model-checking on tree-decomposable graphs
- A regular characterization of graph languages definable in monadic second-order logic
- Logics for unordered trees with data constraints
- The monadic second-order logic of graphs. VII: Graphs as relational structures
- On guarding orthogonal polygons with sliding cameras
- Practical access to dynamic programming on tree decompositions
- A polynomial-time algorithm for finding total colorings of partial \(k\)-trees
- Optimization problems in dotted interval graphs
- Distance three labelings of trees
- scientific article; zbMATH DE number 7559390 (Why is no real title available?)
- Recognizability of graph and pattern languages
- Star colouring of bounded degree graphs and regular graphs
- Upper bounds on the size of obstructions and intertwines
- Algorithms and almost tight results for 3-colorability of small diameter graphs
- An algorithmic metatheorem for directed treewidth
- Towards fixed-parameter tractable algorithms for abstract argumentation
- Hitting minors on bounded treewidth graphs. I: General upper bounds
- Kernelization: new upper and lower bound techniques
- Algorithmic aspects of total Roman and total double Roman domination in graphs
- Computing the zig-zag number of directed graphs
- Contraction bidimensionality of geometric intersection graphs
- A Retrospective on (Meta) Kernelization
- Constructing tree decompositions of graphs with bounded gonality
- On the definability of properties of finite graphs
- Tree \(t\)-spanners in outerplanar graphs via supply demand partition
- scientific article; zbMATH DE number 7651188 (Why is no real title available?)
- On low rank-width colorings
- Are there any good digraph width measures?
- Lacon-, Shrub- and Parity-Decompositions: Characterizing Transductions of Bounded Expansion Classes
- Detecting fixed patterns in chordal graphs in polynomial time
- Treewidth, crushing and hyperbolic volume
- Optimization and Recognition for K 5-minor Free Graphs in Linear Time
- Decomposability helps for deciding logics of knowledge and belief
- Grundy Distinguishes Treewidth from Pathwidth
- Decision problems for edge grammars
- Beyond Classes of Graphs with “Few” Minimal Separators: FPT Results Through Potential Maximal Cliques
- scientific article; zbMATH DE number 2102748 (Why is no real title available?)
- On graphs coverable by \({k}\) shortest paths
- A presheaf semantics for quantified temporal logics
- Vertex partitioning problems on graphs with bounded tree width
- The dag-width of directed graphs
- Tree decomposition and discrete optimization problems: a survey
- The complexity of two graph orientation problems
- On the algorithmic effectiveness of digraph decompositions and complexity measures
- Complexity issues of perfect secure domination in graphs
- The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
- On enumerating minimal siphons in Petri nets using CLP and SAT solvers: theoretical and practical complexity
- On nowhere dense graphs
- The monadic second-order logic of graphs. X: Linear orderings
- On the vertex cover \(P_3\) problem parameterized by treewidth
- Computing with graph rewriting systems with priorities
- scientific article; zbMATH DE number 4124985 (Why is no real title available?)
- A parallel algorithm for edge-coloring partial k-trees
- Treewidth versus clique number. II: Tree-independence number
- Hardness transitions and uniqueness of acyclic colouring
- Graph decompositions for cartesian products
- Node replacements in embedding normal form.
- scientific article; zbMATH DE number 7525479 (Why is no real title available?)
- A strategy for dynamic programs: start over and muddle through
- Coloring graphs without short cycles and long induced paths
- Hitting minors on bounded treewidth graphs. III. Lower bounds
- Quadratic kernelization for convex recoloring of trees
- Algorithmic uses of the Feferman-Vaught theorem
- Exact exponential algorithms to find a tropical connected set of minimum size
- Finite integer index of pathwidth and treewidth
- Quantified conjunctive queries on partially ordered sets
- Quantified conjunctive queries on partially ordered sets
- First-Order Model-Checking in Random Graphs and Complex Networks
- Algorithmic Aspects of Outer-Independent Total Roman Domination in Graphs
- Syntactic recognizability of graphs with fuzzy attributes
- The string generating power of context-free hypergraph grammars
- Obstructions for matroids of path-width at most \(k\) and graphs of linear rank-width at most \(k\)
- Treewidth and logical definability of graph products
- Courcelle's theorem -- a game-theoretic approach
- Spanners in sparse graphs
- Complexity of path-forming games
- Model-checking hierarchical structures
- Decomposition width of matroids
- Tree-width of hypergraphs and surface duality
- Computing role assignments of proper interval graphs in polynomial time
- Computing LOGCFL certificates
This page was built for publication: The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2641288)
