\(NC^ 1\): The automata-theoretic viewpoint

DOI10.1007/BF01212963zbMath0774.68048MaRDI 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

zbMATH Keywords

automata; variety; circuit; monoids

Mathematics Subject Classification ID

68Q70: Algebraic theory of languages and automata

20M35: Semigroups in automata theory, linguistics, etc.

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

Related Items

MONOIDS AND COMPUTATIONS, Unnamed Item, Unnamed Item, Lower bounds for modular counting by circuits with modular gates, The Power of Diversity, The Power of Programs over Monoids in DA, The descriptive complexity approach to LOGCFL, Descriptional and computational complexity of finite automata -- a survey, Extensions to Barrington's M-program model, Languages recognized by finite aperiodic groupoids, Nondeterministic \(NC^1\) computation, Functions with bounded symmetric communication complexity, programs over commutative monoids, and ACC, Representing Boolean functions as polynomials modulo composite numbers, Finite semigroup varieties defined by programs, Programs over semigroups of dot-depth one, On the computational power of programs over \(\mathsf{BA}_2\) monoid, A topological approach to non-uniform complexity, Cost Register Automata for Nested Words, Descriptional and Computational Complexity of Finite Automata

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 ¹
• 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