Powiadomienia systemowe
- Sesja wygasła!
Tytuł artykułu
Wybrane pełne teksty z tego czasopisma
Identyfikatory
Warianty tytułu
Języki publikacji
Abstrakty
We study the computational and descriptional complexity of self-verifying pushdown automata (SVPDA) and self-verifying realtime queue automata (SVRQA). A self-verifying automaton is a nondeterministic device whose nondeterminism is symmetric in the following sense. Each computation path can give one of the answers yes, no, or do not know. For every input word, at least one computation path must give either the answer yes or no, and the answers given must not be contradictory. We show that SVPDA and SVRQA are automata characterizations of so-called complementation kernels, that is, context-free or realtime nondeterministic queue automaton languages whose complement is also context free or accepted by a realtime nondeterministic queue automaton. So, the families of languages accepted by SVPDA and SVRQA are strictly between the families of deterministic and nondeterministic languages. Closure properties and various decidability problems are considered. For example, it is shown that it is not semidecidable whether a given SVPDA or SVRQA can be made self-verifying. Moreover, we study descriptional complexity aspects of these machines. It turns out that the size trade-offs between nondeterministic and self-verifying as well as between self-verifying and deterministic automata are non-recursive. That is, one can choose an arbitrarily large recursive function f, but the gain in economy of description eventually exceeds f when changing from the former system to the latter.
Słowa kluczowe
Wydawca
Czasopismo
Rocznik
Tom
Strony
1--28
Opis fizyczny
Bibliogr. 26 poz., tab.
Twórcy
autor
- Fachbereich 4 – Abteilung Informatikwissenschaften, CIRT, Universität Trier, 54296 Trier, Germany
autor
- Institut für Informatik, Universität Giessen, Arndtstr. 2, 35392 Giessen, Germany
autor
- Institut für Informatik, Universität Giessen, Arndtstr. 2, 35392 Giessen, Germany
Bibliografia
- [1] Fischer PC, Kintala CMR. Real-Time Computations with Restricted Nondeterminism. Math. Systems Theory, 1979. 12:219-231. doi:10.1007/BF01776575.
- [2] Kintala CMR. Computations with a Restricted Number of Nondeterministic Steps. Ph.D. thesis, Pennsylvania State University, 1977.
- [3] Cygan M, Fomin FV, Kowalik L, Lokshtanov D, Marx D, Pilipczuk M, Pilipczuk M, Saurabh S. Parameterized Algorithms. Springer, 2015. ISBN:978-3-319-21274-6, 978-3-319-35702-7.
- [4] Downey RG, Fellows MR. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013. ISBN:978-1-4471-5559-1.
- [5] Duris P, Hromkovic J, Rolim JDP, Schnitger G. Las Vegas Versus Determinism for One-way Communication Complexity, Finite Automata, and Polynomial-time Computations. In: Reischuk R, Morvan M (eds.), Theoretical Aspects of Computer Science (STACS 1997), volume 1200 of LNCS. Springer, 1997 pp. 117-128. doi:10.1007/BFb0023453.
- [6] Hromkovic J, Schnitger G. On the Power of Las Vegas for One-Way Communication Complexity, OBDDs, and Finite Automata. Inform. Comput., 2001. 169:284-296. doi:10.1006/inco.2001.3040.
- [7] Hromkovic J, Schnitger G. Nondeterministic Communication with a Limited Number of Advice Bits. SIAM J. Comput., 2003. 33:43-68. doi:10.1137/S0097539702414622.
- [8] Jirásková G, Pighizzini G. Optimal simulation of self-verifying automata by deterministic automata. Inform. Comput., 2011. 209:528-535. doi:10.1016/j.ic.2010.11.017.
- [9] Ilie L, Păun G, Rozenberg G, Salomaa A. On Strongly Context-Free Languages. Discrete Appl. Math., 2000. 103:158-165. doi:10.1016/S0166-218X(99)00239-5.
- [10] Kutrib M, Malcher A, Wendlandt M. Queue Automata: Foundations and Developments. In: Adamatzky A (ed.), Reversibility and Universality, volume 30 of Emergence, Complexity and Computation, pp. 385-431. Springer, 2018. doi:10.1007/978-3-319-73216-9_19.
- [11] Cherubini A, Citrini C, Crespi-Reghizzi S, Mandrioli D. QRT FIFO Automata, Breadth-First Grammars and Their Relations. Theoret. Comput. Sci., 1991. 85:171-203.
- [12] Sudborough IH. One-Way Multihead Writing Finite Automata. Inform. Control, 1976. 30:1-20. doi:10.1016/S0019-9958(76)90426-5.
- [13] Sudborough IH. Computation by multihead writing finite automata. Ph.D. thesis, Pennsylvania State University, 1971.
- [14] Holzer M, Kutrib M. Descriptional Complexity - An Introductory Survey. In: Martín-Vide C (ed.), Scientific Applications of Language Methods, pp. 1-58. Imperial College Press, 2010. doi:10.1142/9781848165458_0001.
- [15] Hartmanis J. On Gödel speed-up and succinctness of language representations. Theoret. Comput. Sci., 1983. 26:335-342.
- [16] Hartmanis J. Context-free languages and Turing machine computations. Proc. Symposia in Applied Mathematics, 1967. 19:42-51. doi:10.2307/2272443.
- [17] Herzog C. Pushdown automata with bounded nondeterminism and bounded ambiguity. Theoret. Comput. Sci., 1997. 181:141-157. doi:10.1016/S0304-3975(96)00267-8.
- [18] Herzog C. Die Rolle des Nichtdeterminismus in kontextfreien Sprachen. Doctoral dissertation, Universität Frankfurt, 1999. (in German).
- [19] Holzer M, Kutrib M. One-Time Nondeterministic Computations. In: Pighizzini G, Câmpeanu C (eds.), Descriptional Complexity of Formal Systems (DCFS 2017), volume 10316 of LNCS. Springer, 2017 pp. 177-188. doi:10.1007/978-3-319-60252-3_14.
- [20] Harrison MA. Introduction to Formal Language Theory. Addison-Wesley, Reading, 1978.
- [21] Sénizergues G. L(A) = L(B)? Decidability Results from Complete Formal Systems. Theoret. Comput. Sci., 2001. 251:1-166. doi:10.1016/S0304-3975(00)00285-1.
- [22] Stearns RE. A regularity test for pushdown machines. Inform. Control, 1967. 11:323-340. doi:10.1016/S0019-9958(67)90591-8.
- [23] Rogers H. Theory of Recursive Functions and Effective Computability. McGraw-Hill, New York, 1967. doi:10.2307/2271523.
- [24] Salomaa A. Formal Languages. Academic Press, New York, 1973. doi:10.2307/2271881.
- [25] Hopcroft JE, Ullman JD. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading, Massachusetts, 1979. ISBN-13: 978-0201029888, 10:020102988X.
- [26] Schneider C. Deterministisch kontextfreie Sprachen und ihre Reversionen. Master’s thesis, Institut für Informatik, Universität Giessen, 2007. (in German).
Uwagi
Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2021).
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-aa77c1b2-e42f-487f-adc8-9d51d81f3aad