A Note on the Emptiness of Intersection Problem for Left Szilard Languages | Zendy

Erkki Mäkinen | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

A Note on the Emptiness of Intersection Problem for Left Szilard Languages

Author(s) -

Erkki Mäkinen

Publication year - 2016

Publication title -

acta cybernetica

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.143

H-Index - 18

eISSN - 2676-993X

pISSN - 0324-721X

DOI - 10.14232/actacyb.22.3.2016.4

Subject(s) - undecidable problem , decidability , emptiness , intersection (aeronautics) , equivalence (formal languages) , simple (philosophy) , mathematics , discrete mathematics , subclass , computer science , combinatorics , philosophy , theology , epistemology , antibody , engineering , immunology , biology , aerospace engineering

As left Szilard languages form a subclass of simple deterministiclanguages and even a subclass of super-deterministic languages, weknow that their equivalence problem is decidable. In this note weshow that their emptiness of intersection problem is undecidable.The proof follows the lines of the correponding proof for simpledeterministic languages, but some technical tricks are needed. Thisresult sharpens the borderline between decidable and undecidableproblems in formal language theory.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research