Converting nondeterministic two-way automata into small deterministic linear-time machines (Q2105419): Difference between revisions

@@ Property / OpenAlex ID @@
+W3134046426
@@ Property / OpenAlex ID: W3134046426 / rank @@
+Normal rank
@@ Property / Wikidata QID @@
+Q114172424
@@ Property / Wikidata QID: Q114172424 / rank @@
+Normal rank
@@ Property / cites work @@
+Weight-Reducing Hennie Machines and Their Descriptional Complexity
+Normal rank
@@ Property / cites work @@
+Two-way automata and one-tape machines - read only versus linear time
+Normal rank
@@ Property / cites work @@
+Q4991691
@@ Property / cites work: Q4991691 / rank @@
+Normal rank
@@ Property / cites work @@
+Q5541340
@@ Property / cites work: Q5541340 / rank @@
+Normal rank
@@ Property / cites work @@
+More concise representation of regular languages by automata and regular expressions
+Normal rank
@@ Property / cites work @@
+Non-Self-Embedding Grammars, Constant-Height Pushdown Automata, and Limited Automata
+Normal rank
@@ Property / cites work @@
+Q3707408
@@ Property / cites work: Q3707408 / rank @@
+Normal rank
@@ Property / cites work @@
+LIMITED AUTOMATA AND REGULAR LANGUAGES
@@ Property / cites work: LIMITED AUTOMATA AND REGULAR LANGUAGES / rank @@
+Normal rank
@@ Property / cites work @@
+Limited automata and unary languages
@@ Property / cites work: Limited automata and unary languages / 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 @@
+Q5599173
@@ Property / cites work: Q5599173 / rank @@
+Normal rank
@@ Property / cites work @@
+Computational Complexity of One-Tape Turing Machine Computations
+Normal rank
@@ Property / cites work @@
+An NP-complete language accepted in linear time by a one-tape Turing machine
+Normal rank
@@ Property / cites work @@
+Q5192993
@@ Property / cites work: Q5192993 / rank @@
+Normal rank
@@ Property / cites work @@
+Theory of one-tape linear-time Turing machines
@@ Property / cites work: Theory of one-tape linear-time Turing machines / 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 @@
+Q4449194
@@ Property / cites work: Q4449194 / rank @@
+Normal rank
@@ Property / cites work @@
+Nondeterminism is essential in small two-way finite automata with few reversals
+Normal rank
@@ Property / cites work @@
+Converting two-way nondeterministic unary automata into simpler automata.
+Normal rank
@@ Property / cites work @@
+Two-way automata making choices only at the endmarkers
+Normal rank
@@ Property / cites work @@
+Two-way automata characterizations of L/poly versus NL
+Normal rank
@@ Property / cites work @@
+Q5747095
@@ Property / cites work: Q5747095 / rank @@
+Normal rank
@@ Property / cites work @@
+Deterministic context-sensitive languages: Part II
+Normal rank
@@ Property / cites work @@
+Q3862379
@@ Property / cites work: Q3862379 / rank @@
+Normal rank
@@ Property / cites work @@
+Classes of languages and linear-bounded automata
@@ Property / cites work: Classes of languages and linear-bounded automata / rank @@
+Normal rank
@@ Property / cites work @@
+Relationships between nondeterministic and deterministic tape complexities
+Normal rank
@@ Property / cites work @@
+Two-way automata versus logarithmic space
@@ Property / cites work: Two-way automata versus logarithmic space / rank @@
+Normal rank