Two-way unary automata versus logarithmic space (Q549665): Difference between revisions

@@ Property / Mathematics Subject Classification ID @@
+Q45
@@ Property / Mathematics Subject Classification ID: 68Q45 / rank @@
+Normal rank
@@ Property / Mathematics Subject Classification ID @@
+Q15
@@ Property / Mathematics Subject Classification ID: 68Q15 / rank @@
+Normal rank
@@ Property / zbMATH DE Number @@
+5925498
@@ Property / zbMATH DE Number: 5925498 / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+unary regular languages
@@ Property / zbMATH Keywords: unary regular languages / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+finite automata
@@ Property / zbMATH Keywords: finite automata / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+state complexity
@@ Property / zbMATH Keywords: state complexity / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+logarithmic space
@@ Property / zbMATH Keywords: logarithmic space / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+space complexity
@@ Property / zbMATH Keywords: space complexity / rank @@
+Normal rank
@@ Property / MaRDI profile type @@
+Publication
@@ Property / MaRDI profile type: Publication / rank @@
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1016/j.ic.2011.03.003
+Normal rank
@@ Property / OpenAlex ID @@
+W2005397173
@@ Property / OpenAlex ID: W2005397173 / rank @@
+Normal rank
@@ Property / Wikidata QID @@
+Q61677514
@@ Property / Wikidata QID: Q61677514 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4139689
@@ Property / cites work: Q4139689 / rank @@
+Normal rank
@@ Property / cites work @@
+State-complexity of finite-state devices, state compressibility and incompressibility
+Normal rank
@@ Property / cites work @@
+Converting two-way nondeterministic unary automata into simpler automata.
+Normal rank
@@ Property / cites work @@
+Q3862379
@@ Property / cites work: Q3862379 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4449194
@@ Property / cites work: Q4449194 / rank @@
+Normal rank
@@ Property / cites work @@
+Space-bounded reducibility among combinatorial problems
+Normal rank
@@ Property / cites work @@
+Q3517105
@@ Property / cites work: Q3517105 / rank @@
+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 @@
+Turing machines that take advice
@@ Property / cites work: Turing machines that take advice / rank @@
+Normal rank
@@ Property / cites work @@
+DESCRIPTIONAL COMPLEXITY OF NFA OF DIFFERENT AMBIGUITY
+Normal rank
@@ Property / cites work @@
+Q4503152
@@ Property / cites work: Q4503152 / rank @@
+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 @@
+Relating the Type of Ambiguity of Finite Automata to the Succinctness of Their Representation
+Normal rank
@@ Property / cites work @@
+Making Nondeterminism Unambiguous
@@ Property / cites work: Making Nondeterminism Unambiguous / rank @@
+Normal rank
@@ Property / cites work @@
+Nondeterminism and the size of two way finite automata
+Normal rank
@@ Property / cites work @@
+Relationships between nondeterministic and deterministic tape complexities
+Normal rank
@@ Property / cites work @@
+Q5541340
@@ Property / cites work: Q5541340 / 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
@@ Property / cites work @@
+Turing machines with sublogarithmic space
@@ Property / cites work: Turing machines with sublogarithmic space / rank @@
+Normal rank
@@ Property / cites work @@
+Unary finite automata vs. arithmetic progressions
@@ Property / cites work: Unary finite automata vs. arithmetic progressions / rank @@
+Normal rank
@@ links / mardi / name / links / mardi / name @@
+Publication:549665