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)- Exploiting chordal structure in polynomial ideals: a Gröbner bases approach
- The complexity of the perfect matching-cut problem
- Balancedness of MSO transductions in polynomial time
- Prefix-Recognizable Graphs and Monadic Logic
- Clique-perfectness of complements of line graphs
- Where first-order and monadic second-order logic coincide
- Digraphs of bounded width
- scientific article; zbMATH DE number 7471715 (Why is no real title available?)
- On the (parameterized) complexity of recognizing well-covered (\(r\),\(\ell\))-graph
- Perfectly matched sets in graphs: parameterized and exact computation
- Fly-automata, their properties and applications
- Beyond classes of graphs with ``few minimal separators: FPT results through potential maximal cliques
- The behavior of clique-width under graph operations and graph transformations
- Recognizable languages of arrows and cospans
- scientific article; zbMATH DE number 7561615 (Why is no real title available?)
- Towards an Efficient Tree Automata based technique for Timed Systems
- Subgraph complementation
- scientific article; zbMATH DE number 7029306 (Why is no real title available?)
- Induced betweenness in order-theoretic trees
- Edge deletion to tree-like graph classes
- The complexity of finding small separators in temporal graphs
- Bundled crossings revisited
- A meta-theorem for distributed certification
- The monadic second-order logic of graphs. IX: Machines and their behaviours
- ASNP: a tame fragment of existential second-order logic
- Verifying graph programs with monadic second-order logic
- Fixed-Parameter Tractable Canonization and Isomorphism Test for Graphs of Bounded Treewidth
- A new approach for contact graph representations and its applications
- Definability equals recognizability for \(k\)-outerplanar graphs and \(l\)-chordal partial \(k\)-trees
- 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
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)
