Extensions of an idea of McNaughton
From MaRDI portal
Publication:3489464
DOI10.1007/BF02090772zbMath0707.68051MaRDI QIDQ3489464
Publication date: 1990
Published in: Mathematical Systems Theory (Search for Journal in Brave)
combinatorial complexityfirst orderboolean circuit complexitycomputational complexity of a regular languagestar free
Formal languages and automata (68Q45) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
Sublinear-Time Language Recognition and Decision by One-Dimensional Cellular Automata, Sublinear-Time Language Recognition and Decision by One-Dimensional Cellular Automata
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- \(\Sigma_ 1^ 1\)-formulae on finite structures
- First-order logic and star-free sets
- Parallel computation with threshold functions
- Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
- On the relative complexity of some languages in \(NC^ 1\)
- Classifying regular events in symbolic logic
- An arithmetic model of computation equivalent to threshold circuits
- The polynomial-time hierarchy
- A note on some languages in uniform \(ACC^ 0\)
- An application of games to the completeness problem for formalized theories
- Weak Second‐Order Arithmetic and Finite Automata
- Simulation of Parallel Random Access Machines by Circuits
- Parity, circuits, and the polynomial-time hierarchy
- Constant Depth Reducibility
- Expressibility and Nonuniform Complexity Classes
- A taxonomy of problems with fast parallel algorithms
- A logic for constant-depth circuits
- Relational queries computable in polynomial time
- Log Depth Circuits for Division and Related Problems
- Languages that Capture Complexity Classes
- Nondeterministic Space is Closed under Complementation
- Application of model theoretic games to discrete linear orders and finite automata
- OR Forum—Perspectives on Parallel Computing
- Expressibility and Parallel Complexity
- Application des γ‐operateurs au Calcul Logique du Premier Echelon
- On finite monoids having only trivial subgroups
- A Note on Star-Free Events
