Wyniki wyszukiwania - BazTech

Ograniczanie wyników

1 Schedae Informaticae

1 2017

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: finite expandability

Sortuj według:

Ogranicz wyniki do:

A reduction of finitely expandable deep pushdown automata

Dvořáková L., Meduna A.

Schedae Informaticae

2017

Vol. 26

61--68

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 present 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. 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. In its conclusion, the paper suggests open problems and topics for the future investigation.