×

Unitary monoid with two generators: An algorithmic point of view. (English) Zbl 0758.68053

CAAP’90, Proc. 15th Colloq., Copenhagen/Denmark 1990, Lect. Notes Comput. Sci. 431, 117-131 (1990).
Summary: [For the entire collection see Zbl 0745.00027.]
We consider the following problem:
Instance: a finite alphabet \(A\), a biprefix code \(X=\{x,y\}\) whose elements are primitive, \(weA^*\).
Question: find every maximal factors of \(w\) which are prefixes of a word of \(X^*\).
We present an algorithm which solves the problem in time linear of the length of \(w\), after a preprocessing phase applied to the set \(X\).

MSC:

68R15 Combinatorics on words
94A45 Prefix, length-variable, comma-free codes
68Q25 Analysis of algorithms and problem complexity

Keywords:

factorization

Citations:

Zbl 0745.00027
PDFBibTeX XMLCite