Počet záznamů: 1

Regulated nondeterminism in pushdown automata : the non-regular case

  1. 1.
    0353078 - MU-W 2011 RIV NL eng J - Článek v odborném periodiku
    Masopust, Tomáš
    Regulated nondeterminism in pushdown automata : the non-regular case.
    Fundamenta Informaticae. Roč. 104, 1-2 (2010), s. 111-124 ISSN 0169-2968
    Výzkumný záměr: CEZ:AV0Z10190503
    Klíčová slova: pushdown automata * regulation * generative power
    Kód oboru RIV: BA - Obecná matematika
    Impakt faktor: 0.522, rok: 2010
    http://iospress.metapress.com/content/y7830k816323x351/?issue=1&genre=article&spage=111&issn=0169-2968&volume=104

    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.
    Trvalý link: http://hdl.handle.net/11104/0192422
    Název souboruStaženoVelikostKomentářVerzePřístup
    Masopust5.pdf194.9 KBVydavatelský postprintvyžádat