dlt04_reidenbach.pdf (179.53 kB)
0/0

On the equivalence problem for E-pattern languages over small alphabets

Download (179.53 kB)
journal contribution
posted on 09.07.2008 by Daniel Reidenbach
We 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-380

Publisher

© Springer-Verlag

Publication date

2005

Notes

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.com

ISBN

9783540240143

ISSN

0302-9743;1611-3349

Language

en

Exports

Logo branding

Keyword(s)

Exports