The regular languages of first-order logic with one alternation
From MaRDI portal
Publication:6649495
DOI10.1145/3531130.3533371MaRDI QIDQ6649495
Thomas Zeume, Charles Paperman, Michaël Cadilhac, Corentin Barloy
Publication date: 6 December 2024
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Categories as algebra: An essential ingredient in the theory of monoids
- Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
- Regular languages in \(NC\)
- Polynomial closure and unambiguous product
- Programs over semigroups of dot-depth one
- First-order expressibility of languages with neutral letters or: The Crane Beach conjecture
- Languages defined with modular counting quantifiers
- Top-down lower bounds for depth-three circuits
- The regular languages of wire linear \(\mathrm{AC}^0\)
- Finite semigroup varieties of the form V*D
- Threshold circuits of bounded depth
- Extremal Combinatorics
- Parity, circuits, and the polynomial-time hierarchy
- Bounded-depth circuits
- Factorization Forests
- Finite monoids and the fine structure of NC 1
- Circuit Bottom Fan-in and Computational Power
- Separating regular languages with two quantifier alternations
- The Dot-Depth Hierarchy, 45 Years Later
- A SYNTACTICAL PROOF OF LOCALITY OF DA
- The Power of Programs over Monoids in DA
- Going Higher in First-Order Quantifier Alternation Hierarchies on Words
- A new proof of the locality of R
- CONSTANT-DEPTH PERIODIC CIRCUITS
- Circuit complexity of regular languages
This page was built for publication: The regular languages of first-order logic with one alternation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6649495)
