A note on the emptiness of intersection problem for left Szilárd languages
As left Szilárd languages form a subclass of simple deterministic languages and even a subclass of super-deterministic languages, we know that their equivalence problem is decidable. In this note we show that their emptiness of intersection problem is undecidable. The proof follows the lines of the...
Elmentve itt :
| Szerző: | |
|---|---|
| Dokumentumtípus: | Cikk |
| Megjelent: |
2016
|
| Sorozat: | Acta cybernetica
22 No. 3 |
| Kulcsszavak: | Programozási nyelv - determinisztikus |
| Tárgyszavak: | |
| doi: | 10.14232/actacyb.22.3.2016.4 |
| Online Access: | http://acta.bibl.u-szeged.hu/40265 |
| LEADER | 01308nab a2200229 i 4500 | ||
|---|---|---|---|
| 001 | acta40265 | ||
| 005 | 20220620132156.0 | ||
| 008 | 170316s2016 hu o 0|| eng d | ||
| 022 | |a 0324-721X | ||
| 024 | 7 | |a 10.14232/actacyb.22.3.2016.4 |2 doi | |
| 040 | |a SZTE Egyetemi Kiadványok Repozitórium |b hun | ||
| 041 | |a eng | ||
| 100 | 1 | |a Mäkinen Erkki | |
| 245 | 1 | 2 | |a A note on the emptiness of intersection problem for left Szilárd languages |h [elektronikus dokumentum] / |c Mäkinen Erkki |
| 260 | |c 2016 | ||
| 300 | |a 613-616 | ||
| 490 | 0 | |a Acta cybernetica |v 22 No. 3 | |
| 520 | 3 | |a As left Szilárd languages form a subclass of simple deterministic languages and even a subclass of super-deterministic languages, we know that their equivalence problem is decidable. In this note we show that their emptiness of intersection problem is undecidable. The proof follows the lines of the corresponding proof for simple deterministic languages, but some technical tricks are needed. This result sharpens the borderline between decidable and undecidable problems in formal language theory. | |
| 650 | 4 | |a Természettudományok | |
| 650 | 4 | |a Számítás- és információtudomány | |
| 695 | |a Programozási nyelv - determinisztikus | ||
| 856 | 4 | 0 | |u http://acta.bibl.u-szeged.hu/40265/1/actacyb_22_3_2016_4.pdf |z Dokumentum-elérés |