A gentle introduction to applications of algorithmic metatheorems for space and circuit classes

DOI10.3390/A9030044zbMath1461.68249OpenAlexW2475093016MaRDI QIDQ1736808

Till Tantau

Publication date: 26 March 2019

Published in: Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.3390/a9030044

zbMATH Keywords

monadic second-order logictree widthlogarithmic spacealgorithmic metatheoremsCourcelle's theoremtree depthcircuit classes

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Logic in computer science (03B70) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) General topics in the theory of algorithms (68W01) Networks and circuits as models of computation; circuit complexity (68Q06)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of first-order and monadic second-order logic revisited
• Linear time solvable optimization problems on graphs of bounded clique-width
• Saving space by algebraization
• Algorithmic Meta Theorems for Circuit Classes of Constant and Logarithmic Depth
• Existential Second-order Logic over Graphs: A Complete Complexity-theoretic Classification
• Deciding first-order properties of locally tree-decomposable structures
• Counting Paths in VPA Is Complete for #NC 1
• Undirected connectivity in log-space
• A taxonomy of problems with fast parallel algorithms
• On the presence of disjoint subgraphs of a specified type
• Canonizing Graphs of Bounded Tree Width in Logspace
• Deciding First-Order Properties of Nowhere Dense Graphs
• Existential second-order logic over graphs
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth

This page was built for publication: A gentle introduction to applications of algorithmic metatheorems for space and circuit classes