Extensions of an idea of McNaughton

DOI10.1007/BF02090772MaRDI QIDQ3489464zbMATH OpenFDO

Authors David A. Mix Barrington

Publication date 1990

Published in Mathematical Systems Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF02090772

zbMATH Keywords

boolean circuit complexitycombinatorial complexitycomputational complexity of a regular languagefirst orderstar free

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Formal languages and automata (68Q45)

Recommendations

• scientific article; zbMATH DE number 459361
• Circuit complexity of regular languages
• scientific article; zbMATH DE number 618821
• Regular languages in \(NC\)
• scientific article; zbMATH DE number 988809

Cites work

• \(\Sigma_ 1^ 1\)-formulae on finite structures
• A logic for constant-depth circuits
• A note on some languages in uniform \(ACC^ 0\)
• A Note on Star-Free Events
• A taxonomy of problems with fast parallel algorithms
• An application of games to the completeness problem for formalized theories
• An arithmetic model of computation equivalent to threshold circuits
• Application des γ‐operateurs au Calcul Logique du Premier Echelon
• Application of model theoretic games to discrete linear orders and finite automata
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Classifying regular events in symbolic logic
• Constant Depth Reducibility
• Expressibility and Nonuniform Complexity Classes
• Expressibility and Parallel Complexity
• First-order logic and star-free sets
• scientific article; zbMATH DE number 4012495 (Why is no real title available?)
• scientific article; zbMATH DE number 4028925 (Why is no real title available?)
• scientific article; zbMATH DE number 4076666 (Why is no real title available?)
• scientific article; zbMATH DE number 3654376 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 3474957 (Why is no real title available?)
• scientific article; zbMATH DE number 3561239 (Why is no real title available?)
• Languages that Capture Complexity Classes
• Log Depth Circuits for Division and Related Problems
• Nondeterministic Space is Closed under Complementation
• On finite monoids having only trivial subgroups
• On the relative complexity of some languages in \(NC^ 1\)
• OR Forum—Perspectives on Parallel Computing
• Parallel computation with threshold functions
• Parity, circuits, and the polynomial-time hierarchy
• Relational queries computable in polynomial time
• Simulation of Parallel Random Access Machines by Circuits
• The polynomial-time hierarchy
• Weak Second‐Order Arithmetic and Finite Automata

Cited in

(4)

• Sublinear-time language recognition and decision by one-dimensional cellular automata
• McCarthy's idea
• Sublinear-Time Language Recognition and Decision by One-Dimensional Cellular Automata
• The Boyd-Wong idea extended

This page was built for publication: Extensions of an idea of McNaughton

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3489464)