On languages accepted with simultaneous complexity bounds and their ranking problem
From MaRDI portal
Publication:5096881
DOI10.1007/3-540-58338-6_71zbMath1493.68137OpenAlexW1538001993MaRDI QIDQ5096881
Carlo Mereghetti, Giovanni Pighizzini, Alberto Bertoni
Publication date: 18 August 2022
Published in: Mathematical Foundations of Computer Science 1994 (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/3-540-58338-6_71
Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Classical models of computation (Turing machines, etc.) (68Q04)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Effective entropies and data compression
- Random generation of combinatorial structures from a uniform distribution
- On a complexity hierarchy between L and NL
- On uniform circuit complexity
- Towards a complexity theory of synchronous parallel computation
- On eliminating nondeterminism from Turing machines which use less than logarithm worktape space
- Space bounded computations: Review and new separation results
- A very hard log-space counting class
- Formal languages and enumeration
- The complexity of computing maximal word functions
- An optimal lower bound for nonregular languages
- Algebraic languages and polyominoes enumeration
- On the Efficient Generation of Language Instances
- The complexity of ranking simple languages
- A Time Complexity Gap for Two-Way Probabilistic Finite-State Automata
- A taxonomy of problems with fast parallel algorithms
- Languages Simultaneously Complete for One-Way and Two-Way Log-Tape Automata
- Nondeterministic Computations in Sublogarithmic Space and Space Constructibility
- EFFICIENT DETECTORS AND CONSTRUCTORS FOR SIMPLE LANGUAGES
- On ranking 1-way finitely ambiguous NL languages and $\# P_1$-complete census functions
- Some Results on Tape-Bounded Turing Machines
- One-tape, off-line Turing machine computations
