FREE SHIPPING. 24/7 CUSTOMER SERVICE. ALL THRONES SHIP WITHIN 7 DAYS.

Nested Words

Quels sont les mots imbriqués?
Mots imbriqués est un modèle pour la représentation de données avec un ordre linéaire et une correspondance hiérarchique imbriquée d'éléments. Des exemples de données avec une telle structure hiérarchique linéaire double comprennent des exécutions de programmes structurés, des données linguistiques annotées et des documents HTML / XML. Un mot imbriqué consiste en une séquence de positions ordonnées linéairement, complétée par des arêtes imbriquées reliant les appels aux retours (ou les balises ouvertes aux balises fermées). Les arêtes ne se croisent pas pour créer une structure hiérarchique correctement imbriquée et nous permettons à certaines arêtes d'être en attente. Cette structure d'imbrication peut être représentée de manière unique par une séquence spécifiant les types de positions (appels, retours et internes). Les mots imbriqués généralisent les mots et les arbres ordonnés et permettent les opérations sur les mots et sur les arbres.
Mots imbriqués automates - accepteurs à états finis pour mots imbriqués, définissent la classe des langages normaux des mots imbriqués. Cette classe possède toutes les propriétés théoriques attrayantes dont jouissent les langages de mots classiques classiques: les automates de mots imbriqués déterministes sont aussi expressifs que leurs équivalents non déterministes; la classe est fermée sous l'union, l'intersection, la complémentation, la concaténation, le Kleene- *, les préfixes et les homomorphismes de langage; l'appartenance, la vacuité, l'inclusion linguistique et l'équivalence linguistique sont décidables; et la définissabilité dans la logique monadique du second ordre correspond exactement à la reconnaissabilité à l'état fini. Ces résultats généralisent également à l'infini des mots imbriqués.

Comment se rapportent-ils aux langages de mots sans contexte?
Étant donné une langue L de mots imbriqués sur un alphabet, le codage linéaire des mots imbriqués donne une langue L 'sur l'alphabet étiqueté constitué de symboles étiquetés avec le type de position. Si L est le langage courant des mots imbriqués, alors L 'est dépourvu de contexte. En fait, l'automate à pile acceptant L 'a une structure particulière: lors de la lecture d'un appel, l'automate doit appuyer sur un symbole, lors de la lecture d'un symbole de retour, il doit faire apparaître un symbole (si la pile est non vide), et lors de la lecture un symbole interne, il ne peut que mettre à jour son état de contrôle. Nous appelons ces automates de manière visible des automates à pile et la classe de langages de mots qu'ils acceptent (VPL). Puisque nos automates peuvent être déterminés, les VPL correspondent à une sous-classe de langages déterministes sans contexte (DCFL). Les VPL généralisent les langages de parenthèse, les langages entre crochets et les langages équilibrés, et ils ont de meilleures propriétés de fermeture que les LFC, les DCFL ou les langages de paranthèse.
Nous soutenons que pour la vérification algorithmique de programmes structurés, au lieu de le voir comme un langage dépourvu de contexte, il convient de le voir comme un langage ordinaire de mots imbriqués (ou de manière équivalente, un langage visiblement compressif), ce qui permettrait vérification de nombreuses propriétés (telles que l'inspection de pile, les conditions pré-post) qui ne sont pas exprimables dans les logiques de spécification existantes.

En général, les automates à pile remplissent deux fonctions distinctes: découvrir la correspondance hiérarchique et traiter / interroger la correspondance. Dans les applications où seul le second objectif est pertinent (comme dans l'analyse de programme), on peut remplacer les automates à pile par des NWA avec de nombreux avantages.

Comment se rapportent-ils aux arbres commandés?
Les données à double structure hiérarchique linéaire sont traditionnellement modélisées à l'aide de données binaires et, plus généralement, à l'aide d'arbres ordonnés non classés et interrogées à l'aide d'automates d'arbres. Dans les arborescences ordonnées, les nœuds avec le même parent sont ordonnés de manière linéaire et les traversées d'arborescences classiques telles que infixe (ou profondeur-première gauche à droite) peuvent être utilisées pour définir un ordre implicite de tous les nœuds. Il s’avère que les haies, dans lesquelles une haie est une séquence d’arbres ordonnés, constituent une classe spéciale de mots imbriqués, à savoir ceux correspondant aux mots de Dyck, et les langues de haie ordinaires correspondent à des langues équilibrées.
Pour le traitement de documents, les mots imbriqués présentent de nombreux avantages par rapport aux arbres ordonnés. La représentation basée sur une arborescence suppose implicitement que les données linéaires en entrée peuvent être analysées dans une arborescence. Il est donc impossible de représenter et de traiter des données qui peuvent ne pas être analysées correctement. Les opérations sur les mots, telles que les préfixes, les suffixes et la concaténation, bien qu'elles soient naturelles pour le traitement de documents, n'ont pas d'opérations arborescentes analogues. Deuxièmement, les automates arborescents peuvent naturellement exprimer des contraintes sur la séquence d'étiquettes le long d'un chemin hiérarchique, ainsi que le long des frères et sœurs de gauche à droite, mais elles ont du mal à capturer les contraintes faisant référence à l'ordre linéaire global. Par exemple, la requête que les modèles p1, ... pk apparaissent dans le document dans cet ordre est compilée en un automate de mots déterministe (et donc une NWA déterministe) de taille linéaire, mais un automate d'arbre déterministe standard pour cette requête doit être de taille exponentielle en k. Les RNF peuvent être considérées comme une sorte d’automates arborescents, de sorte que les automates ascendants ascendants et descendants sont des cas particuliers. Ces résultats impliquent qu’une requête peut être codée de manière plus succincte dans la vue Mots imbriqués avec des avantages en termes de complexité.