Počet záznamů: 1
Regulated nondeterminism in pushdown automata : the non-regular case
- 1.
SYSNO ASEP 0353078 Druh ASEP J - Článek v odborném periodiku Zařazení RIV J - Článek v odborném periodiku Poddruh J Článek ve WOS Název Regulated nondeterminism in pushdown automata : the non-regular case Tvůrce(i) Masopust, Tomáš (MU-W) RID, ORCID, SAI Zdroj.dok. Fundamenta Informaticae. - : IOS Press - ISSN 0169-2968
Roč. 104, 1-2 (2010), s. 111-124Poč.str. 14 s. Jazyk dok. eng - angličtina Země vyd. NL - Nizozemsko Klíč. slova pushdown automata ; regulation ; generative power Vědní obor RIV BA - Obecná matematika CEZ AV0Z10190503 - MU-W (2005-2011) UT WOS 000285459400006 EID SCOPUS 78650647940 DOI 10.3233/FI-2010-338 Anotace We continue the investigation of pushdown automata which are allowed to make a non-deterministic decision if and only if their pushdown content forms a string belonging to a given control language. We prove that if the control language is linear and non-regular, then the power of pushdown automata regulated in this way is increased to the power of Turing machines. From a practical point of view, however, it is inefficient to check the form of the pushdown content in each computational step. Therefore, we prove that only two checks of the pushdown content are of interest for these machines to be computationally complete. Based on this observation, we introduce and discuss a new model of regulated pushdown automata. Pracoviště Matematický ústav Kontakt Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Rok sběru 2011
Počet záznamů: 1