Regulated pushdown automata
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 con...
Elmentve itt :
| Szerzők: | |
|---|---|
| Dokumentumtípus: | Cikk |
| Megjelent: |
2000
|
| Sorozat: | Acta cybernetica
14 No. 4 |
| Kulcsszavak: | Számítástechnika, Kibernetika, Automaták |
| Tárgyszavak: | |
| Online Access: | http://acta.bibl.u-szeged.hu/12656 |
| LEADER | 01454nab a2200229 i 4500 | ||
|---|---|---|---|
| 001 | acta12656 | ||
| 005 | 20220614113239.0 | ||
| 008 | 161015s2000 hu o 0|| eng d | ||
| 022 | |a 0324-721X | ||
| 040 | |a SZTE Egyetemi Kiadványok Repozitórium |b hun | ||
| 041 | |a eng | ||
| 100 | 1 | |a Meduna Alexander | |
| 245 | 1 | 0 | |a Regulated pushdown automata |h [elektronikus dokumentum] / |c Meduna Alexander |
| 260 | |c 2000 | ||
| 300 | |a 653-664 | ||
| 490 | 0 | |a Acta cybernetica |v 14 No. 4 | |
| 520 | 3 | |a 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. | |
| 650 | 4 | |a Természettudományok | |
| 650 | 4 | |a Számítás- és információtudomány | |
| 695 | |a Számítástechnika, Kibernetika, Automaták | ||
| 700 | 0 | 1 | |a Kolar Dusan |e aut |
| 856 | 4 | 0 | |u http://acta.bibl.u-szeged.hu/12656/1/cybernetica_014_numb_004_653-664.pdf |z Dokumentum-elérés |