\(NC^ 1\): The automata-theoretic viewpoint
From MaRDI portal
Publication:685708
DOI10.1007/BF01212963zbMath0774.68048OpenAlexW2045171534MaRDI QIDQ685708
Denis Thérien, Pierre McKenzie, Pierre Péladeau
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
Algebraic theory of languages and automata (68Q70) Semigroups in automata theory, linguistics, etc. (20M35) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (19)
Representing Boolean functions as polynomials modulo composite numbers ⋮ Finite semigroup varieties defined by programs ⋮ On the computational power of programs over \(\mathsf{BA}_2\) monoid ⋮ MONOIDS AND COMPUTATIONS ⋮ Extensions to Barrington's M-program model ⋮ Descriptional and computational complexity of finite automata -- a survey ⋮ The descriptive complexity approach to LOGCFL ⋮ Unnamed Item ⋮ A topological approach to non-uniform complexity ⋮ The Power of Diversity ⋮ Unnamed Item ⋮ Descriptional and Computational Complexity of Finite Automata ⋮ Cost Register Automata for Nested Words ⋮ Languages recognized by finite aperiodic groupoids ⋮ Nondeterministic \(NC^1\) computation ⋮ Lower bounds for modular counting by circuits with modular gates ⋮ Programs over semigroups of dot-depth one ⋮ The Power of Programs over Monoids in DA ⋮ Functions with bounded symmetric communication complexity, programs over commutative monoids, and ACC
Cites Work
- Unnamed Item
- Inverse semigroups and varieties of finite semigroups
- Non-uniform automata over groups
- \(\Sigma_ 1^ 1\)-formulae on finite structures
- Locally trivial categories and unambiguous concatenation
- Parallel computation with threshold functions
- Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
- Languages of R-trivial monoids
- Classification of finite monoids: the language approach
- The dot-depth hierarchy of star-free languages is infinite
- Characterizations of locally testable events
- On uniformity within \(NC^ 1\)
- Parity, circuits, and the polynomial-time hierarchy
- A taxonomy of problems with fast parallel algorithms
- Bounds for Width Two Branching Programs
- Finite monoids and the fine structure of NC 1
- Sur le produit avec compteur modulo un nombre premier
- Relativized Polynomial Time Hierarchies Having Exactly K Levels
- Algebraic decision procedures for local testability
- On finite monoids having only trivial subgroups
- Algebraic Theory of Machines. I. Prime Decomposition Theorem for Finite Semigroups and Machines
- CONSTANT-DEPTH PERIODIC CIRCUITS
- The NP-completeness column: An ongoing guide
This page was built for publication: \(NC^ 1\): The automata-theoretic viewpoint
