Algebraic caractérisations of NTIME(F) and NTIME(F,A)
Stenger, Hans-Jürgen
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 18 (1984), p. 365-385 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Publié le : 1984-01-01
@article{ITA_1984__18_4_365_0,
     author = {Stenger, Hans-J\"urgen},
     title = {Algebraic caract\'erisations of NTIME$(F)$ and NTIME$(F, A)$},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {18},
     year = {1984},
     pages = {365-385},
     mrnumber = {775839},
     zbl = {0547.68080},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_1984__18_4_365_0}
}

Stenger, Hans-Jürgen. Algebraic caractérisations of NTIME$(F)$ and NTIME$(F, A)$. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 18 (1984) pp. 365-385. http://gdmltest.u-ga.fr/item/ITA_1984__18_4_365_0/

1. B. S. Baker and R. V. Book, Reversal-bounded Multipushdown Machines, J. of Computer and Systems Science, Vol. 8, 1974, pp. 315-332. | MR 375844 | Zbl 0309.68043

2. R. V. Book, Simple Representations of certain classes of Languages, J.A.C.M., Vol. 25, 1978, No. 1, pp. 23-31. | MR 461992 | Zbl 0364.68073

3. R. V. Book, On languages Accepted by Space-bounded Oracle-Machines, Acta Informatica, Vol. 12, 1979, pp. 177-185. | MR 538287 | Zbl 0389.68029

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. | MR 570974 | Zbl 0413.68045

5. R. V. Book and C. Wrathall, On languages specified by relative acceptance, Theoretical Computer Science, Vol. 7, 1978, pp. 185-195. | MR 509016 | Zbl 0385.68061

6. S. Ginsburg, Algebraic and automata-theoretic properties of formal languages, North-Holland, Amsterdam, 1975. | MR 443446 | Zbl 0325.68002

7. J. Hopcroft and J. Ullman, Introduction to Automata Theory, Languages and Computation, Addison-Wesley, Amsterdam, 1979. | MR 645539 | Zbl 0426.68001

8. W. J. Paul, Komplexitätstheorie, Teubner, Stuttgart, 1978. | MR 517109

9. H. Schwichtenberg, Rekursionszahlen und die Grzegorczyk Hierarchie, Arch. math. Logik, Vol. 12, 1969, pp. 85-97. | MR 253900 | Zbl 0213.01801

10. C. Wrathall, Subrecursive Predicates and Automata, Ph. D. dissertation, Harvard University, 1975.