A note on the emptiness of intersection problem for left Szilárd languages

Mäkinen Erkki: A note on the emptiness of intersection problem for left Szilárd languages. In: Acta cybernetica, (22) 3. pp. 613-616. (2016)

[thumbnail of actacyb_22_3_2016_4.pdf]
Cikk, tanulmány, mű

Download (248kB) | Preview


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.

Item Type: Article
Journal or Publication Title: Acta cybernetica
Date: 2016
Volume: 22
Number: 3
ISSN: 0324-721X
Page Range: pp. 613-616
Language: English
Place of Publication: Szeged
Related URLs: http://acta.bibl.u-szeged.hu/41665/
DOI: 10.14232/actacyb.22.3.2016.4
Uncontrolled Keywords: Programozási nyelv - determinisztikus
Additional Information: Bibliogr.: p. 615-616. ; összefoglalás angol nyelven
Subjects: 01. Natural sciences
01. Natural sciences > 01.02. Computer and information sciences
Date Deposited: 2017. Mar. 16. 13:20
Last Modified: 2022. Jun. 20. 13:21
URI: http://acta.bibl.u-szeged.hu/id/eprint/40265

Actions (login required)

View Item View Item