Paper Info
Title
An examination of Ohlebusch and Ukkonen's conjecture on the equivalence problem for E-pattern languages
Abstract
Our paper contributes 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 which, 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 and, thus, yields new insights into combinatories on morphisms in free monoids - is restricted to terminal alphabets with at most four distinct letters. Additionally and with regard to larger alphabets, we examine the standard proof technique which in previous works has successfully been applied to restricted variants of the equivalence problem, and we show that it has to be adapted in an unexpected manner if the full class of E-pattern languages is considered. This necessity of modifying the analysed method is caused by a strongly counter-intuitive phenomenon concerning the expressive power of injective morphisms.
Year
Venue
Keywords
2007
Journal of Automata, Languages and Combinatorics
yields new insight,pattern language,equivalence problem,theoretical computer science,computable function,analysed method,injective morphisms,restricted variant,new facet,e-pattern language,decision problems,combinatorics on words
Field
DocType
Volume
Discrete mathematics,Combinatorics,Injective function,Abstract family of languages,Monoid,Ukkonen's algorithm,Equivalence (measure theory),Conjecture,Mathematics,Combinatorics on words,Computable function
Journal
12
Issue
Citations 
PageRank 
3
4
0.48
References 
Authors
13
1
Name
Order
Citations
PageRank
Daniel Reidenbach115418.06