Circuit complexity of regular languages
From MaRDI portal
Publication:5918477
DOI10.4171/Automata-1/14MaRDI QIDQ5918477
Publication date: 4 February 2022
Published in: Handbook of Automata Theory (Search for Journal in Brave)
Formal languages and automata (68Q45) Algebraic theory of languages and automata (68Q70) Networks and circuits as models of computation; circuit complexity (68Q06)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Families of recognizable sets corresponding to certain varieties of finite monoids
- \(\Sigma_ 1^ 1\)-formulae on finite structures
- Unbounded fan-in circuits and associative functions
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
- A generalization of the Schützenberger product of finite monoids
- On uniform circuit complexity
- Classification of finite monoids: the language approach
- Regular languages in \(NC\)
- The dot-depth hierarchy of star-free languages is infinite
- Regular languages defined with generalized quantifiers
- Finite semigroup varieties of the form V*D
- On uniformity within \(NC^ 1\)
- Parity, circuits, and the polynomial-time hierarchy
- Finite monoids and the fine structure of NC 1
- Branching Programs and Binary Decision Diagrams
- CONSTANT-DEPTH PERIODIC CIRCUITS
- Circuit complexity of regular languages
This page was built for publication: Circuit complexity of regular languages
