Regulated pushdown automata

Meduna Alexander and Kolar Dusan: Regulated pushdown automata. In: Acta cybernetica, (14) 4. pp. 653-664. (2000)

[thumbnail of cybernetica_014_numb_004_653-664.pdf]
Cikk, tanulmány, mű

Download (722kB) | Preview


The present paper suggests a new investigation area of the formal language theory — regulated automata. Specifically, it investigates pushdown automata that regulate the use of their rules by control languages. It proves that this regulation has no effect on the power of pushdown automata if the control languages are regular. However, the pushdown automata regulated by linear control languages characterize the family of recursively enumerable languages. All these results are established in terms of (A) acceptance by final state, (B) acceptance by empty pushdown, and (C) acceptance by final state and empty pushdown. In its conclusion, this paper formulates several open problems.

Item Type: Article
Journal or Publication Title: Acta cybernetica
Date: 2000
Volume: 14
Number: 4
ISSN: 0324-721X
Page Range: pp. 653-664
Language: English
Place of Publication: Szeged
Related URLs:
Uncontrolled Keywords: Számítástechnika, Kibernetika, Automaták
Additional Information: Bibliogr.: 664. p. ; összefoglalás angol nyelven
Subjects: 01. Natural sciences
01. Natural sciences > 01.02. Computer and information sciences
Date Deposited: 2016. Oct. 15. 12:25
Last Modified: 2022. Jun. 14. 11:32

Actions (login required)

View Item View Item