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

DOI10.1007/BF01212963zbMath0774.68048MaRDI QIDQ685708

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

Publication date: 10 October 1993

Published in: Computational Complexity (Search for Journal in Brave)

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, The Power of Diversity, 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, 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