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)

zbMATH Keywords

combinatorial complexityfirst orderboolean circuit complexitycomputational complexity of a regular languagestar free

Mathematics Subject Classification ID

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

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

• 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?)
• A Note on Star-Free Events
• A logic for constant-depth circuits
• A note on some languages in uniform \(ACC^ 0\)
• 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
• Languages that Capture Complexity Classes
• Log Depth Circuits for Division and Related Problems
• Nondeterministic Space is Closed under Complementation
• OR Forum—Perspectives on Parallel Computing
• On finite monoids having only trivial subgroups
• On the relative complexity of some languages in \(NC^ 1\)
• 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
• \(\Sigma_ 1^ 1\)-formulae on finite structures

Cited in

(4)

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

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)