Tytuł artykułu
Autorzy
Wybrane pełne teksty z tego czasopisma
Identyfikatory
Warianty tytułu
Języki publikacji
Abstrakty
We resolve an old problem, namely to design a 'natural' machine model for accepting the complements of recursively enumerable languages. The model we present is based on nondeterministic Turing machines with 'one-sided' advice. We prove that these machines precisely accept the co-RE languages, without restriction on the advice functions that are used. We show that for accepting a co-RE language, one-sided advice is as powerful as arbitrary advice, but also that linearly bounded one-sided advice is sufficient. However, 'long' sublinear advice can make Turing machines with one-sided advice accept more co-RE languages than 'short' sublinear advice. We prove that infinite proper hierarchies of language classes inside co-RE can be devised, using suitable increasing sequences of bounding functions for the allowed advice. The machine model and the results dualize for the family of recursively enumerable languages.
Słowa kluczowe
Wydawca
Czasopismo
Rocznik
Tom
Strony
347--366
Opis fizyczny
Bibliogr. 14 poz.
Twórcy
autor
- Department of Information and Computing Sciences, Utrecht University, Princetonplein 5, 3584 CC Utrecht, the Netherlands
autor
- Institute of Computer Science, Academy of Sciences of the Czech Republic, Pod Vodárenskou vĕží 2, 182 07 Prague 8, Czech Republic
Bibliografia
- [1] Balcázar JL, Díaz J, Gabarró J. Structural Complexity I, Second Edition, Springer, 1995. doi:10.1007/978-3-642-79235-9.
- [2] Barzdin’ JaM. Complexity of programs to determine whether natural numbers not greater than n belong to recursively enumerable set, Soviet Math. Dokl. 1968;9(5):1251–1254.
- [3] Chandra A, Kozen D, Stockmeyer L. Alternation, JACM 1981;28(1):114–133. doi:10.1145/322234.322243.
- [4] Ehrenfeucht A, Rozenberg G, Ruohonen K. A morphic representation of complements of recursively enumerable sets, JACM. 1981;28(4):706–714. doi:10.1145/322276.322282.
- [5] Karp RM, Lipton RJ, Some connections between non-uniform and uniform complexity classes, Proc. Twelfth Ann. ACM Symp. on Theory of Computing, ACM Press, 1980, pp. 302–309. doi:10.1145/800141.804678.
- [6] Karp RM, Lipton RJ. Turing machines that take advice, L’Enseignement Mathématique IIe Série, Tome XXVIII. 1982, pp. 191–209. (Extended version of [5].)
- [7] Leivant D. Alternating Turing machines and the Analytical Hierarchy, in: A. Voronkov (Ed.), Turing-100. The Alan Turing Centenary, EPiC Series vol 10, Easychair, 2012, pp. 204-213. ISSN:2398-7340.
- [8] Păun G. (DNA) Computing by carving, Soft Computing. 1999;3(1):30–36. doi:10.1007/s005000050088.
- [9] Rogers Jr H. Theory of recursive functions and effective computability, McGraw-Hill, New York, 1967. URL https://books.google.pl/books?id=nAkzAAAAMAAJ.
- [10] Ruohonen K. On machine characterization of nonrecursive hierarchies, Ann. Univ. Turkuensis, Ser. A I .1984;186:87–101.
- [11] Turing AM. On computable numbers, with an application to the Entscheidungsproblem, Proc. London Math. Soc. 1936;42(2):230–265; A correction, ibid., 1937;43(2):544–546. doi:10.1112/plms/s2-42.1.230.
- [12] Turing AM. Systems of logic based on ordinals, Proc. London Math. Soc., Series 2, 45 1939, pp. 161–228. doi:10.1112/plms/s2-45.1.161.
- [13] Ullian JS. Three theorems concerning principal AFL’s, Journal of Computer and Systems Sciences, 1971;5:304–314. URL https://doi.org/10.1016/S0022-0000(71)80038-7.
- [14] Verbaan PRA. The Computational Complexity of Evolving Systems, Ph.D. Thesis, Dept of Information and Computing Sciences, Faculty of Science, Utrecht University, 2006.
Uwagi
Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017).
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-2f7abfc7-dc7e-45f9-a830-106f9066b2cf