dlt04_reidenbach.pdf (179.53 kB)
Download fileOn the equivalence problem for E-pattern languages over small alphabets
journal contribution
posted on 2008-07-09, 10:12 authored by Daniel ReidenbachWe contribute new facets to the discussion on the equivalence
problem for E-pattern languages (also referred to as extended or
erasing pattern languages). This fundamental open question asks for the
existence of a computable function that, given any pair of patterns, decides
whether or not they generate the same language. Our main result
disproves Ohlebusch and Ukkonen’s conjecture (Theoretical Computer
Science 186, 1997) on the equivalence problem; the respective argumentation,
that largely deals with the nondeterminism of pattern languages,
is restricted to terminal alphabets with at most four distinct letters.
History
School
- Science
Department
- Computer Science
Citation
REIDENBACH, D., 2005. On the equivalence problem for E-pattern languages over small alphabets. Lecture Notes in Computer Science, 3340, pp. 368-380Publisher
© Springer-VerlagPublication date
2005Notes
This is a journal article. It was published in Lecture notes in computer science [© Springer Verlag] and the definitive version is available at: www.springerlink.comISBN
9783540240143ISSN
0302-9743;1611-3349Language
- en