A hierarchy that does not collapse : alternations in low level space
RAIRO-Theor. Inf. Appl., 28 5 (1994) 465-512
Published online: 2017-02-01
Articles citing this article
The Citing articles tool gives a list of articles citing the current article.
The citing articles come from EDP Sciences database, as well as other publishers participating in CrossRef Cited-by Linking Program. You can set up your personal account to receive an email alert each time this article is cited by a new article (see the menu on the right-hand side of the abstract page).
Cited article:
This article has been cited by the following article(s):
Machines, Computations, and Universality
Viliam Geffert and Zuzana BednárováLecture Notes in Computer Science, Machines, Computations, and Universality 10881 105 (2018)
https://doi.org/10.1007/978-3-319-92402-1_6
Alternating space is closed under complement and other simulations for sublogarithmic space
Viliam GeffertInformation and Computation 253 163 (2017)
https://doi.org/10.1016/j.ic.2017.02.001
Developments in Language Theory
Viliam GeffertLecture Notes in Computer Science, Developments in Language Theory 9840 190 (2016)
https://doi.org/10.1007/978-3-662-53132-7_16
An alternating hierarchy for finite automata
Viliam GeffertTheoretical Computer Science 445 1 (2012)
https://doi.org/10.1016/j.tcs.2012.04.044
Fooling Turing machines with sublogarithmic space: a note on ‘For completeness, sublogarithmic space is no space’ by M. Agrawal
Andrzej SzepietowskiInformation Processing Letters 106 (4) 162 (2008)
https://doi.org/10.1016/j.ipl.2007.11.005
Space hierarchy theorem revised
Viliam GeffertTheoretical Computer Science 295 (1-3) 171 (2003)
https://doi.org/10.1016/S0304-3975(02)00402-4
For completeness, sublogarithmic space is no space
Manindra AgrawalInformation Processing Letters 82 (6) 321 (2002)
https://doi.org/10.1016/S0020-0190(01)00296-4
Mathematical Foundations of Computer Science 2001
Viliam GeffertLecture Notes in Computer Science, Mathematical Foundations of Computer Science 2001 2136 387 (2001)
https://doi.org/10.1007/3-540-44683-4_34
Alternation for sublogarithmic space-bounded alternating pushdown automata
Jianliang Xu, Tsunehiro Yoshinaga, Katsushi Inoue, Yue Wang and Akira ItoTheoretical Computer Science 259 (1-2) 475 (2001)
https://doi.org/10.1016/S0304-3975(00)00035-9
A Space Lower Bound for Acceptance by One-Way Π2-Alternating Machines
Viliam Geffert and Norbert PopélyRAIRO - Theoretical Informatics and Applications 34 (5) 357 (2000)
https://doi.org/10.1051/ita:2000101
A variant of inductive counting
Viliam GeffertTheoretical Computer Science 237 (1-2) 465 (2000)
https://doi.org/10.1016/S0304-3975(99)00338-2
Bridging across the log(n) Space Frontier
Viliam GeffertInformation and Computation 142 (2) 127 (1998)
https://doi.org/10.1006/inco.1997.2682
Sublogarithmic Bounds on Space and Reversals
Viliam Geffert, Carlo Mereghetti and Giovanni PighizziniSIAM Journal on Computing 28 (1) 325 (1998)
https://doi.org/10.1137/S0097539796301306
Mathematical Foundations of Computer Science 1997
Maciej Liśkiewicz and Rüdiger ReischukLecture Notes in Computer Science, Mathematical Foundations of Computer Science 1997 1295 91 (1997)
https://doi.org/10.1007/BFb0029952
Mathematical Foundations of Computer Science 1995
Viliam GeffertLecture Notes in Computer Science, Mathematical Foundations of Computer Science 1995 969 50 (1995)
https://doi.org/10.1007/3-540-60246-1_112