On languages accepted with simultaneous complexity bounds and their ranking problem
From MaRDI portal
Recommendations
- The complexity of ranking simple languages
- On ranking 1-way finitely ambiguous NL languages and $\# P_1$-complete census functions
- scientific article; zbMATH DE number 18635
- Strong optimal lower bounds for Turing machines that accept nonregular languages
- Lower bounds for language recognition on two-dimensional alternating multihead machines
Cites work
- A taxonomy of problems with fast parallel algorithms
- A Time Complexity Gap for Two-Way Probabilistic Finite-State Automata
- A very hard log-space counting class
- Algebraic languages and polyominoes enumeration
- An optimal lower bound for nonregular languages
- Effective entropies and data compression
- EFFICIENT DETECTORS AND CONSTRUCTORS FOR SIMPLE LANGUAGES
- Formal languages and enumeration
- scientific article; zbMATH DE number 3664335 (Why is no real title available?)
- scientific article; zbMATH DE number 1142306 (Why is no real title available?)
- scientific article; zbMATH DE number 4187112 (Why is no real title available?)
- Languages Simultaneously Complete for One-Way and Two-Way Log-Tape Automata
- Nondeterministic Computations in Sublogarithmic Space and Space Constructibility
- On a complexity hierarchy between L and NL
- On eliminating nondeterminism from Turing machines which use less than logarithm worktape space
- On ranking 1-way finitely ambiguous NL languages and $\# P_1$-complete census functions
- On the Efficient Generation of Language Instances
- On uniform circuit complexity
- One-tape, off-line Turing machine computations
- Random generation of combinatorial structures from a uniform distribution
- Some Results on Tape-Bounded Turing Machines
- Space bounded computations: Review and new separation results
- The complexity of computing maximal word functions
- The complexity of ranking simple languages
- Towards a complexity theory of synchronous parallel computation
Cited in
(5)- The complexity of ranking simple languages
- Alternating space is closed under complement and other simulations for sublogarithmic space
- SOME DECISION QUESTIONS CONCERNING THE TIME COMPLEXITY OF LANGUAGE ACCEPTORS
- On ranking 1-way finitely ambiguous NL languages and $\# P_1$-complete census functions
- Some Decision Questions Concerning the Time Complexity of Language Acceptors
This page was built for publication: On languages accepted with simultaneous complexity bounds and their ranking problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5096881)
