UNDECIDABILITY OF LANGUAGE EQUIVALENCE FOR GENERALIZED REGULAR EXPRESSIONS

Article type: Research Article

Authors: Hirshfeld, Yoram

Affiliations: School of Mathematical Sciences, Sackler Faculty of Exact Sciences, Tel Aviv University, Tel Aviv 69978, Israel

Abstract: The shuffle operator models communication free concurrency and has little expressive power (it does not produce new languages when added to regular expressions). Decidability problems for languages involving this operation were previously tackled but remained unsolved (except for a weak conjecture). We prove that language equivalence is undecidable even for a very restricted class of expressions involving the shuffle operator. This also re-proves that language equivalence is undecidable for Basic Parallel Processes.

DOI: 10.3233/FI-1996-2617

Journal: Fundamenta Informaticae, vol. 26, no. 1, pp. 95-102, 1996