The search session has expired. Please query the service again.

All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Previous Page 21

Displaying 401 – 408 of 408

Showing per page

Well quasi-orders, unavoidable sets, and derivation systems

Flavio D'Alessandro, Stefano Varricchio (2006)

RAIRO - Theoretical Informatics and Applications

Let I be a finite set of words and ⇒ I * be the derivation relation generated by the set of productions {ε → u | u ∈ I}. Let L I ϵ be the set of words u such that ϵ ⇒ I * u . We prove that the set I is unavoidable if and only if the relation ⇒ I * is a well quasi-order on the set L I ϵ . This result generalizes a theorem of [Ehrenfeucht et al.,Theor. Comput. Sci.27 (1983) 311–332]. Further generalizations are investigated.

Words over an ordered alphabet and suffix permutations

Jean-Pierre Duval, Arnaud Lefebvre (2002)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Given an ordered alphabet and a permutation, according to the lexicographic order, on the set of suffixes of a word w , we present in this article a linear time and space method to determine whether a word w ' has the same permutation on its suffixes. Using this method, we are then also able to build the class of all the words having the same permutation on their suffixes, first of all the smallest one. Finally, we note that this work can lead to a method for generating a Lyndon word randomly in linear...

Words over an ordered alphabet and suffix permutations

Jean-Pierre Duval, Arnaud Lefebvre (2010)

RAIRO - Theoretical Informatics and Applications

Given an ordered alphabet and a permutation, according to the lexicographic order, on the set of suffixes of a word w, we present in this article a linear time and space method to determine whether a word w' has the same permutation on its suffixes. Using this method, we are then also able to build the class of all the words having the same permutation on their suffixes, first of all the smallest one. Finally, we note that this work can lead to a method for generating a Lyndon word...

Currently displaying 401 – 408 of 408

Previous Page 21