Regular languages in NC
From MaRDI portal
Publication:1191027
DOI10.1016/0022-0000(92)90014-AzbMATH Open0757.68057OpenAlexW1972594149MaRDI QIDQ1191027FDOQ1191027
Authors: David A. Mix Barrington, Howard Straubing, Kevin J. Compton, Denis Thérien 
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
Recommendations
Formal languages and automata (68Q45) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Semigroups in automata theory, linguistics, etc. (20M35)
Cites Work
- \(\Sigma_ 1^ 1\)-formulae on finite structures
- On uniformity within \(NC^ 1\)
- Title not available (Why is that?)
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- Title not available (Why is that?)
- Parity, circuits, and the polynomial-time hierarchy
- Languages that Capture Complexity Classes
- Title not available (Why is that?)
- On finite monoids having only trivial subgroups
- Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
- Classifying regular events in symbolic logic
- Weak Second‐Order Arithmetic and Finite Automata
- Title not available (Why is that?)
- Families of recognizable sets corresponding to certain varieties of finite monoids
- Non-uniform automata over groups
- Unbounded fan-in circuits and associative functions
- Finite monoids and the fine structure of NC 1
- Categories as algebra: An essential ingredient in the theory of monoids
- Constant Depth Reducibility
- Title not available (Why is that?)
- The dot-depth hierarchy of star-free languages is infinite
- CONSTANT-DEPTH PERIODIC CIRCUITS
- Aperiodic homomorphisms and the concatenation product of recognizable sets
Cited In (49)
- Regular languages and partial commutations
- Extensions of an idea of McNaughton
- Some results onC-varieties
- One quantifier alternation in first-order logic with modular predicates
- Hierarchies and reducibilities on regular languages related to modulo counting
- Cost register automata for nested words
- Title not available (Why is that?)
- Title not available (Why is that?)
- Visibly counter languages and constant depth circuits
- Threshold Circuits for Iterated Matrix Product and Powering
- A constant-space sequential model of computation for first-order logic
- A constant-space sequential model of computation for first-order logic
- Difference hierarchies and duality with an application to formal languages
- Counting modulo quantifiers on finite structures
- On the complexity of algebraic numbers, and the bit-complexity of straight-line programs1
- Covering and separation for logical fragments with modular predicates
- Typed monoids -- an Eilenberg-like theorem for non regular languages
- Varieties
- Dual Space of a Lattice as the Completion of a Pervin Space
- On All Things Star-Free
- Deciding FO-rewritability of Regular Languages and Ontology-Mediated Queries in Linear Temporal Logic
- Visibly counter languages and the structure of \(\mathrm {NC}^{1}\)
- Efficient algorithms for membership in Boolean hierarchies of regular languages
- Title not available (Why is that?)
- The descriptive complexity approach to LOGCFL
- Finite semigroup varieties defined by programs
- Finite monoids and the fine structure of NC 1
- Languages polylog-time reducible to dot-depth 1/2
- Substitution Principle and semidirect products
- Alternation hierarchies of first order logic with regular predicates
- First-order expressibility of languages with neutral letters or: The Crane Beach conjecture
- Circuit Complexity of Regular Languages
- The regular languages of wire linear \(\mathrm{AC}^0\)
- Title not available (Why is that?)
- Programs over semigroups of dot-depth one
- Circuit complexity of regular languages
- Circuit complexity of regular languages
- Actions, wreath products of \(\mathcal C\)-varieties and concatenation product.
- Parallel complexity of the regular code problem
- The amazing mixed polynomial closure and its applications to two-variable first-order logic
- The regular languages of first-order logic with one alternation
- On distinguishing \(\mathbf {NC^1}\) and \(\mathbf {NL}\)
- Equational descriptions of languages
- The many faces of a translation
- A circuit complexity approach to transductions
- Recognizing Lexicographically Smallest Words and Computing Successors in Regular Languages
- Languages defined with modular counting quantifiers
- Deciding FO-definability of regular languages
- On the acceptance power of regular languages
This page was built for publication: Regular languages in \(NC\)
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1191027)
