ON THE AVERAGE MINIMAL PREFIX-LENGTH OF THE GENERALIZED SEMI-DYCKLANGUAGE

摘要

Given two disjoint alphabets T_[ and T_] and a relation R is contained in T_[ x T_], the "generalized semi-Dycklanguage " D~R over T_[ ∪ T_] consists of all words ω ∈ (T_[ ∪ T_])~* which are equivalent to the empty word under the congruence δ defined by xy ≡ ε mod δ for all (x, y) ∈ R. For arbitrary R, we compute the average length of the shortest prefix which has to be read in order to decide whether or not a given word of length n over (T_[ ∪ T_])~* belongs to D~R.%Étant donnés deux alphabets disjoints T_[ et T_] et une relation R is contained in T_[ x T_], le « langage de semi-Dyck généralisé » D~R sur T_[ ∪ T_] est composé des mots ω ∈ (T_[ ∪ T_])~* qui sont équivalents au mot vide pour la congruence δ définie par xy ≡ ε mod δ pour tout (x, y) ∈ R. Pour tout R, nous calculons la longueur moyenne du plus court préfixe d'un mot de longueur n sur (T_[ ∪ T_])~* qu'il faut lire pour décider si ce mot appartient ou non au langage D~R.