Formulas, regular languages and Boolean circuits

DOI10.1016/0304-3975(92)90152-6zbMath0780.68085OpenAlexW1966350813MaRDI QIDQ1193413

Pierre Péladeau

Publication date: 27 September 1992

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(92)90152-6

zbMATH Keywords

regular languagesparallel complexity class

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Non-uniform automata over groups
• \(\Sigma_ 1^ 1\)-formulae on finite structures
• Classifying regular events in symbolic logic
• Logically defined subsets of \(\mathbb{N}{}^ k\)
• Semigroups, Presburger formulas, and languages
• Weak Second‐Order Arithmetic and Finite Automata
• Parity, circuits, and the polynomial-time hierarchy
• A logic for constant-depth circuits
• Languages that Capture Complexity Classes
• Finite monoids and the fine structure of NC ¹
• Complexity classes and theories of finite models
• On the Forms of the Predicates in the Theory of Constructive Ordinals

This page was built for publication: Formulas, regular languages and Boolean circuits