×

Algebraic characterisations of NTIME(F) and NTIME(F,A). (English) Zbl 0547.68080

Summary: If F is a class of time bounds and A is a language, then NTIME(F) (NTIME(F,A)) is the class of languages accepted by nondeterministic Turing machines (by oracle machines with oracle set A) that are time bounded by a function of F. Each of these two classes is characterized algebraically through a uniform representation of its languages. As an application, several classes of formal languages, each with its relativized counterpart, are characterized by specification of F: the class of recursively enumerable (recursive, primitive recursive) sets, for each \(k\geq 3\) the class \(E_ k\) of sets whose characteristic function is in the Grzegorczyk class \({\mathcal E}_ k\) and the class NP.

MSC:

68Q45 Formal languages and automata
68Q25 Analysis of algorithms and problem complexity
03D05 Automata and formal grammars in connection with logical questions
03D10 Turing machines and related notions
03D15 Complexity of computation (including implicit computational complexity)
PDFBibTeX XMLCite
Full Text: EuDML

References:

[1] 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.68043 MR375844 · Zbl 0309.68043 · doi:10.1016/S0022-0000(74)80027-9
[2] 2. R. V. BOOK, Simple Representations of certain classes of Languages, J.A.C.M., Vol. 25, 1978, No. 1, pp. 23-31. Zbl0364.68073 MR461992 · Zbl 0364.68073 · doi:10.1145/322047.322050
[3] 3. R. V. BOOK, On languages Accepted by Space-bounded Oracle-Machines, Acta Informatica, Vol. 12, 1979, pp. 177-185. Zbl0389.68029 MR538287 · Zbl 0389.68029 · doi:10.1007/BF00266049
[4] 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.68045 MR570974 · Zbl 0413.68045
[5] 5. R. V. BOOK and C. WRATHALL, On languages specified by relative acceptance, Theoretical Computer Science, Vol. 7, 1978, pp. 185-195. Zbl0385.68061 MR509016 · Zbl 0385.68061 · doi:10.1016/0304-3975(78)90048-8
[6] 6. S. GINSBURG, Algebraic and automata-theoretic properties of formal languages, North-Holland, Amsterdam, 1975. Zbl0325.68002 MR443446 · Zbl 0325.68002
[7] 7. J. HOPCROFT and J. ULLMAN, Introduction to Automata Theory, Languages and Computation, Addison-Wesley, Amsterdam, 1979. Zbl0426.68001 MR645539 · Zbl 0426.68001
[8] 8. W. J. PAUL, Komplexitätstheorie, Teubner, Stuttgart, 1978. MR517109
[9] 9. H. SCHWICHTENBERG, Rekursionszahlen und die Grzegorczyk Hierarchie, Arch. math. Logik, Vol. 12, 1969, pp. 85-97. Zbl0213.01801 MR253900 · Zbl 0213.01801 · doi:10.1007/BF01982053
[10] 10. C. WRATHALL, Subrecursive Predicates and Automata, Ph. D. dissertation, Harvard University, 1975.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.