NC^ 1: The automata-theoretic viewpoint
From MaRDI portal
Publication:685708
DOI10.1007/BF01212963zbMATH Open0774.68048OpenAlexW2045171534MaRDI QIDQ685708FDOQ685708
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
Recommendations
Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Algebraic theory of languages and automata (68Q70) Semigroups in automata theory, linguistics, etc. (20M35)
Cites Work
- Title not available (Why is that?)
- \(\Sigma_ 1^ 1\)-formulae on finite structures
- On uniformity within \(NC^ 1\)
- A taxonomy of problems with fast parallel algorithms
- Characterizations of locally testable events
- Parity, circuits, and the polynomial-time hierarchy
- 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\)
- Bounds for Width Two Branching Programs
- Non-uniform automata over groups
- Classification of finite monoids: the language approach
- Finite monoids and the fine structure of NC 1
- Locally trivial categories and unambiguous concatenation
- Algebraic Theory of Machines. I. Prime Decomposition Theorem for Finite Semigroups and Machines
- Sur le produit avec compteur modulo un nombre premier
- Inverse semigroups and varieties of finite semigroups
- Algebraic decision procedures for local testability
- Languages of R-trivial monoids
- The dot-depth hierarchy of star-free languages is infinite
- Relativized Polynomial Time Hierarchies Having Exactly K Levels
- CONSTANT-DEPTH PERIODIC CIRCUITS
- The NP-completeness column: An ongoing guide
Cited In (27)
- Title not available (Why is that?)
- Circuit complexity before the dawn of the new millennium
- Title not available (Why is that?)
- On the computational power of programs over \(\mathsf{BA}_2\) monoid
- Nondeterministic \(NC^1\) computation
- Cost Register Automata for Nested Words
- The descriptive complexity approach to LOGCFL
- Finite semigroup varieties defined by programs
- Finite monoids and the fine structure of NC 1
- Representing Boolean functions as polynomials modulo composite numbers
- Descriptional and Computational Complexity of Finite Automata
- Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
- Title not available (Why is that?)
- Functions with bounded symmetric communication complexity, programs over commutative monoids, and ACC
- 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
- MONOIDS AND COMPUTATIONS
- Descriptional and computational complexity of finite automata -- a survey
- The Power of Programs over Monoids in DA
- Languages recognized by finite aperiodic groupoids
- Title not available (Why is that?)
- Separating NC along the \(\delta\) axis
- The Power of Diversity
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)
