Extensions of an idea of McNaughton

DOI10.1007/BF02090772zbMATH Open0707.68051MaRDI QIDQ3489464FDOQ3489464

Authors: David A. Mix Barrington 

Publication date: 1990

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

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

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)

Cites Work

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

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)