Linear delay enumeration and monadic second-order logic

DOI10.1016/j.dam.2008.08.021zbMath1217.03024OpenAlexW2041198634MaRDI QIDQ967312

Bruno Courcelle

Publication date: 28 April 2010

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2008.08.021

zbMATH Keywords

monadic second-order logicenumerationrandom generationunfoldingquerytree-widthtree automatonDAGmonadic second-order transductionrecognizable set of terms

Mathematics Subject Classification ID

Related Items (19)

On enumerating monomials and other combinatorial structures by polynomial interpolation ⋮ Enumerating minimal dominating sets in chordal bipartite graphs ⋮ Cograph generation with linear delay ⋮ Computing thejth solution of a first-order query ⋮ Output-polynomial enumeration on graphs of bounded (local) linear MIM-width ⋮ Compact representation for answer sets of \(n\)-ary regular queries ⋮ Counting Minimal Dominating Sets ⋮ An incremental polynomial time algorithm to enumerate all minimal edge dominating sets ⋮ Enumerating models of DNF faster: breaking the dependency on the formula size ⋮ Efficient enumeration of dominating sets for sparse graphs ⋮ Refined notions of parameterized enumeration kernels with applications to matching cut enumeration ⋮ Monadic second-order model-checking on decomposable matroids ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On the dualization in distributive lattices and related problems ⋮ Enumeration of Minimal Dominating Sets and Variants ⋮ Enumerating Minimal Dominating Sets in Triangle-Free Graphs ⋮ A Polynomial Delay Algorithm for Enumerating Minimal Dominating Sets in Chordal Graphs ⋮ Structural tractability of enumerating CSP solutions

Cites Work

• Unnamed Item
• Unnamed Item
• Random generation of words in an algebraic language in linear binary space
• Generating words in a context-free language uniformly at random
• Query efficient implementation of graphs of bounded clique-width
• The complexity of first-order and monadic second-order logic revisited
• Tree acceptors and some of their applications
• Uniform Random Generation of Strings in a Context-Free Language
• Random Generation for Finitely Ambiguous Context-free Languages
• MSO Queries on Tree Decomposable Structures Are Computable with Linear Delay
• Handbook of Graph Grammars and Computing by Graph Transformation
• First-order queries on structures of bounded degree are computable with constant delay
• Database Programming Languages
• Generalized finite automata theory with an application to a decision problem of second-order logic
• Graph-Theoretic Concepts in Computer Science
• Finding Branch-Decompositions and Rank-Decompositions

This page was built for publication: Linear delay enumeration and monadic second-order logic