References of "Domaratzki, Michael"
     in
Bookmark and Share    
Full Text
Peer Reviewed
See detailComposition and orbits of language operations: finiteness and upper bounds
Charlier, Emilie ULg; Domaratzki, Michael; Harju, Tero et al

in International Journal of Computer Mathematics (2013), 90(6), 1171-1196

We consider a set of eight natural operations on formal languages (Kleene closure, positive closure, complement, prefix, suffix, factor, subword, and reversal), and compositions of them. If x and y are ... [more ▼]

We consider a set of eight natural operations on formal languages (Kleene closure, positive closure, complement, prefix, suffix, factor, subword, and reversal), and compositions of them. If x and y are compositions, we say x is equivalent to y if they have the same effect on all languages L. We prove that the number of equivalence classes of these eight operations is finite. This implies that the orbit of any language L under the elements of the monoid is finite and bounded, independently of L. This generalizes previous results about complement, Kleene closure, and positive closure. We also estimate the number of distinct languages generated by various subsets of these operations. [less ▲]

Detailed reference viewed: 23 (5 ULg)
Full Text
Peer Reviewed
See detailAbelian primitive words
Domaratzki, Michael; Rampersad, Narad ULg

in Mauri, Giancarlo; Leporati, Alberto (Eds.) DLT 2011 - Developments in Language Theory (2011)

We investigate Abelian primitive words, which are words that are not Abelian powers. We show that unlike classical primitive words, the set of Abelian primitive words is not context-free. We can determine ... [more ▼]

We investigate Abelian primitive words, which are words that are not Abelian powers. We show that unlike classical primitive words, the set of Abelian primitive words is not context-free. We can determine whether a word is Abelian primitive in linear time. Also different from classical primitive words, we find that a word may have more than one Abelian root. We also consider enumeration problems and the relation to the theory of codes. [less ▲]

Detailed reference viewed: 6 (0 ULg)