A Language-Theoretical Approach to Descriptive Complexity

DOI10.1007/978-3-662-53132-7_6zbMath1436.68130OpenAlexW2493682561MaRDI QIDQ2817376

Michaël Cadilhac, Andreas Krebs, Klaus-Joern Lange

Publication date: 30 August 2016

Published in: Developments in Language Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-662-53132-7_6

zbMATH Keywords

circuitsformal languageslogicdescriptive complexityhyperwords

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Descriptive complexity and finite models (68Q19) Switching theory, applications of Boolean algebras to circuits and networks (94C11)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Nesting until and since in linear temporal logic
• On uniformity within \(NC^ 1\)
• Characterizing \(\text{TC}^{0}\) in terms of infinite groups
• Linear Circuits, Two-Variable Logic and Weakly Blocked Monoids
• Regular Languages Definable by Majority Quantifiers with Two Variables
• Expressibility and Parallel Complexity
• The descriptive complexity approach to LOGCFL

This page was built for publication: A Language-Theoretical Approach to Descriptive Complexity