The complexity of ranking simple languages
From MaRDI portal
Publication:3034844
DOI10.1007/BF02090763zbMath0692.68059MaRDI QIDQ3034844
Publication date: 1990
Published in: Mathematical Systems Theory (Search for Journal in Brave)
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (16)
On ranking 1-way finitely ambiguous NL languages and $\# P_1$-complete census functions ⋮ How hard is to compute the edit distance ⋮ Rational transductions and complexity of counting problems ⋮ Parallel recognition and ranking of context-free languages ⋮ On languages accepted with simultaneous complexity bounds and their ranking problem ⋮ Rational transductions and complexity of counting problems ⋮ Recursion-theoretic ranking and compression ⋮ On sets polynomially enumerable by iteration ⋮ Polynomial-time compression ⋮ Ranking and unranking left szilard languages ⋮ A very hard log-space counting class ⋮ Closure and nonclosure properties of the classes of compressible and rankable sets ⋮ Non-commutative arithmetic circuits: depth reduction and size lower bounds ⋮ How hard is computing the edit distance? ⋮ Computing a context-free grammar-generating series ⋮ The complexity of computing maximal word functions
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The complexity of computing the permanent
- On pebble automata
- Tree-size bounded alternation
- On uniform circuit complexity
- Simulation of Parallel Random Access Machines by Circuits
- A taxonomy of problems with fast parallel algorithms
- Path Systems: Constructions, Solutions and Applications
- Alternation
- k + 1 Heads Are Better than k
- Parallelism in random access machines
- Finite-Turn Pushdown Automata
- Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
This page was built for publication: The complexity of ranking simple languages
