<p>Using BNF with your unique-repetition operator, <code>x := S^</code> says that an <code>x</code> is an instance <code>a</code> of symbol <code>S</code>, optionally followed by an instance <code>b</code> of set <code>S - a</code>, itself optionally followed by an instance <code>c</code> of set <code>S - a - b</code>, and so forth. If <code>|S|</code> is the number of possible <code>S</code>, and is finite, then <code>2 ^ |S|! - 1</code> is the number of possible <code>S^</code>.</p>

<p>It's not really meaningful to talk in terms of the <em>computational</em> power of the language being described, since this is about static semantics, in the twilight between syntax and ordinary (dynamic) semantics. The expressive power of the <em>grammar</em> is extended, since it has a formal means of expressing a particular type of input adaptation.</p>

<p>Specifically, it provides a means of accepting <em>a permutation of a subset</em> of a particular set. I don't think there is any existing name for this class of language. It's certainly not context-free, but the context requirement is at least pretty strictly controlled. If you need a term for it, just coin one. I suggest <em>context-respecting</em> for the class of languages that cannot be described by a context-free grammar without additional embedded information about static semantic constraints, which to be fair <em>are</em> vaguely syntactic in spirit.</p>

<p>The most useful application of this <em>particular</em> extension is probably just the ability to introduce unique-key constraints, but it also lets you describe such interesting sets as <code>x := [0-7]^</code>, which matches any octal number of 8 or fewer non-repeated digits. As for the complexity of it, determining whether an element of the set has been seen is no worse than logarithmic, and the frequency of checking is linear in the number of elements matched, so the <code>^</code> operator is indeed decidable in worst-case linearithmic time.</p>

CC BY-SA 2.5
2011-02-07T08:42:25.877Z
Thanks for the answer and for the hint to think in permutations of a subset. Although the unique-repetition operator does not catch key-value pairs with unique keys, the complexity should be the same for this cases. However, if I start to apply the operator on arbitrary structures, the class `S^` where `S` is some CFL may be get non-context-free because CFLs are not closed under difference. It should be doable if `S` is a regular language, but unfortunately you cannot decide whether a given CFL is regular. Maybe I'll raise another question as this is beyond the constraints of JSON and XML.
Jakob
CC BY-SA 2.5
2011-02-06T13:33:56.040Z
2011-02-06T13:33:56.040Z
Jon Purdy
<p><em>I moved <a href="https://stackoverflow.com/questions/3335026/which-formal-language-class-are-xml-and-json-with-unique-keys-they-are-not-conte">this question from stackoverflow</a> where id got no answers. We had a similar question <a href="https://cstheory.stackexchange.com/questions/3987/is-json-a-regular-language">whether JSON is regular</a></em>:</p>

<p>JSON and XML are both frequently called to be context-free languages - they are both specified mainly by a formal grammar in EBNF. However this is only true for JSON as defined in <a href="https://stackoverflow.com/questions/3335026/which-formal-language-class-are-xml-and-json-with-unique-keys-they-are-not-conte">RFC 4329, section 2.2</a> which does not require uniqueness of object keys (many may not know but {"a":1,"a":2} is valid JSON!). But if you require unique keys in JSON or <a href="https://cstheory.stackexchange.com/questions/3987/is-json-a-regular-language">unique attribute names in XML</a> this cannot be expressed by a context-free grammars. But which is the language class of JSON with unique keys and for well-formed XML (which implies unique attribute names?).</p>

<p>One of the best paper I found on this subject (Murato et al, 2001: <a href="http://www.cobase.cs.ucla.edu/tech-docs/dongwon/mura0619.pdf" rel="noreferrer">Taxonomy of XML Schema Languages using Formal Language Theory</a>) explicitly excludes integrity constraints such as keys/keyrefs and uniqueness to be checked on an additional layer. Beside this the subset of XML defined by an XML Schema or by a DTD is context-free. But not the full set of all well-formed XML documents.</p>

<p>I think a nested stack automaton (=indexed language) should be able to parse JSON with unique key constraint. For XML can simlify the question to the language S of all comma-separated lists of unique integers. Does anyone know more, preferably with citations?</p>

<p><strong>P.S:</strong> A simple algorithm to decide the languages (beside the context-free part) is based on a good sorting algorithm. Therefore it should be decidable in "linearithmic time" with O(n log n) worst case. I have not found out yet, whether the complexity class is for instance <em>"mildly context-sensitive"</em>, or <em>"indexed"</em> but probably something between context-free and context-sensitive (?).</p>

<p><strong>EDIT:</strong> Maybe I better reformulate the question for the more theoretical computer scientists. Given the class CFL of all languages that can be expressed by Backus-Naur-Form with repetition (<code>x := a+</code> <span class="math-container">$\Leftrightarrow$</span> <code>x := a | x a</code>). Now what do I gain in computational power if I introduce a "repetition with unique instances" operator <code>^</code>, so <code>a^</code> is a sequence of <code>a</code> where each element results in a different sequence of terminals?</p>

CC BY-SA 2.5
2011-01-31T14:26:28.750Z
JSON with repeatable object keys is context-free (see JSON grammar), but how do you express the unique key constraint in a common grammar or automaton? Or: Which complexity class belongs an XML parser to, if it can detect the set of all well-formed XML documents (well-formed implies unique attribute names per element).
Jakob
CC BY-SA 2.5
2011-01-31T14:55:43.630Z
Using compiler generator terms here. The respective *syntax* of both JSON and XML is certainly context-free. Properties like unique identifiers or value type restrictions are *static semantics* (some people call this syntax, too, but I reject that nomenclature for several reasons). Parser generators usually allow you to enrich a common parser by things like *syntactic/semantic predicates* that need not be context-free. In theory, *attributed grammars* are used. I don't know wether such features can be naturally expressed with formal grammars of any power.
Raphael
CC BY-SA 2.5
2011-01-31T15:38:57.793Z
Which parts of a *formal* language goes beyond syntax, depends on the viewpoint. Simple nested structures like XML and JSON can be parsed by a pushdown automaton. I just want to know, which computable power you get, if the automaton is enriched with a dictionary to look up whether a stored value has been read before, to ensure the uniqueness constraint. I'd guess its an indexed grammar (a nested stack automaton?) but there are several kinds of indexed grammars.
Jakob
CC BY-SA 2.5
2011-01-31T17:09:28.743Z
@Jakob, I'd fold this discussion (abbreviated) into the question so it's clear exactly what you're asking
Suresh Venkat
CC BY-SA 2.5
2011-02-01T09:31:40.783Z
An LBA should be sufficient since you will never have to store more identifiers than you have characters in your text. I do not know enough about classes between CFL and CSL to be of help there.
Raphael
CC BY-SA 2.5
2011-02-02T16:21:01.043Z
JSON is perfectly valid javascript, even with non-unique keys (just tried it, the key takes on the last value listed).  What do you mean by "which formal language"?  Isn't JSON and XML which unique keys technically the same language as JSON and XML without unique keys?
Neil
CC BY-SA 2.5
2011-02-02T23:16:31.123Z
`{'a':1,'a:'2}` is valid JSON (1), but not valid JSON-with-unique-keys (2), so (1) and (2) cannot be the same same language. I am looking for a formal description of the unique-keys constraint and its computational complexity in terms of formal languages.
Jakob
CC BY-SA 2.5
2011-02-03T00:06:27.930Z
In the last edit, “where each element results in a difference sequence of non-terminals”: Did you mean “terminals” where you wrote “non-terminals”?  (And “difference sequence” must be a typo for “different sequence.”)
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-03T08:53:22.357Z
I'm not an expert on the subject ... but I think that in order to achieve the "unique key constraint" a linear indexed grammar is not enough, because the stack can be filled only with terminal symbols, and with push/pop you cannot produce a sequence of unique identifiers (you cannot "count" ... even in unary). And I'm not sure that even a CSL is enough ... perhaps you need RE.
Marzio De Biasi
CC BY-SA 2.5
2011-02-03T13:30:02.697Z
@Tsuyoshi Ito: thanks, I fixed the typo. However I found that even a "repetition with unique instances" operator cannot guarantee uniqueness of keys in key-value pairs. It would only catch `{'x':1,'x':1}` but not `{'x':1,'x':2}`.
Jakob
CC BY-SA 2.5
2011-02-03T19:58:54.337Z
Ah, I see.  Thanks for the follow-up.  But then, if I understand it correctly, your last edit is not a “reformulation” and solving it will not answer your original question.  If this is the case, I think that it is better to edit the question to clarify the connection between the two problems (or simply remove this reformulation if you are not interested in it).
Tsuyoshi Ito
<fl.formal-languages>
Which formal language class are XML and JSON with unique keys?
Jakob
# Which formal language class are XML and JSON with unique keys?

(Asked by: username_0 on 2011-01-31)

*I moved [this question from stackoverflow](https://stackoverflow.com/questions/3335026/which-formal-language-class-are-xml-and-json-with-unique-keys-they-are-not-conte) where id got no answers. We had a similar question [whether JSON is regular](https://cstheory.stackexchange.com/questions/3987/is-json-a-regular-language)*:

JSON and XML are both frequently called to be context-free languages - they are both specified mainly by a formal grammar in EBNF. However this is only true for JSON as defined in [RFC 4329, section 2.2](https://stackoverflow.com/questions/3335026/which-formal-language-class-are-xml-and-json-with-unique-keys-they-are-not-conte) which does not require uniqueness of object keys (many may not know but {"a":1,"a":2} is valid JSON!). But if you require unique keys in JSON or [unique attribute names in XML](https://cstheory.stackexchange.com/questions/3987/is-json-a-regular-language) this cannot be expressed by a context-free grammars. But which is the language class of JSON with unique keys and for well-formed XML (which implies unique attribute names?).

One of the best paper I found on this subject (Murato et al, 2001: [Taxonomy of XML Schema Languages using Formal Language Theory](http://www.cobase.cs.ucla.edu/tech-docs/dongwon/mura0619.pdf)) explicitly excludes integrity constraints such as keys/keyrefs and uniqueness to be checked on an additional layer. Beside this the subset of XML defined by an XML Schema or by a DTD is context-free. But not the full set of all well-formed XML documents.

I think a nested stack automaton (=indexed language) should be able to parse JSON with unique key constraint. For XML can simlify the question to the language S of all comma-separated lists of unique integers. Does anyone know more, preferably with citations?

**P.S:** A simple algorithm to decide the languages (beside the context-free part) is based on a good sorting algorithm. Therefore it should be decidable in "linearithmic time" with O(n log n) worst case. I have not found out yet, whether the complexity class is for instance *"mildly context-sensitive"*, or *"indexed"* but probably something between context-free and context-sensitive (?).

**EDIT:** Maybe I better reformulate the question for the more theoretical computer scientists. Given the class CFL of all languages that can be expressed by Backus-Naur-Form with repetition (`x := a+` $\Leftrightarrow$ `x := a | x a`). Now what do I gain in computational power if I introduce a "repetition with unique instances" operator `^`, so `a^` is a sequence of `a` where each element results in a different sequence of terminals?

**Tags:** fl.formal-languages
> **Comments:**
> **username_0**: JSON with repeatable object keys is context-free (see JSON grammar), but how do you express the unique key constraint in a common grammar or automaton? Or: Which complexity class belongs an XML parser to, if it can detect the set of all well-formed XML documents (well-formed implies unique attribute names per element).  
> **username_1**: Using compiler generator terms here. The respective *syntax* of both JSON and XML is certainly context-free. Properties like unique identifiers or value type restrictions are *static semantics* (some people call this syntax, too, but I reject that nomenclature for several reasons). Parser generators usually allow you to enrich a common parser by things like *syntactic/semantic predicates* that need not be context-free. In theory, *attributed grammars* are used. I don't know wether such features can be naturally expressed with formal grammars of any power.  
> **username_0**: Which parts of a *formal* language goes beyond syntax, depends on the viewpoint. Simple nested structures like XML and JSON can be parsed by a pushdown automaton. I just want to know, which computable power you get, if the automaton is enriched with a dictionary to look up whether a stored value has been read before, to ensure the uniqueness constraint. I'd guess its an indexed grammar (a nested stack automaton?) but there are several kinds of indexed grammars.  
> **username_2**: @Jakob, I'd fold this discussion (abbreviated) into the question so it's clear exactly what you're asking  
> **username_1**: An LBA should be sufficient since you will never have to store more identifiers than you have characters in your text. I do not know enough about classes between CFL and CSL to be of help there.  
> **username_3**: JSON is perfectly valid javascript, even with non-unique keys (just tried it, the key takes on the last value listed).  What do you mean by "which formal language"?  Isn't JSON and XML which unique keys technically the same language as JSON and XML without unique keys?  
> **username_0**: `{'a':1,'a:'2}` is valid JSON (1), but not valid JSON-with-unique-keys (2), so (1) and (2) cannot be the same same language. I am looking for a formal description of the unique-keys constraint and its computational complexity in terms of formal languages.  
> **username_4**: In the last edit, “where each element results in a difference sequence of non-terminals”: Did you mean “terminals” where you wrote “non-terminals”?  (And “difference sequence” must be a typo for “different sequence.”)  
> **username_5**: I'm not an expert on the subject ... but I think that in order to achieve the "unique key constraint" a linear indexed grammar is not enough, because the stack can be filled only with terminal symbols, and with push/pop you cannot produce a sequence of unique identifiers (you cannot "count" ... even in unary). And I'm not sure that even a CSL is enough ... perhaps you need RE.  
> **username_0**: @Tsuyoshi Ito: thanks, I fixed the typo. However I found that even a "repetition with unique instances" operator cannot guarantee uniqueness of keys in key-value pairs. It would only catch `{'x':1,'x':1}` but not `{'x':1,'x':2}`.  
> **username_4**: Ah, I see.  Thanks for the follow-up.  But then, if I understand it correctly, your last edit is not a “reformulation” and solving it will not answer your original question.  If this is the case, I think that it is better to edit the question to clarify the connection between the two problems (or simply remove this reformulation if you are not interested in it).  

---

## 1 answers

### Answer by username_6 on 2011-02-06. Score: 7 | Accepted answer

Using BNF with your unique-repetition operator, `x := S^` says that an `x` is an instance `a` of symbol `S`, optionally followed by an instance `b` of set `S - a`, itself optionally followed by an instance `c` of set `S - a - b`, and so forth. If `|S|` is the number of possible `S`, and is finite, then `2 ^ |S|! - 1` is the number of possible `S^`.

It's not really meaningful to talk in terms of the *computational* power of the language being described, since this is about static semantics, in the twilight between syntax and ordinary (dynamic) semantics. The expressive power of the *grammar* is extended, since it has a formal means of expressing a particular type of input adaptation.

Specifically, it provides a means of accepting *a permutation of a subset* of a particular set. I don't think there is any existing name for this class of language. It's certainly not context-free, but the context requirement is at least pretty strictly controlled. If you need a term for it, just coin one. I suggest *context-respecting* for the class of languages that cannot be described by a context-free grammar without additional embedded information about static semantic constraints, which to be fair *are* vaguely syntactic in spirit.

The most useful application of this *particular* extension is probably just the ability to introduce unique-key constraints, but it also lets you describe such interesting sets as `x := [0-7]^`, which matches any octal number of 8 or fewer non-repeated digits. As for the complexity of it, determining whether an element of the set has been seen is no worse than logarithmic, and the frequency of checking is linear in the number of elements matched, so the `^` operator is indeed decidable in worst-case linearithmic time.

> **Comments:**
> **username_0**: Thanks for the answer and for the hint to think in permutations of a subset. Although the unique-repetition operator does not catch key-value pairs with unique keys, the complexity should be the same for this cases. However, if I start to apply the operator on arbitrary structures, the class `S^` where `S` is some CFL may be get non-context-free because CFLs are not closed under difference. It should be doable if `S` is a regular language, but unfortunately you cannot decide whether a given CFL is regular. Maybe I'll raise another question as this is beyond the constraints of JSON and XML.  

---

