Graph structure and monadic second-order logic. A language-theoretic approach
From MaRDI portal
Publication:3077955
Applications of graph theory (05C90) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Formal languages and automata (68Q45) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Automata and formal grammars in connection with logical questions (03D05)
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)- Lower bounds on the complexity of \(\mathsf{MSO}_1\) model-checking
- Parametrised complexity of satisfiability in temporal logic
- Grouped domination parameterized by vertex cover, twin cover, and beyond
- scientific article; zbMATH DE number 7471674 (Why is no real title available?)
- Unified reasoning about robustness properties of symbolic-heap separation logic
- Graph theory in Coq: minors, treewidth, and isomorphisms
- 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
- Counting kernels in directed graphs with arbitrary orientations
- Recurrence relations for graph polynomials on bi-iterative families of graphs
- Context-sensitive fusion grammars and fusion grammars with forbidden context are universal
- scientific article; zbMATH DE number 7559390 (Why is no real title available?)
- On retracts, absolute retracts, and foldings in cographs
- An algorithmic metatheorem for directed treewidth
- Clique-width of path powers
- Acyclic coloring parameterized by directed clique-width
- A Retrospective on (Meta) Kernelization
- Are there any good digraph width measures?
- Polynomial time algorithms for computing a minimum hull set in distance-hereditary and chordal graphs
- Feedback vertex set and even cycle transversal for \(H\)-free graphs: finding large block graphs
- Beyond Classes of Graphs with “Few” Minimal Separators: FPT Results Through Potential Maximal Cliques
- Regular planar monoidal languages
- Existential monadic second order logic on random rooted trees
- 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
- The complexity of two graph orientation problems
- Finer tight bounds for coloring on clique-width
- Finer tight bounds for coloring on clique-width
- Generalisations of matrix partitions: complexity and obstructions
- Strong backdoors for default logic
- Strong Backdoors for Default Logic
- scientific article; zbMATH DE number 4124985 (Why is no real title available?)
- Treewidth-two graphs as a free algebra
- Regularity equals monadic second-order definability for quasi-trees
- Capturing MSO with one quantifier
- Finding a potential community in networks
- Reachability analysis of reversal-bounded automata on series-parallel graphs
- Courcelle's theorem -- a game-theoretic approach
- Shelah-Stupp's and Muchnik's iterations revisited
- The monadic second-order logic of graphs XVI : Canonical graph decompositions
- A linear time algorithm for metric dimension of cactus block graphs
- A constant time algorithm for some optimization problems in rotagraphs and fasciagraphs
- Recovering sparse graphs
- Rabin's theorem in the concurrency setting: a conjecture
- Towards compositional graph theory
- Harary polynomials
- Convolution and concurrency
- Deleting edges to restrict the size of an epidemic in temporal networks
- Parameterized complexity of CTL
- One-way resynchronizability of word transducers
- Efficient computation of the oriented chromatic number of recursively defined digraphs
- Graph planning with expected finite horizon
- Deleting edges to restrict the size of an epidemic in temporal networks
- On \(H\)-topological intersection graphs
- Fast FPT-approximation of branchwidth
- On the computational complexity of the bipartizing matching problem
- Algebras for tree decomposable graphs
- FPT and kernelization algorithms for the induced tree problem
- Multiple context-free tree grammars: lexicalization and characterization
- scientific article; zbMATH DE number 7795664 (Why is no real title available?)
- Network-based vertex dissolution
- Seurat games on Stockmeyer graphs
- A logical approach to locality in pictures languages
- Analyzing timed systems using tree automata
- Crossing minimization for 1-page and 2-page drawings of graphs with bounded treewidth
- Streaming ranked-tree-to-string transducers
- On the parameterized complexity of s-club cluster deletion problems
- On the algebraization of Henkin‐type second‐order logic
- Parameterized model checking of rendezvous systems
- Computing with tangles
- A Büchi-Elgot-Trakhtenbrot theorem for automata with MSO graph storage
- Verification of parameterized communicating automata via split-width
- Finite-image property of weighted tree automata over past-finite monotonic strong bimonoids
- A reasoning system for satisfiability of diagrammatic specifications
- Clique-width and edge contraction
- Can one design a geometry engine? Can one design a geometry engine? On the (un)decidability of certain affine Euclidean geometries
- A Decision Procedure for Guarded Separation Logic Complete Entailment Checking for Separation Logic with Inductive Definitions
- Determinacy and rewriting of functional top-down and MSO tree transformations
- Tree automata and pigeonhole classes of matroids. II
- Betweenness of partial orders
- Definable decompositions for graphs of bounded linear cliquewidth
- Causality in bounded Petri nets is MSO definable
- Regular model checking with regular relations
- Verification of agent navigation in partially-known environments
- Property testing for bounded degree databases
- Tractability, hardness, and kernelization lower bound for and/or graph solution
- Bottom-up unranked tree-to-graph transducers for translation into semantic graphs
- On caterpillar factors in graphs
- Well-quasi-ordering of matrices under Schur complement and applications to directed graphs
- Parameterized orientable deletion
- Linear rank-width and linear clique-width of trees
- Comparing linear width parameters for directed graphs
- Properties of graphs specified by a regular language
- Fixed-treewidth-efficient algorithms for edge-deletion to interval graph classes
- scientific article; zbMATH DE number 1290983 (Why is no real title available?)
- Parameterized orientable deletion
- On the computational complexity of variants of combinatorial voter control in elections
- Grouped domination parameterized by vertex cover, twin cover, and beyond
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)
