Computations by fly-automata beyond monadic second-order logic

DOI10.1016/j.tcs.2015.12.026zbMath1335.68116arXiv1305.7120OpenAlexW1525922973MaRDI QIDQ5964015

Bruno Courcelle, Irène Durand

Publication date: 26 February 2016

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1305.7120

zbMATH Keywords

dynamic programmingmonadic second-order logicmodel-checkinggraph algorithmsalgorithmic meta-theoremsclique-widthdata complexityinfinite automataparameterized algorithmstree-width

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Specification and verification (program logics, model checking, etc.) (68Q60) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (9)

Grammars and clique-width bounds from split decompositions ⋮ On quasi-planar graphs: clique-width and logical description ⋮ From tree-decompositions to clique-width terms ⋮ Fair allocation algorithms for indivisible items under structured conflict constraints ⋮ On defining linear orders by automata ⋮ Practical algorithms for MSO model-checking on tree-decomposable graphs ⋮ Fly-automata for checking \(\mathrm{MSO}_2\) graph properties ⋮ Vector domination in split-indifference graphs ⋮ Clique-width of point configurations

Uses Software

• Symbolic automata

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fly-automata for checking monadic second-order properties of graphs of bounded tree-width
• Fundamentals of parameterized complexity
• Tight complexity bounds for FPT subgraph problems parameterized by the clique-width
• Complexity of finding maximum regular induced subgraphs with prescribed degree
• Courcelle's theorem -- a game-theoretic approach
• On the model-checking of monadic second-order formulas with edge set quantifications
• On the algorithmic effectiveness of digraph decompositions and complexity measures
• Practical algorithms for MSO model-checking on tree-decomposable graphs
• On the complexity of some colorful problems parameterized by treewidth
• Monadic second-order evaluations on tree-decomposable graphs
• Handbook of weighted automata
• MSOL partitioning problems on graphs of bounded treewidth and clique-width
• Equivalences and transformations of regular systems - applications to recursive program schemes and grammars
• Minimisation of acyclic deterministic automata in linear time
• Finite tree automata with cost functions
• The monadic second-order logic of graphs. X: Linear orderings
• The complexity of first-order and monadic second-order logic revisited
• A unified approach to polynomial algorithms on graphs of bounded (bi-)rank-width
• Automata for the verification of monadic second-order graph properties
• Linear time solvable optimization problems on graphs of bounded clique-width
• The rank-width of edge-coloured graphs
• Parametrized complexity theory.
• Model-Checking by Infinite Fly-Automata
• Expansions of MSO by cardinality relations
• Symbolic Automata: The Toolkit
• Monadic datalog over finite structures of bounded treewidth
• First-Order and Monadic Second-Order Model-Checking on Ordered Structures
• Easy problems for tree-decomposable graphs
• Clique-Width is NP-Complete
• The Complexity of Translating Logic to Finite Automata

This page was built for publication: Computations by fly-automata beyond monadic second-order logic