Internally Expandable Pushdown Automata and Their Computational Completeness

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26230%2F18%3APU130690" target="_blank" >RIV/00216305:26230/18:PU130690 - isvavai.cz</a>

Výsledek na webu

<a href="http://www.romjist.ro/full-texts/paper595.pdf" target="_blank" >http://www.romjist.ro/full-texts/paper595.pdf</a>

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Internally Expandable Pushdown Automata and Their Computational Completeness

Popis výsledku v původním jazyce

The present paper defines the notion of an internally expandable pushdown automaton (IEPDA). In essence, this automaton expands the topmost expandable non-input symbol in its pushdown list. This expanded symbol, however, may not occur on the very top of the pushdown; instead, it may appear deeper in the pushdown. The paper demonstrates that this notion represents an automaton-based counter part to the notion of a state grammar. Indeed, both are equally powerful. Therefore, internally expandable pushdown automata are computationally complete--that is, they are as powerful as Turing machines. In fact there are computationally complete IEPDAs with no more than four states

Název v anglickém jazyce

Internally Expandable Pushdown Automata and Their Computational Completeness

Popis výsledku anglicky

The present paper defines the notion of an internally expandable pushdown automaton (IEPDA). In essence, this automaton expands the topmost expandable non-input symbol in its pushdown list. This expanded symbol, however, may not occur on the very top of the pushdown; instead, it may appear deeper in the pushdown. The paper demonstrates that this notion represents an automaton-based counter part to the notion of a state grammar. Indeed, both are equally powerful. Therefore, internally expandable pushdown automata are computationally complete--that is, they are as powerful as Turing machines. In fact there are computationally complete IEPDAs with no more than four states

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2018

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Romanian Journal of Information Science and Technology (ROMJIST)

ISSN

1453-8245

e-ISSN

—

Svazek periodika

21

Číslo periodika v rámci svazku

3

Stát vydavatele periodika

RO - Rumunsko

Počet stran výsledku

6

Strana od-do

232-237

Kód UT WoS článku

000455900300004

EID výsledku v databázi Scopus

2-s2.0-85056635452