Quelles classes de langage formel sont XML et JSON avec des clés uniques?

J'ai déplacé cette question de stackoverflow où id n'a obtenu aucune réponse. Nous avions une question similaire à savoir si JSON est régulier :

JSON et XML sont tous deux fréquemment appelés pour être des langages sans contexte - ils sont tous deux spécifiés principalement par une grammaire formelle dans EBNF. Cependant, cela n'est vrai que pour JSON tel que défini dans la RFC 4329, section 2.2, qui ne requiert pas l'unicité des clés d'objet (beaucoup ne le savent pas, mais {"a": 1, "a": 2} est un JSON valide!). Mais si vous avez besoin de clés uniques en JSON ou de noms d'attributs uniques en XML, cela ne peut pas être exprimé par des grammaires sans contexte. Mais quelle est la classe de langage de JSON avec des clés uniques et pour XML bien formé (ce qui implique des noms d'attribut uniques?).

L'un des meilleurs articles que j'ai trouvés à ce sujet (Murato et al, 2001: Taxonomy of XML Schema Languages ​​using Formal Language Theory ) exclut explicitement les contraintes d'intégrité telles que les clés / références de clés et l'unicité à vérifier sur une couche supplémentaire. À côté de cela, le sous-ensemble de XML défini par un schéma XML ou par une DTD est sans contexte. Mais pas l'ensemble complet de tous les documents XML bien formés.

Je pense qu'un automate de pile imbriqué (= langage indexé) devrait être capable d'analyser JSON avec une contrainte de clé unique. Car XML peut simplifier la question dans le langage S de toutes les listes séparées par des virgules d'entiers uniques. Quelqu'un en sait-il plus, de préférence avec des citations?

PS: Un algorithme simple pour décider des langues (à côté de la partie sans contexte) est basé sur un bon algorithme de tri. Par conséquent, il devrait être décidable en "temps linéithmique" avec le pire des cas O (n log n). Je n'ai pas encore découvert si la classe de complexité est par exemple "légèrement sensible au contexte" ou "indexée" mais probablement quelque chose entre sans contexte et sensible au contexte (?).

EDIT: Je ferais peut - être mieux de reformuler la question pour les informaticiens plus théoriques. Étant donné la classe CFL de toutes les langues qui peuvent être exprimées par Backus-Naur-Form avec répétition ( ). Maintenant, qu'est-ce que je gagne en puissance de calcul si j'introduis un opérateur "répétition avec des instances uniques" , est-ce donc une séquence où chaque élément se traduit par une séquence différente de terminaux?x := a+ $\Leftrightarrow$ x := a | x a^a^a

L'utilisation de BNF avec votre opérateur de répétition unique, x := S^indique que an xest une instance ade symbole S, éventuellement suivie d'une instance bde set S - a, elle-même éventuellement suivie d'une instance cde set S - a - b, etc. Si |S|est le nombre de possibles Set est fini, alors 2 ^ |S|! - 1est le nombre de possibles S^.

Il n'est pas vraiment significatif de parler en termes de puissance de calcul du langage décrit, car il s'agit de sémantique statique, dans le crépuscule entre la syntaxe et la sémantique ordinaire (dynamique). Le pouvoir expressif de la grammaire est étendu, car elle dispose d'un moyen formel d'exprimer un type particulier d'adaptation d'entrée.

Plus précisément, il fournit un moyen d'accepter une permutation d'un sous-ensemble d'un ensemble particulier. Je ne pense pas qu'il existe un nom existant pour cette classe de langue. Ce n'est certainement pas sans contexte, mais l'exigence de contexte est au moins assez strictement contrôlée. Si vous avez besoin d'un terme pour cela, il suffit d'en inventer un. Je suggère le respect du contexte pour la classe des langages qui ne peuvent pas être décrits par une grammaire hors contexte sans informations supplémentaires intégrées sur les contraintes sémantiques statiques, qui pour être justes sont vaguement syntaxiques dans l'esprit.

L'application la plus utile de cette extension particulière est probablement simplement la possibilité d'introduire des contraintes de clé unique, mais elle vous permet également de décrire des ensembles intéressants tels que x := [0-7]^, qui correspondent à n'importe quel nombre octal de 8 chiffres non répétés ou moins. Quant à la complexité de celui-ci, déterminer si un élément de l'ensemble a été vu n'est pas pire que logarithmique, et la fréquence de vérification est linéaire dans le nombre d'éléments appariés, de sorte que l' ^opérateur est effectivement décidable dans le pire des cas.