The complexity of ranking simple languages
From MaRDI portal
Recommendations
- On ranking 1-way finitely ambiguous NL languages and $\# P_1$-complete census functions
- Rational transductions and complexity of counting problems
- Ranking and formal power series
- On languages accepted with simultaneous complexity bounds and their ranking problem
- Ranking and unranking left szilard languages
Cites work
- scientific article; zbMATH DE number 4033108 (Why is no real title available?)
- scientific article; zbMATH DE number 3664335 (Why is no real title available?)
- scientific article; zbMATH DE number 3560742 (Why is no real title available?)
- scientific article; zbMATH DE number 3302285 (Why is no real title available?)
- k + 1 Heads Are Better than k
- A taxonomy of problems with fast parallel algorithms
- Alternation
- Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
- Finite-Turn Pushdown Automata
- On pebble automata
- On uniform circuit complexity
- Parallelism in random access machines
- Path Systems: Constructions, Solutions and Applications
- Simulation of Parallel Random Access Machines by Circuits
- The complexity of computing the permanent
- Tree-size bounded alternation
Cited in
(20)- Non-commutative arithmetic circuits: depth reduction and size lower bounds
- On the complexity of ranking
- The complexity of computing maximal word functions
- Polynomial-time compression
- A very hard log-space counting class
- Closure and nonclosure properties of the classes of compressible and rankable sets
- On ranking 1-way finitely ambiguous NL languages and $\# P_1$-complete census functions
- Bounded length UCFG equivalence
- How hard is to compute the edit distance
- Ranking and unranking left szilard languages
- Computing a context-free grammar-generating series
- How hard is computing the edit distance?
- On sets polynomially enumerable by iteration
- Recursion-theoretic ranking and compression
- CONSTRUCTING LANGUAGE INSTANCES BASED ON PARTIAL INFORMATION
- scientific article; zbMATH DE number 1869614 (Why is no real title available?)
- Rational transductions and complexity of counting problems
- 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
This page was built for publication: The complexity of ranking simple languages
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3034844)
