Graph structure and monadic second-order logic. A language-theoretic approach
From MaRDI portal
Automata and formal grammars in connection with logical questions (03D05) Graph algorithms (graph-theoretic aspects) (05C85) Applications of graph theory (05C90) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10)
Recommendations
- Graph Structure and Monadic Second-Order Logic: Language Theoretical Aspects
- Monadic Second-Order Logic for Graphs: Algorithmic and Language Theoretical Applications
- scientific article; zbMATH DE number 1696755
- scientific article; zbMATH DE number 177437
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
Cited in
(only showing first 100 items - show all)- A regular characterization of graph languages definable in monadic second-order logic
- The monadic second-order logic of graphs. VII: Graphs as relational structures
- Monadic second-order logic, graph coverings and unfoldings of transition systems
- Existential monadic second order logic on random rooted trees
- Parameterized model checking of rendezvous systems
- Balancedness of MSO transductions in polynomial time
- Deciding whether there are infinitely many prime graphs with forbidden induced subgraphs
- A simple linear time algorithm for the locally connected spanning tree problem on maximal planar chordal graphs
- Second-order propositional modal logic: expressiveness and completeness results
- Finding a potential community in networks
- Reachability analysis of reversal-bounded automata on series-parallel graphs
- Multiple context-free tree grammars: lexicalization and characterization
- On retracts, absolute retracts, and foldings in cographs
- Fly-automata for checking \(\mathrm{MSO}_2\) graph properties
- On the (parameterized) complexity of recognizing well-covered (\(r\),\(\ell\))-graph
- Automata for the verification of monadic second-order graph properties
- On the tree-width of even-hole-free graphs
- The complexity of finding small separators in temporal graphs
- Linear-bounded composition of tree-walking tree transducers: linear size increase and complexity
- Bottom-up unranked tree-to-graph transducers for translation into semantic graphs
- Measuring what matters: a hybrid approach to dynamic programming with treewidth
- On knot-free vertex deletion: fine-grained parameterized complexity analysis of a deadlock resolution graph problem
- Context-sensitive fusion grammars and fusion grammars with forbidden context are universal
- Maximum matching in almost linear time on graphs of bounded clique-width
- A meta-theorem for distributed certification
- ASNP: a tame fragment of existential second-order logic
- Shelah-Stupp's and Muchnik's iterations revisited
- Verifying graph programs with monadic second-order logic
- Finite-image property of weighted tree automata over past-finite monotonic strong bimonoids
- Regular model checking with regular relations
- Verification of agent navigation in partially-known environments
- Minimum \(t\)-spanners on subcubic graphs
- An adjacency labeling scheme based on a decomposition of trees into caterpillars
- Grammars and clique-width bounds from split decompositions
- On quasi-planar graphs: clique-width and logical description
- Subgraph complementation
- Parameterized orientable deletion
- Bisimulation invariant monadic-second order logic in the finite
- Bundled crossings revisited
- Graph theory in Coq: minors, treewidth, and isomorphisms
- On caterpillar factors in graphs
- XML navigation and transformation by tree-walking automata and transducers with visible and invisible pebbles
- How to compute digraph width measures on directed co-graphs
- Classes of graphs with low complexity: the case of classes with bounded linear rankwidth
- Fixed-treewidth-efficient algorithms for edge-deletion to interval graph classes
- One-way resynchronizability of word transducers
- Efficient computation of the oriented chromatic number of recursively defined digraphs
- Rabin's theorem in the concurrency setting: a conjecture
- Language theoretic properties of regular DAG languages
- Nontrivial path covers of graphs: existence, minimization and maximization
- On width measures and topological problems on semi-complete digraphs
- Comparing linear width parameters for directed graphs
- Linear rank-width and linear clique-width of trees
- On labeled birooted tree languages: algebras, automata and logic
- A characterisation of clique-width through nested partitions
- Clique-width and edge contraction
- The rank-width of edge-coloured graphs
- Definability equals recognizability for \(k\)-outerplanar graphs and \(l\)-chordal partial \(k\)-trees
- Tractability, hardness, and kernelization lower bound for and/or graph solution
- Computing square roots of graphs with low maximum degree
- From tree-decompositions to clique-width terms
- Fast exact algorithms for some connectivity problems parameterized by clique-width
- Logics for unordered trees with data constraints
- The monadic quantifier alternation hierarchy over grids and graphs
- Can one design a geometry engine? Can one design a geometry engine? On the (un)decidability of certain affine Euclidean geometries
- Computability by monadic second-order logic
- Deleting edges to restrict the size of an epidemic in temporal networks
- An algorithmic metatheorem for directed treewidth
- Clique-width of path powers
- Posets with interfaces as a model for concurrency
- FPT algorithms to compute the elimination distance to bipartite graphs and more
- Transformation of variants of Petri nets into context-dependent fusion grammars
- The Caucal hierarchy: interpretations in the (W)MSO+\(\mathsf{U}\) logic
- Graph planning with expected finite horizon
- Computing the best-case energy complexity of satisfying assignments in monotone circuits
- On the computational complexity of the bipartizing matching problem
- Parameterized complexity of computing maximum minimal blocking and hitting sets
- FPT and kernelization algorithms for the induced tree problem
- Perfectly matched sets in graphs: parameterized and exact computation
- A linear time algorithm for metric dimension of cactus block graphs
- Parameterized complexity of CTL
- Verification of parameterized communicating automata via split-width
- Strong Backdoors for Default Logic
- Exploiting chordal structure in polynomial ideals: a Gröbner bases approach
- Causality in bounded Petri nets is MSO definable
- Beyond Classes of Graphs with “Few” Minimal Separators: FPT Results Through Potential Maximal Cliques
- A Practical Algorithm for the Uniform Membership Problem of Labeled Multidigraphs of Tree-Width 2 for Spanning Tree Automata
- A constant time algorithm for some optimization problems in rotagraphs and fasciagraphs
- Relating paths in transition systems: the fall of the modal mu-calculus
- Regularity equals monadic second-order definability for quasi-trees
- Capturing MSO with one quantifier
- Large Induced Subgraphs via Triangulations and CMSO
- A logical approach to locality in pictures languages
- Fixed-Parameter Tractable Canonization and Isomorphism Test for Graphs of Bounded Treewidth
- Unified reasoning about robustness properties of symbolic-heap separation logic
- On the computational complexity of variants of combinatorial voter control in elections
- Digraphs of bounded width
- Graph transformation meets reversible circuits: model transformation and optimization
- Recognizability equals definability for graphs of bounded treewidth and bounded chordality
- Fly-automata for checking monadic second-order properties of graphs of bounded tree-width
This page was built for publication: Graph structure and monadic second-order logic. A language-theoretic approach
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3077955)
