A gentle introduction to applications of algorithmic metatheorems for space and circuit classes
From MaRDI portal
Publication:1736808
DOI10.3390/a9030044zbMath1461.68249MaRDI QIDQ1736808
Publication date: 26 March 2019
Published in: Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.3390/a9030044
monadic second-order logic; tree width; logarithmic space; algorithmic metatheorems; Courcelle's theorem; tree depth; circuit classes
68Q25: Analysis of algorithms and problem complexity
03B70: Logic in computer science
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
68W01: General topics in the theory of algorithms
68Q06: Networks and circuits as models of computation; circuit complexity
