Let I be a finite set of words and ⇒I* be the derivation relation generated by the set of productions {ε → u | u ∈ I}. Let LI ε 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 LI ε. This result generalizes a theorem of [7]. Further generalizations are investigated. © Springer-Verlag Berlin Heidelberg 2004.
Avoidable sets and well quasi orders / D'Alessandro, Flavio; Varricchio, S.. - STAMPA. - 3340:(2004), pp. 139-150. (Intervento presentato al convegno DLT 2004 tenutosi a DEVELOPMENTS IN LANGUAGE THEORY, AUCKLAND, NEW ZELAND).
Avoidable sets and well quasi orders
D'ALESSANDRO, Flavio;
2004
Abstract
Let I be a finite set of words and ⇒I* be the derivation relation generated by the set of productions {ε → u | u ∈ I}. Let LI ε 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 LI ε. This result generalizes a theorem of [7]. Further generalizations are investigated. © Springer-Verlag Berlin Heidelberg 2004.File allegati a questo prodotto
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
