Size complexity of rotating and sweeping automata (Q414916): Difference between revisions

@@ Property / cites work @@
+Q3938525
@@ Property / cites work: Q3938525 / rank @@
+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 @@
+A Time Complexity Gap for Two-Way Probabilistic Finite-State Automata
+Normal rank
@@ Property / cites work @@
+Q3947125
@@ Property / cites work: Q3947125 / rank @@
+Normal rank
@@ Property / cites work @@
+Complementing two-way finite automata
@@ Property / cites work: Complementing two-way finite automata / rank @@
+Normal rank
@@ Property / cites work @@
+Q4228510
@@ Property / cites work: Q4228510 / rank @@
+Normal rank
@@ Property / cites work @@
+On the power of Las Vegas for one-way communication complexity, OBDDs, and finite automata
+Normal rank
@@ Property / cites work @@
+On the power of Las Vegas II: Two-way finite automata
+Normal rank
@@ Property / cites work @@
+State complexity of some operations on binary regular languages
+Normal rank
@@ Property / cites work @@
+Small Sweeping 2NFAs Are Not Closed Under Complement
+Normal rank
@@ Property / cites work @@
+Size Complexity of Two-Way Finite Automata
@@ Property / cites work: Size Complexity of Two-Way Finite Automata / rank @@
+Normal rank
@@ Property / cites work @@
+An Exponential Gap Between LasVegas and Deterministic Sweeping Finite Automata
+Normal rank
@@ Property / cites work @@
+On the Size Complexity of Rotating and Sweeping Automata
+Normal rank
@@ Property / cites work @@
+Amplification of slight probabilistic advantage at absolutely no cost in space
+Normal rank
@@ Property / cites work @@
+Two-way deterministic finite automata are exponentially more succinct than sweeping automata
+Normal rank
@@ Property / cites work @@
+Q5541339
@@ Property / cites work: Q5541339 / rank @@
+Normal rank
@@ Property / cites work @@
+Nondeterminism and the size of two way finite automata
+Normal rank
@@ Property / cites work @@
+Halting space-bounded computations
@@ Property / cites work: Halting space-bounded computations / rank @@
+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