The Boolean Formula Value Problem as Formal Language

DOI10.1007/978-3-642-31644-9_9zbMath1367.68171OpenAlexW46435304MaRDI QIDQ3166948

Klaus-Joern Lange

Publication date: 1 November 2012

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-31644-9_9

zbMATH Keywords

word equationsalgebraic approachsyntactic monoid\(\mathrm{TC}^{0}\) vs \(\mathrm{NC}^{1}\)Boolean formula value problem

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Algebraic theory of languages and automata (68Q70) Semigroups in automata theory, linguistics, etc. (20M35)

Cites Work

• Unnamed Item
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Visibly pushdown languages
• Automata, Languages and Programming

This page was built for publication: The Boolean Formula Value Problem as Formal Language