Detail publikace

A Reduction of Finitely Expandable Deep Pushdown Automata

CHARVÁT, L. MEDUNA, A.

Originální název

A Reduction of Finitely Expandable Deep Pushdown Automata

Typ

článek v časopise ve Scopus, Jsc

Jazyk

angličtina

Originální abstrakt

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.

Klíčová slova

Deep Pushdown Automata, Finite Expandability, Reduction, Non-Input Pushdown Symbols

Autoři

CHARVÁT, L.; MEDUNA, A.

Vydáno

16. 2. 2018

ISSN

0860-0295

Periodikum

Schedae Informaticae

Ročník

2017

Číslo

26

Stát

Polská republika

Strany od

61

Strany do

68

Strany počet

8

URL

http://www.ejournals.eu/Schedae-Informaticae/2017/Volume-26/art/10836/

BibTex

@article{BUT157232,
  author="Lucie {Charvát} and Alexandr {Meduna}",
  title="A Reduction of Finitely Expandable Deep Pushdown Automata",
  journal="Schedae Informaticae",
  year="2018",
  volume="2017",
  number="26",
  pages="61--68",
  doi="10.4467/20838476SI.17.005.8151",
  issn="0860-0295",
  url="http://www.ejournals.eu/Schedae-Informaticae/2017/Volume-26/art/10836/"
}