A gentle introduction to applications of algorithmic metatheorems for space and circuit classes
type: Item
instance of: scholarly article
title: A gentle introduction to applications of algorithmic metatheorems for space and circuit classes
zbMATH Open document ID: 1461.68249
author: Till Tantau
published in: Algorithms
publication date: 2019-03-26T00:00:00Z
review text: Summary: Algorithmic metatheorems state that if a problem can be described in a certain \textit{logic} and the inputs are \textit{structured} in a certain way, then the problem can be solved with a certain \textit{amount of resources.} As an example, by Courcelle's Theorem, all monadic second-order (``in a certain logic'') properties of graphs of bounded tree width (``structured in a certain way'') can be solved in linear time (``with a certain amount of resources''). Such theorems have become valuable tools in algorithmics: if a problem happens to have the right structure and can be described in the right logic, they immediately yield a (typically tight) upper bound on the time complexity of the problem. Perhaps even more importantly, several complex algorithms rely on algorithmic metatheorems internally to solve subproblems, which considerably broadens the range of applications of these theorems. This paper is intended as a gentle introduction to the ideas behind algorithmic metatheorems, especially behind some recent results concerning space and circuit classes, and tries to give a flavor of the range of their applications.
Mathematics Subject Classification ID: 68W01
Mathematics Subject Classification ID: 03B70
Mathematics Subject Classification ID: 68Q06
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 7042353
zbMATH Keywords: algorithmic metatheorems
zbMATH Keywords: Courcelle's theorem
zbMATH Keywords: tree width
zbMATH Keywords: tree depth
zbMATH Keywords: monadic second-order logic
zbMATH Keywords: logarithmic space
zbMATH Keywords: circuit classes
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.3390/a9030044
OpenAlex ID: W2475093016
cites work: Q4385531
cites work: Deciding First-Order Properties of Nowhere Dense Graphs
cites work: Deciding first-order properties of locally tree-decomposable structures
cites work: Linear time solvable optimization problems on graphs of bounded clique-width
cites work: On the presence of disjoint subgraphs of a specified type
cites work: Q3086928
cites work: Q3118384
cites work: Q3172385
cites work: Q4227581
cites work: Q4058132
cites work: A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
cites work: The complexity of first-order and monadic second-order logic revisited
cites work: Undirected connectivity in log-space
cites work: Canonizing Graphs of Bounded Tree Width in Logspace
cites work: Q3113750
cites work: Existential second-order logic over graphs
cites work: Existential Second-order Logic over Graphs: A Complete Complexity-theoretic Classification
cites work: Algorithmic meta theorems for circuit classes of constant and logarithmic depth
cites work: Counting Paths in VPA Is Complete for #NC 1
cites work: A taxonomy of problems with fast parallel algorithms
cites work: Saving space by algebraization
DOI: 10.3390/A9030044
description: scientific article; zbMATH DE number 7042353