A Reduction of Finitely Expandable Deep Pushdown Automata

Kód výsledku v IS VaVaI

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

Výsledek na webu

<a href="http://www.ejournals.eu/Schedae-Informaticae/2017/Volume-26/art/10836/" target="_blank" >http://www.ejournals.eu/Schedae-Informaticae/2017/Volume-26/art/10836/</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.4467/20838476SI.17.005.8151" target="_blank" >10.4467/20838476SI.17.005.8151</a>

Jazyk výsledku

angličtina

Název v původním jazyce

A Reduction of Finitely Expandable Deep Pushdown Automata

Popis výsledku v původním jazyce

For a positive integer n, n-expandable deep pushdown automata always contain no more than n occurrences of non-input symbols in their pushdowns during any computation. As its main result, the paper demonstrates that these automata are as powerful as the same automata with only two non-input pushdown symbols---$ and #, where # always appears solely as the pushdown bottom. Moreover, the paper demonstrates an infinite hierarchy of language families that follows from this main result. The paper also points out that if # is the only non-input symbol in these automata, then they characterize the family of regular languages.

Název v anglickém jazyce

A Reduction of Finitely Expandable Deep Pushdown Automata

Popis výsledku anglicky

For a positive integer n, n-expandable deep pushdown automata always contain no more than n occurrences of non-input symbols in their pushdowns during any computation. As its main result, the paper demonstrates that these automata are as powerful as the same automata with only two non-input pushdown symbols---$ and #, where # always appears solely as the pushdown bottom. Moreover, the paper demonstrates an infinite hierarchy of language families that follows from this main result. The paper also points out that if # is the only non-input symbol in these automata, then they characterize the family of regular languages.

Druh

J_SC - Článek v periodiku v databázi SCOPUS

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)

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

Schedae Informaticae

ISSN

0860-0295

e-ISSN

—

Svazek periodika

2017

Číslo periodika v rámci svazku

26

Stát vydavatele periodika

PL - Polská republika

Počet stran výsledku

8

Strana od-do

61-68

Kód UT WoS článku

—

EID výsledku v databázi Scopus

2-s2.0-85057858123