On the power of Las Vegas II: Two-way finite automata (Q5958109): Difference between revisions

@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / cites work @@
+Q3938525
@@ Property / cites work: Q3938525 / rank @@
+Normal rank
@@ Property / cites work @@
+Exact lower time bounds for computing Boolean functions on CREW PRAMs
+Normal rank
@@ Property / cites work @@
+Las Vegas versus determinism for one-way communication complexity, finite automata, and polynomial-time computations
+Normal rank
@@ Property / cites work @@
+Computational Complexity of Probabilistic Turing Machines
+Normal rank
@@ Property / cites work @@
+Q5592246
@@ Property / cites work: Q5592246 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4337605
@@ Property / cites work: Q4337605 / rank @@
+Normal rank
@@ Property / cites work @@
+Communication Complexity
@@ Property / cites work: Communication Complexity / rank @@
+Normal rank
@@ Property / cites work @@
+Two-way deterministic finite automata are exponentially more succinct than sweeping automata
+Normal rank
@@ Property / cites work @@
+Communication complexity
@@ Property / cites work: Communication complexity / rank @@
+Normal rank
@@ Property / cites work @@
+Q4418659
@@ Property / cites work: Q4418659 / rank @@
+Normal rank
@@ Property / cites work @@
+Nondeterminism and the size of two way finite automata
+Normal rank
@@ Property / cites work @@
+Lower bounds on the size of sweeping automata
@@ Property / cites work: Lower bounds on the size of sweeping automata / rank @@
+Normal rank
@@ Property / cites work @@
+Q3762226
@@ Property / cites work: Q3762226 / rank @@
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1016/s0304-3975(00)00155-9
+Normal rank
@@ Property / OpenAlex ID @@
+W1971083528
@@ Property / OpenAlex ID: W1971083528 / rank @@
+Normal rank