Languages polylog-time reducible to dot-depth 1/2
From MaRDI portal
Publication:859980
DOI10.1016/j.jcss.2006.09.004zbMath1178.68315OpenAlexW2114279245MaRDI QIDQ859980
Publication date: 22 January 2007
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jcss.2006.09.004
Related Items (4)
Efficient algorithms for membership in Boolean hierarchies of regular languages ⋮ Hierarchies and reducibilities on regular languages related to modulo counting ⋮ Fine hierarchies and m-reducibilities in theoretical computer science ⋮ Machines that can output empty words
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the acceptance power of regular languages
- First-order logic and star-free sets
- Unambiguous computations and locally definable acceptance types
- Polynomial operations and hierarchies of concatenation
- Regular languages in \(NC\)
- A uniform approach to define complexity classes
- The dot-depth hierarchy of star-free languages is infinite
- Gap-definable counting classes
- Polynomial closure and unambiguous product
- Finite semigroup varieties defined by programs
- Programs over semigroups of dot-depth one
- Eilenberg's theorem for positive varieties of languages
- Finite semigroup varieties of the form V*D
- A complexity theory for feasible closure properties
- Dot-depth of star-free events
- A reducibility for the dot-depth hierarchy
- On the unique satisfiability problem
- An application of the Ehrenfeucht-Fraisse game in formal language theory
- Simultaneous strong separations of probabilistic and unambiguous complexity classes
- RELATIVIZABLE AND NONRELATIVIZABLE THEOREMS IN THE POLYNOMIAL THEORY OF ALGORITHMS
- Threshold Computation and Cryptographic Security
- Some results onC-varieties
- On Existentially First-Order Definable Languages and Their Relation to NP
- THE WREATH PRODUCT PRINCIPLE FOR ORDERED SEMIGROUPS
- LINDSTRÖM QUANTIFIERS AND LEAF LANGUAGE DEFINABILITY
- On finite monoids having only trivial subgroups
- Fundamentals of Computation Theory
This page was built for publication: Languages polylog-time reducible to dot-depth 1/2
