Algebraic caractérisations of NTIME and NTIME
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (1984)
- Volume: 18, Issue: 4, page 365-385
- ISSN: 0988-3754
Access Full Article
top
How to cite
topStenger, Hans-Jürgen. "Algebraic caractérisations of NTIME$(F)$ and NTIME$(F, A)$." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 18.4 (1984): 365-385. <http://eudml.org/doc/92217>.
@article{Stenger1984,
author = {Stenger, Hans-Jürgen},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {nondeterministic Turing machines; oracle machines; classes of formal languages},
language = {eng},
number = {4},
pages = {365-385},
publisher = {EDP-Sciences},
title = {Algebraic caractérisations of NTIME$(F)$ and NTIME$(F, A)$},
url = {http://eudml.org/doc/92217},
volume = {18},
year = {1984},
}
TY - JOUR
AU - Stenger, Hans-Jürgen
TI - Algebraic caractérisations of NTIME$(F)$ and NTIME$(F, A)$
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 1984
PB - EDP-Sciences
VL - 18
IS - 4
SP - 365
EP - 385
LA - eng
KW - nondeterministic Turing machines; oracle machines; classes of formal languages
UR - http://eudml.org/doc/92217
ER -
References
top- 1. B. S. BAKER and R. V. BOOK, Reversal-bounded Multipushdown Machines, J. of Computer and Systems Science, Vol. 8, 1974, pp. 315-332. Zbl0309.68043MR375844
- 2. R. V. BOOK, Simple Representations of certain classes of Languages, J.A.C.M., Vol. 25, 1978, No. 1, pp. 23-31. Zbl0364.68073MR461992
- 3. R. V. BOOK, On languages Accepted by Space-bounded Oracle-Machines, Acta Informatica, Vol. 12, 1979, pp. 177-185. Zbl0389.68029MR538287
- 4. R. V. BOOK, Complexity Classes of Formal Languages, Springer Lect. Notes in Comp. Sci., Vol. 74, pp. 43-56, Springer, Berlin, New York, 1979. Zbl0413.68045MR570974
- 5. R. V. BOOK and C. WRATHALL, On languages specified by relative acceptance, Theoretical Computer Science, Vol. 7, 1978, pp. 185-195. Zbl0385.68061MR509016
- 6. S. GINSBURG, Algebraic and automata-theoretic properties of formal languages, North-Holland, Amsterdam, 1975. Zbl0325.68002MR443446
- 7. J. HOPCROFT and J. ULLMAN, Introduction to Automata Theory, Languages and Computation, Addison-Wesley, Amsterdam, 1979. Zbl0426.68001MR645539
- 8. W. J. PAUL, Komplexitätstheorie, Teubner, Stuttgart, 1978. MR517109
- 9. H. SCHWICHTENBERG, Rekursionszahlen und die Grzegorczyk Hierarchie, Arch. math. Logik, Vol. 12, 1969, pp. 85-97. Zbl0213.01801MR253900
- 10. C. WRATHALL, Subrecursive Predicates and Automata, Ph. D. dissertation, Harvard University, 1975.
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.