NC^ 1: The automata-theoretic viewpoint

DOI10.1007/BF01212963MaRDI QIDQ685708zbMATH OpenOpenAlexFDO

Authors Pierre McKenzie, Pierre Péladeau, Denis Thérien

Publication date 10 October 1993

Published in Computational Complexity (Search for Journal in Brave)

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

zbMATH Keywords

automatacircuitvarietymonoids

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Algebraic theory of languages and automata (68Q70) Semigroups in automata theory, linguistics, etc. (20M35)

Recommendations

• Finite monoids and the fine structure of NC ¹
• scientific article; zbMATH DE number 4117877
• Some classes of languages in \(NC^ 1\)
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• On uniformity within \(NC^ 1\)

Cites work

• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• A taxonomy of problems with fast parallel algorithms
• Algebraic Theory of Machines. I. Prime Decomposition Theorem for Finite Semigroups and Machines
• Algebraic decision procedures for local testability
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Bounds for Width Two Branching Programs
• CONSTANT-DEPTH PERIODIC CIRCUITS
• Characterizations of locally testable events
• Classification of finite monoids: the language approach
• Finite monoids and the fine structure of NC ¹
• Inverse semigroups and varieties of finite semigroups
• Languages of R-trivial monoids
• Locally trivial categories and unambiguous concatenation
• Non-uniform automata over groups
• On finite monoids having only trivial subgroups
• On uniformity within \(NC^ 1\)
• Parallel computation with threshold functions
• Parity, circuits, and the polynomial-time hierarchy
• Relativized Polynomial Time Hierarchies Having Exactly K Levels
• Sur le produit avec compteur modulo un nombre premier
• The NP-completeness column: An ongoing guide
• The dot-depth hierarchy of star-free languages is infinite
• \(\Sigma_ 1^ 1\)-formulae on finite structures

Cited in

(29)

• scientific article; zbMATH DE number 7566068 (Why is no real title available?)
• Circuit complexity before the dawn of the new millennium
• Cost register automata for nested words
• scientific article; zbMATH DE number 7577578 (Why is no real title available?)
• The power of programs over monoids in DA
• On the computational power of programs over \(\mathsf{BA}_2\) monoid
• Nondeterministic NC^1 computation
• The power of diversity
• Noncommutative arithmetic circuits meet finite automata
• Finite semigroup varieties defined by programs
• Representing Boolean functions as polynomials modulo composite numbers
• The descriptive complexity approach to LOGCFL
• Finite monoids and the fine structure of NC ¹
• Descriptional and Computational Complexity of Finite Automata
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Functions with bounded symmetric communication complexity, programs over commutative monoids, and ACC
• scientific article; zbMATH DE number 4080911 (Why is no real title available?)
• Some classes of languages in \(NC^ 1\)
• Extensions to Barrington's M-program model
• On uniformity within \(NC^ 1\)
• A topological approach to non-uniform complexity
• Programs over semigroups of dot-depth one
• Lower bounds for modular counting by circuits with modular gates
• Descriptional and computational complexity of finite automata -- a survey
• MONOIDS AND COMPUTATIONS
• Languages recognized by finite aperiodic groupoids
• scientific article; zbMATH DE number 4117877 (Why is no real title available?)
• The algebraic theory of Parikh automata
• Separating NC along the \(\delta\) axis

This page was built for publication: \(NC^ 1\): The automata-theoretic viewpoint

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