Regular languages in \(NC\)
From MaRDI portal
Publication:1191027
DOI10.1016/0022-0000(92)90014-AzbMath0757.68057OpenAlexW1972594149MaRDI QIDQ1191027
David A. Mix Barrington, Howard Straubing, Denis Thérien, Kevin J. Compton
Publication date: 27 September 1992
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0022-0000(92)90014-a
Formal languages and automata (68Q45) Semigroups in automata theory, linguistics, etc. (20M35) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
Dual Space of a Lattice as the Completion of a Pervin Space ⋮ On Distinguishing NC $$^1$$ and NL ⋮ Efficient algorithms for membership in Boolean hierarchies of regular languages ⋮ Languages polylog-time reducible to dot-depth 1/2 ⋮ The regular languages of wire linear \(\mathrm{AC}^0\) ⋮ A Circuit Complexity Approach to Transductions ⋮ Visibly Counter Languages and the Structure of $$\mathrm {NC}^{1}$$ ⋮ Alternation Hierarchies of First Order Logic with Regular Predicates ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Finite semigroup varieties defined by programs ⋮ On the complexity of algebraic numbers, and the bit-complexity of straight-line programs1 ⋮ Deciding FO-rewritability of Regular Languages and Ontology-Mediated Queries in Linear Temporal Logic ⋮ Recognizing Lexicographically Smallest Words and Computing Successors in Regular Languages ⋮ Substitution Principle and semidirect products ⋮ Deciding FO-definability of regular languages ⋮ Hierarchies and reducibilities on regular languages related to modulo counting ⋮ Circuit complexity of regular languages ⋮ A constant-space sequential model of computation for first-order logic ⋮ Typed Monoids – An Eilenberg-Like Theorem for Non Regular Languages ⋮ Circuit complexity of regular languages ⋮ EQUATIONAL DESCRIPTIONS OF LANGUAGES ⋮ Actions, wreath products of \(\mathcal C\)-varieties and concatenation product. ⋮ The descriptive complexity approach to LOGCFL ⋮ First-order expressibility of languages with neutral letters or: The Crane Beach conjecture ⋮ Some results onC-varieties ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Cost Register Automata for Nested Words ⋮ A constant-space sequential model of computation for first-order logic ⋮ On All Things Star-Free ⋮ Difference hierarchies and duality with an application to formal languages ⋮ Varieties ⋮ Programs over semigroups of dot-depth one ⋮ One quantifier alternation in first-order logic with modular predicates ⋮ Threshold Circuits for Iterated Matrix Product and Powering ⋮ Counting modulo quantifiers on finite structures ⋮ Languages defined with modular counting quantifiers ⋮ The many faces of a translation
Cites Work
- Categories as algebra: An essential ingredient in the theory of monoids
- Families of recognizable sets corresponding to certain varieties of finite monoids
- Non-uniform automata over groups
- \(\Sigma_ 1^ 1\)-formulae on finite structures
- Unbounded fan-in circuits and associative functions
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
- Classifying regular events in symbolic logic
- The dot-depth hierarchy of star-free languages is infinite
- Aperiodic homomorphisms and the concatenation product of recognizable sets
- On uniformity within \(NC^ 1\)
- Weak Second‐Order Arithmetic and Finite Automata
- Parity, circuits, and the polynomial-time hierarchy
- Constant Depth Reducibility
- Languages that Capture Complexity Classes
- Finite monoids and the fine structure of NC 1
- On finite monoids having only trivial subgroups
- CONSTANT-DEPTH PERIODIC CIRCUITS
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
