Regular languages in NC
From MaRDI portal
Recommendations
Cites work
- scientific article; zbMATH DE number 4028925 (Why is no real title available?)
- scientific article; zbMATH DE number 4076666 (Why is no real title available?)
- scientific article; zbMATH DE number 3654376 (Why is no real title available?)
- scientific article; zbMATH DE number 3561239 (Why is no real title available?)
- scientific article; zbMATH DE number 3368555 (Why is no real title available?)
- Aperiodic homomorphisms and the concatenation product of recognizable sets
- Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
- CONSTANT-DEPTH PERIODIC CIRCUITS
- Categories as algebra: An essential ingredient in the theory of monoids
- Classifying regular events in symbolic logic
- Constant Depth Reducibility
- Families of recognizable sets corresponding to certain varieties of finite monoids
- Finite monoids and the fine structure of NC 1
- Languages that Capture Complexity Classes
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- Non-uniform automata over groups
- On finite monoids having only trivial subgroups
- On uniformity within \(NC^ 1\)
- Parity, circuits, and the polynomial-time hierarchy
- The dot-depth hierarchy of star-free languages is infinite
- Unbounded fan-in circuits and associative functions
- Weak Second‐Order Arithmetic and Finite Automata
- \(\Sigma_ 1^ 1\)-formulae on finite structures
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
- scientific article; zbMATH DE number 2051829 (Why is no real title available?)
- scientific article; zbMATH DE number 7577578 (Why is no real title available?)
- 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
- Typed monoids -- an Eilenberg-like theorem for non regular languages
- Covering and separation for logical fragments with modular predicates
- Varieties
- Dual Space of a Lattice as the Completion of a Pervin Space
- Visibly counter languages and the structure of \(\mathrm {NC}^{1}\)
- Efficient algorithms for membership in Boolean hierarchies of regular languages
- On All Things Star-Free
- Deciding FO-rewritability of Regular Languages and Ontology-Mediated Queries in Linear Temporal Logic
- scientific article; zbMATH DE number 611232 (Why is no real title available?)
- Finite semigroup varieties defined by programs
- The descriptive complexity approach to LOGCFL
- Finite monoids and the fine structure of NC 1
- Languages polylog-time reducible to dot-depth 1/2
- Alternation hierarchies of first order logic with regular predicates
- Substitution Principle and semidirect products
- 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\)
- Programs over semigroups of dot-depth one
- scientific article; zbMATH DE number 2051828 (Why is no real title available?)
- Circuit complexity of regular languages
- Circuit complexity of regular languages
- Parallel complexity of the regular code problem
- Actions, wreath products of \(\mathcal C\)-varieties and concatenation product.
- 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
- On the acceptance power of regular languages
- Languages defined with modular counting quantifiers
- Deciding FO-definability of regular languages
- Recognizing Lexicographically Smallest Words and Computing Successors in 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)
