On languages accepted with simultaneous complexity bounds and their ranking problem (Q5096881): Difference between revisions

@@ Property / author @@
+Alberto Bertoni
@@ Property / author: Alberto Bertoni / rank @@
+Normal rank
@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1007/3-540-58338-6_71
+Normal rank
@@ Property / OpenAlex ID @@
+W1538001993
@@ Property / OpenAlex ID: W1538001993 / rank @@
+Normal rank
@@ Property / cites work @@
+The complexity of computing maximal word functions
+Normal rank
@@ Property / cites work @@
+A very hard log-space counting class
@@ Property / cites work: A very hard log-space counting class / rank @@
+Normal rank
@@ Property / cites work @@
+On ranking 1-way finitely ambiguous NL languages and $\# P_1$-complete census functions
+Normal rank
@@ Property / cites work @@
+An optimal lower bound for nonregular languages
@@ Property / cites work: An optimal lower bound for nonregular languages / rank @@
+Normal rank
@@ Property / cites work @@
+On a complexity hierarchy between L and NL
@@ Property / cites work: On a complexity hierarchy between L and NL / rank @@
+Normal rank
@@ Property / cites work @@
+Towards a complexity theory of synchronous parallel computation
+Normal rank
@@ Property / cites work @@
+A taxonomy of problems with fast parallel algorithms
+Normal rank
@@ Property / cites work @@
+A Time Complexity Gap for Two-Way Probabilistic Finite-State Automata
+Normal rank
@@ Property / cites work @@
+Algebraic languages and polyominoes enumeration
@@ Property / cites work: Algebraic languages and polyominoes enumeration / rank @@
+Normal rank
@@ Property / cites work @@
+Nondeterministic Computations in Sublogarithmic Space and Space Constructibility
+Normal rank
@@ Property / cites work @@
+Formal languages and enumeration
@@ Property / cites work: Formal languages and enumeration / rank @@
+Normal rank
@@ Property / cites work @@
+One-tape, off-line Turing machine computations
@@ Property / cites work: One-tape, off-line Turing machine computations / rank @@
+Normal rank
@@ Property / cites work @@
+Languages Simultaneously Complete for One-Way and Two-Way Log-Tape Automata
+Normal rank
@@ Property / cites work @@
+Some Results on Tape-Bounded Turing Machines
@@ Property / cites work: Some Results on Tape-Bounded Turing Machines / rank @@
+Normal rank
@@ Property / cites work @@
+Q3862379
@@ Property / cites work: Q3862379 / rank @@
+Normal rank
@@ Property / cites work @@
+The complexity of ranking simple languages
@@ Property / cites work: The complexity of ranking simple languages / rank @@
+Normal rank
@@ Property / cites work @@
+Effective entropies and data compression
@@ Property / cites work: Effective entropies and data compression / rank @@
+Normal rank
@@ Property / cites work @@
+EFFICIENT DETECTORS AND CONSTRUCTORS FOR SIMPLE LANGUAGES
+Normal rank
@@ Property / cites work @@
+Random generation of combinatorial structures from a uniform distribution
+Normal rank
@@ Property / cites work @@
+Q4385522
@@ Property / cites work: Q4385522 / rank @@
+Normal rank
@@ Property / cites work @@
+Q5751951
@@ Property / cites work: Q5751951 / rank @@
+Normal rank
@@ Property / cites work @@
+On eliminating nondeterminism from Turing machines which use less than logarithm worktape space
+Normal rank
@@ Property / cites work @@
+Space bounded computations: Review and new separation results
+Normal rank
@@ Property / cites work @@
+On uniform circuit complexity
@@ Property / cites work: On uniform circuit complexity / rank @@
+Normal rank
@@ Property / cites work @@
+On the Efficient Generation of Language Instances
@@ Property / cites work: On the Efficient Generation of Language Instances / rank @@
+Normal rank