Boolean language operations on nondeterministic automata with a pushdown of constant height
From MaRDI portal
Publication:2403237
Recommendations
- Boolean language operations on nondeterministic automata with a pushdown of constant height
- The size-cost of Boolean operations on constant height deterministic pushdown automata
- The size-cost of Boolean operations on constant height deterministic pushdown automata
- Height-Deterministic Pushdown Automata
- Removing nondeterminism in constant height pushdown automata
Cites work
- Behaviours of unary quantum automata
- Boolean language operations on nondeterministic automata with a pushdown of constant height
- Complexity measures for regular expressions
- Complexity of promise problems on classical and quantum automata
- Descriptional complexity -- an introductory survey
- Descriptional complexity of two-way pushdown automata with restricted head reversals
- Deterministic input-driven queue automata: finite turns, decidability, and closure properties
- GOLOMB RULERS AND DIFFERENCE SETS FOR SUCCINCT QUANTUM AUTOMATA
- scientific article; zbMATH DE number 3568031 (Why is no real title available?)
- scientific article; zbMATH DE number 3639163 (Why is no real title available?)
- scientific article; zbMATH DE number 1517989 (Why is no real title available?)
- scientific article; zbMATH DE number 941396 (Why is no real title available?)
- scientific article; zbMATH DE number 3254905 (Why is no real title available?)
- Language operations with regular expressions of polynomial size
- Lower bounds on the size of sweeping automata
- Mathematical Foundations of Computer Science 2005
- More concise representation of regular languages by automata and regular expressions
- Nondeterminism and the size of two way finite automata
- On the size of unary probabilistic and nondeterministic automata
- Positional simulation of two-way automata: Proof of a conjecture of R. Kannan and generalizations
- Queue automata of constant length
- Removing nondeterminism in constant height pushdown automata
- Size complexity of rotating and sweeping automata
- Syllabic languages and go-through automata
- The Boolean closure of linear context-free languages
- The size-cost of Boolean operations on constant height deterministic pushdown automata
- The state complexities of some basic operations on regular languages
- Two double-exponential gaps for automata with a limited pushdown
- Two-way unary automata versus logarithmic space
- UNARY LANGUAGE OPERATIONS, STATE COMPLEXITY AND JACOBSTHAL'S FUNCTION
Cited in
(11)- The descriptional power of queue automata of constant length
- Deterministic and nondeterministic iterated uniform finite-state transducers: computational and descriptional power
- Removing nondeterminism in constant height pushdown automata
- The size-cost of Boolean operations on constant height deterministic pushdown automata
- Boolean language operations on nondeterministic automata with a pushdown of constant height
- Computational and Descriptional Power of Nondeterministic Iterated Uniform Finite-State Transducers*
- The size-cost of Boolean operations on constant height deterministic pushdown automata
- Pushdown automata and constant height: decidability and bounds
- Latvian quantum finite state automata for unary languages
- Latvian quantum finite state automata for unary languages
- Deterministic pushdown automata with translucent input letters
This page was built for publication: Boolean language operations on nondeterministic automata with a pushdown of constant height
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2403237)
