On the acceptance power of regular languages
From MaRDI portal
Publication:672323
DOI10.1016/0304-3975(95)00032-RzbMath0873.68121MaRDI QIDQ672323
Publication date: 28 February 1997
Published in: Theoretical Computer Science (Search for Journal in Brave)
Formal languages and automata (68Q45) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
UNIFORM CHARACTERIZATIONS OF COMPLEXITY CLASSES OF FUNCTIONS, Relating Automata-theoretic Hierarchies to Complexity-theoretic Hierarchies, Languages polylog-time reducible to dot-depth 1/2, Perfect correspondences between dot-depth and polynomial-time hierarchies, 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, On Existentially First-Order Definable Languages and Their Relation to NP
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The method of forced enumeration for nondeterministic automata
- Probabilistic quantifiers and games
- Classifying regular events in symbolic logic
- A uniform approach to define complexity classes
- The polynomial-time hierarchy
- Complete sets and the polynomial-time hierarchy
- Logspace and logtime leaf languages
- Complexity classes and sparse oracles
- On the computational power of pushdown automata
- Locally testable languages
- Characterizations of locally testable events
- Relativized counting classes: Relations among thresholds, parity, and mods
- PP is as Hard as the Polynomial-Time Hierarchy
- Nondeterministic Space is Closed under Complementation
- Counting Classes are at Least as Hard as the Polynomial-Time Hierarchy
- Structure and importance of logspace-MOD class
- On the Structure of Polynomial Time Reducibility
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
- Complexity classes defined by counting quantifiers
- Lower Bound of the Number of Threshold Functions
- The Theory of Definite Automata
- A logical calculus of the ideas immanent in nervous activity
- Counting classes: Thresholds, parity, mods, and fewness
