{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T14:31:05Z","timestamp":1777645865891,"version":"3.51.4"},"reference-count":0,"publisher":"SAGE Publications","issue":"1","license":[{"start":{"date-parts":[[1996,1,1]],"date-time":"1996-01-01T00:00:00Z","timestamp":820454400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Fundamenta Informaticae"],"published-print":{"date-parts":[[1996,4]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.3233\/fi-1996-2617","type":"journal-article","created":{"date-parts":[[2019,12,2]],"date-time":"2019-12-02T20:49:16Z","timestamp":1575319756000},"page":"95-102","source":"Crossref","is-referenced-by-count":0,"title":["UNDECIDABILITY OF LANGUAGE EQUIVALENCE FOR GENERALIZED REGULAR EXPRESSIONS"],"prefix":"10.1177","volume":"26","author":[{"given":"Yoram","family":"Hirshfeld","sequence":"first","affiliation":[{"name":"School of Mathematical Sciences, Sackler Faculty of Exact Sciences, Tel Aviv University, Tel Aviv 69978, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"179","published-online":{"date-parts":[[1996,1,1]]},"container-title":["Fundamenta Informaticae"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/FI-1996-2617","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/FI-1996-2617","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T06:33:33Z","timestamp":1777444413000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.3233\/FI-1996-2617"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996,1,1]]},"references-count":0,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1996,4]]}},"alternative-id":["10.3233\/FI-1996-2617"],"URL":"https:\/\/doi.org\/10.3233\/fi-1996-2617","relation":{},"ISSN":["0169-2968","1875-8681"],"issn-type":[{"value":"0169-2968","type":"print"},{"value":"1875-8681","type":"electronic"}],"subject":[],"published":{"date-parts":[[1996,1,1]]}}}