Finite monoids and the fine structure of NC 1
From MaRDI portal
Publication:3820014
DOI10.1145/48014.63138zbMath0667.68068OpenAlexW2010465749WikidataQ29011821 ScholiaQ29011821MaRDI QIDQ3820014
David A. Mix Barrington, Denis Thérien
Publication date: 1988
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/48014.63138
Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Algebraic theory of languages and automata (68Q70) Semigroups in automata theory, linguistics, etc. (20M35)
Related Items (56)
Inapproximability results for equations over finite groups ⋮ On ACC ⋮ Representing Boolean functions as polynomials modulo composite numbers ⋮ Polynomial time machines equipped with word problems over algebraic structures as their acceptance criteria ⋮ A note on a theorem of Barrington, Straubing and Thérien ⋮ Boolean circuits versus arithmetic circuits ⋮ On uniformity within \(NC^ 1\) ⋮ The complexity of intersecting finite automata having few final states ⋮ Finite loops recognize exactly the regular open languages ⋮ Skew circuits of small width ⋮ Comments on ``Arithmetic complexity, Kleene closure, and formal power series ⋮ On the relative complexity of some languages in \(NC^ 1\) ⋮ Visibly Counter Languages and the Structure of $$\mathrm {NC}^{1}$$ ⋮ Finite semigroup varieties defined by programs ⋮ Deciding FO-rewritability of Regular Languages and Ontology-Mediated Queries in Linear Temporal Logic ⋮ A note on uniform circuit lower bounds for the counting hierarchy (extended abstract) ⋮ Probabilism versus Alternation for Automata ⋮ Recognizing Lexicographically Smallest Words and Computing Successors in Regular Languages ⋮ Two-way automata and length-preserving homomorphisms ⋮ Circuit complexity of regular languages ⋮ On the computational power of programs over \(\mathsf{BA}_2\) monoid ⋮ Oracle branching programs and Logspace versus \(P^*\) ⋮ Logically defined subsets of \(\mathbb{N}{}^ k\) ⋮ Learning Read-Constant Polynomials of Constant Degree Modulo Composites ⋮ Regular languages in \(NC\) ⋮ Formulas, regular languages and Boolean circuits ⋮ Evaluation of circuits over nilpotent and polycyclic groups ⋮ \(NC^ 1\): The automata-theoretic viewpoint ⋮ On a conjecture concerning dot-depth two languages ⋮ Learning read-constant polynomials of constant degree modulo composites ⋮ MONOIDS AND COMPUTATIONS ⋮ Circuit complexity of regular languages ⋮ Some results on the dot-depth hierarchy ⋮ Extensions to Barrington's M-program model ⋮ Space Complexity of Reachability Testing in Labelled Graphs ⋮ Learning expressions and programs over monoids ⋮ Descriptional and computational complexity of finite automata -- a survey ⋮ The descriptive complexity approach to LOGCFL ⋮ Unnamed Item ⋮ The algebraic theory of Parikh automata ⋮ The Power of Diversity ⋮ Unnamed Item ⋮ Circuit complexity and the expressive power of generalized first-order formulas ⋮ Descriptional and Computational Complexity of Finite Automata ⋮ Unnamed Item ⋮ Nondeterministic \(NC^1\) computation ⋮ On \(\text{TC}^0,\text{AC}^0\), and arithmetic circuits ⋮ Space complexity of reachability testing in labelled graphs ⋮ Programs over semigroups of dot-depth one ⋮ An impossibility gap between width-4 and width-5 permutation branching programs ⋮ The Power of Programs over Monoids in DA ⋮ An ergodic theorem for read-once non-uniform deterministic finite automata ⋮ Languages defined with modular counting quantifiers ⋮ On the computational power of probabilistic and quantum branching program ⋮ Non-uniform automata over groups ⋮ On learning embedded midbit functions
This page was built for publication: Finite monoids and the fine structure of NC 1
