Sublogarithmic-space turing machines, nonuniform space complexity, and closure properties (Q3811712): Difference between revisions

@@ Property / author @@
-Bala Ravikumar
@@ Property / author: Bala Ravikumar / rank @@
-Normal rank
@@ Property / author @@
+Bala Ravikumar
@@ Property / author: Bala Ravikumar / rank @@
+Normal rank
@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / cites work @@
+Lower bounds on space complexity for contextfree recognition
+Normal rank
@@ Property / cites work @@
+On pebble automata
@@ Property / cites work: On pebble automata / rank @@
+Normal rank
@@ Property / cites work @@
+Q3811706
@@ Property / cites work: Q3811706 / rank @@
+Normal rank
@@ Property / cites work @@
+Some observations concerning alternating Turing machines using small space
+Normal rank
@@ Property / cites work @@
+Space bounds for processing contentless inputs
@@ Property / cites work: Space bounds for processing contentless inputs / rank @@
+Normal rank
@@ Property / cites work @@
+Remarks on the complexity of nondeterministic counter languages
+Normal rank
@@ Property / cites work @@
+On tape bounds for single letter alphabet language processing
+Normal rank
@@ Property / cites work @@
+Q4198075
@@ Property / cites work: Q4198075 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3862379
@@ Property / cites work: Q3862379 / rank @@
+Normal rank
@@ Property / cites work @@
+Circuit-size lower bounds and non-reducibility to sparse sets
+Normal rank
@@ Property / cites work @@
+On efficient deterministic simulation of turing machine computations below logaspace
+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 @@
+A note on multihead automata and context-sensitive languages
+Normal rank
@@ Property / cites work @@
+Halting space-bounded computations
@@ Property / cites work: Halting space-bounded computations / rank @@
+Normal rank
@@ Property / cites work @@
+Q5636862
@@ Property / cites work: Q5636862 / rank @@
+Normal rank
@@ Property / cites work @@
+There are no fully space constructible functions between log log n and log n
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1007/bf02088003
+Normal rank
@@ Property / OpenAlex ID @@
+W2088539304
@@ Property / OpenAlex ID: W2088539304 / rank @@
+Normal rank