The complexity of ranking simple languages
From MaRDI portal
DOI10.1007/BF02090763zbMATH Open0692.68059MaRDI QIDQ3034844FDOQ3034844
Authors: Dung T. Huynh 
Publication date: 1990
Published in: Mathematical Systems Theory (Search for Journal in Brave)
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
Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Turing machines and related notions (03D10)
Cites Work
- Title not available (Why is that?)
- The complexity of computing the permanent
- On uniform circuit complexity
- A taxonomy of problems with fast parallel algorithms
- Alternation
- Simulation of Parallel Random Access Machines by Circuits
- Parallelism in random access machines
- Finite-Turn Pushdown Automata
- Title not available (Why is that?)
- Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
- k + 1 Heads Are Better than k
- Title not available (Why is that?)
- Tree-size bounded alternation
- Title not available (Why is that?)
- On pebble automata
- Path Systems: Constructions, Solutions and Applications
Cited In (20)
- Computing a context-free grammar-generating series
- CONSTRUCTING LANGUAGE INSTANCES BASED ON PARTIAL INFORMATION
- A very hard log-space counting class
- Polynomial-time compression
- Parallel recognition and ranking of context-free languages
- The complexity of computing maximal word functions
- Closure and nonclosure properties of the classes of compressible and rankable sets
- How hard is computing the edit distance?
- Non-commutative arithmetic circuits: depth reduction and size lower bounds
- Ranking and unranking left szilard languages
- On sets polynomially enumerable by iteration
- On the complexity of ranking
- Title not available (Why is that?)
- How hard is to compute the edit distance
- Rational transductions and complexity of counting problems
- Rational transductions and complexity of counting problems
- On languages accepted with simultaneous complexity bounds and their ranking problem
- Bounded length UCFG equivalence
- Recursion-theoretic ranking and compression
- On ranking 1-way finitely ambiguous NL languages and $\# P_1$-complete census functions
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)
