Qual classe de linguagem formal é XML e JSON com chaves exclusivas?

Eu mudei essa pergunta do stackoverflow onde o id não obteve respostas. Tivemos uma pergunta semelhante se o JSON é regular :

JSON e XML são freqüentemente chamados de linguagens livres de contexto - ambos são especificados principalmente por uma gramática formal no EBNF. No entanto, isso é válido apenas para JSON, conforme definido na RFC 4329, seção 2.2, que não requer exclusividade de chaves de objeto (muitos podem não saber, mas {"a": 1, "a": 2} é JSON válido!). Mas se você precisar de chaves exclusivas em JSON ou nomes de atributos exclusivos em XML, isso não poderá ser expresso por gramáticas livres de contexto. Mas qual é a classe de linguagem do JSON com chaves exclusivas e para XML bem formado (o que implica nomes de atributos exclusivos?).

Um dos melhores artigos que encontrei sobre esse assunto (Murato et al., 2001: Taxonomia das Linguagens de Esquema XML usando a Teoria da Linguagem Formal ) exclui explicitamente restrições de integridade, como chaves / referências de chave e exclusividade, a serem verificadas em uma camada adicional. Além disso, o subconjunto de XML definido por um esquema XML ou por uma DTD é livre de contexto. Mas não o conjunto completo de todos os documentos XML bem formados.

Eu acho que um autômato de pilha aninhada (= linguagem indexada) deve ser capaz de analisar o JSON com restrição de chave exclusiva. Para XML, pode simular a pergunta na linguagem S de todas as listas separadas por vírgula de números inteiros exclusivos. Alguém sabe mais, de preferência com citações?

PS: Um algoritmo simples para decidir as linguagens (além da parte livre de contexto) é baseado em um bom algoritmo de classificação. Portanto, deve ser decidido em "tempo linearitmico" com O (n log n) no pior caso. Ainda não descobri se a classe de complexidade é, por exemplo, "levemente sensível ao contexto" ou "indexada", mas provavelmente algo entre livre de contexto e sensível ao contexto (?).

Edição: Talvez seja melhor reformular a questão para os cientistas da computação mais teóricos. Dada a classe CFL de todos os idiomas que podem ser expressos por Backus-Naur-Form com repetição ( ). Agora, o que ganho em poder computacional se introduzir um operador de "repetição com instâncias únicas" , assim é uma sequência em que cada elemento resulta em uma sequência diferente de terminais?x := a+ $\Leftrightarrow$ x := a | x a^a^a

O uso do BNF com seu operador de repetição exclusiva x := S^diz que an xé uma instância ado símbolo S, opcionalmente seguida por uma instância bdo conjunto S - a, ela própria opcionalmente seguida por uma instância cdo conjunto S - a - be assim por diante. Se |S|é o número de possíveis Se é finito, então 2 ^ |S|! - 1é o número de possíveis S^.

Não é realmente significativo falar em termos do poder computacional da linguagem que está sendo descrita, já que se trata de semântica estática, no crepúsculo entre a sintaxe e a semântica comum (dinâmica). O poder expressivo da gramática é estendido, pois possui um meio formal de expressar um tipo particular de adaptação de entrada.

Especificamente, fornece um meio de aceitar uma permutação de um subconjunto de um conjunto específico. Eu não acho que exista um nome para essa classe de linguagem. Certamente não é livre de contexto, mas o requisito de contexto é pelo menos bastante estritamente controlado. Se você precisar de um termo, basta inventar um. Sugiro respeito ao contexto para a classe de linguagens que não pode ser descrita por uma gramática livre de contexto sem informações adicionais incorporadas sobre restrições semânticas estáticas, as quais, para serem justas, são vagamente sintáticas em espírito.

A aplicação mais útil dessa extensão específica é provavelmente apenas a capacidade de introduzir restrições de chave exclusiva, mas também permite descrever conjuntos interessantes como x := [0-7]^, que correspondem a qualquer número octal de 8 ou menos dígitos não repetidos. Quanto à complexidade, determinar se um elemento do conjunto foi visto não é pior que logarítmico, e a frequência da verificação é linear no número de elementos correspondentes, de modo que o ^operador é realmente decidível no pior momento linearitêmico.