On representing RE languages by one-sided internal contextual languages
In this paper we prove that each recursively enumerable language L can be written in the form L — cutd(L' fl R), where L' is a language generated by a one-sided internal contextual grammar witli context-free choice, R is a regular language, and cutd is the operation which removes the prefi...
Elmentve itt :
| Szerzők: | |
|---|---|
| Dokumentumtípus: | Cikk |
| Megjelent: |
1996
|
| Sorozat: | Acta cybernetica
12 No. 3 |
| Kulcsszavak: | Számítástechnika, Kibernetika |
| Tárgyszavak: | |
| Online Access: | http://acta.bibl.u-szeged.hu/12557 |
| LEADER | 01556nab a2200265 i 4500 | ||
|---|---|---|---|
| 001 | acta12557 | ||
| 005 | 20220613142520.0 | ||
| 008 | 161015s1996 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 Ehrenfeucht Andrzej | |
| 245 | 1 | 3 | |a On representing RE languages by one-sided internal contextual languages |h [elektronikus dokumentum] / |c Ehrenfeucht Andrzej |
| 260 | |c 1996 | ||
| 300 | |a 217-233 | ||
| 490 | 0 | |a Acta cybernetica |v 12 No. 3 | |
| 520 | 3 | |a In this paper we prove that each recursively enumerable language L can be written in the form L — cutd(L' fl R), where L' is a language generated by a one-sided internal contextual grammar witli context-free choice, R is a regular language, and cutd is the operation which removes the prefix bounded by the special symbol d, which appears exactly once in the strings for which cutd is defined. However, the context-free choice sets are always deterministic linear languages of a very simple form. Similar representations can be obtained using one-sided contextual grammars with finite choice and with erased or with erasing contexts. | |
| 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 | ||
| 700 | 0 | 1 | |a Mateescu Alexandru |e aut |
| 700 | 0 | 1 | |a Păun Gheorghe |e aut |
| 700 | 0 | 1 | |a Rozenberg Grzegorz |e aut |
| 700 | 0 | 1 | |a Salomaa Arto |e aut |
| 856 | 4 | 0 | |u http://acta.bibl.u-szeged.hu/12557/1/cybernetica_012_numb_003_217-233.pdf |z Dokumentum-elérés |