Dominance Languages are not Semilinear

A point mentioned by Bruno Guillaume during a conversation about Interaction Grammars (Perrier, 2004) some time ago. Looking at Hopcroft and Pansiot (1979)'s VASS, it turns out that Interaction Grammars is not the only dominance formalism that derives non semilinear sets.

Non Semilinearity

An interesting consequence of the equivalence of Rambow (1994)'s {}-LIGs with de Groote et al. (2004)'s VATAs is that the former generate some non semilinear sets. Indeed, VATAs generalize Hopcroft and Pansiot (1979)'s VASS, and we can very easily translate their example of a VASS with a non semilinear reachability set into a dominance grammar that generates a non semilinear language.

Hopcroft and Pansiot's three-dimensional VASS example (Lemma 2.8) follows, with two states A and B and (A,(0,0,1)) as initial configuration:

A → (A,(0,1,-1))
A → (B,(0,0,0))
B → (B,(0,-1,2))
B → (A,(1,0,0))

They prove that a configuration (A,(x₁,x₂,x₃)) is reachable if and only if 0 < x₂ + x₃ ≤ 2^x₁ holds.

The translation as a {}-LIG is rather immediate; we merely add the rules of T and U to consume the remaining indices and produce a and b symbols.

S → A {x₃}
A {x₃} → A {x₂}
A → B
B {x₂} → B {x₃,x₃}
B → A {x₁}
A → T
T {x₁} → a T
T → U
U {x₂} → b U | b
U {x₃} → b U | b

By Hopcroft and Pansiot's proof, the language of this grammar is

ℒ = { aⁿb^m | 0 ≤ n, 0 < m ≤ 2ⁿ }.

Rambow further provides the translation from {}-LIGs to weakly equivalent UVG-dls. The translation exploits a normal form for {}-LIGs; the translated grammar follows.

   S    S     A    A    A    A      T'   T      U'   U'
   |    |     |    |    |    |     / \   |     / \   |
   A    A     A'   A'   B    T    a   T  U    b   U  b
   :    :     :    :
   U    A'    U    B
   |    |     |    |
   U'   A     U'   B'


   B'   B'   B"   B"   B
   |    |    |    |    |
   B"   B"   B    B    A
   :    :    :    :    :
   U    A'   U    A'   T
   |    |    |    |    |
   U'   A    U'   A    T'

Consequences

UVG-dls are the simplest representatives of a number of dominance grammatical formalisms: GAG (Candito and Kahane, 1998), DSG (Rambow et al., 2001), (non-local) TDG (Kallmeyer, 1999), and Interaction Grammars (Perrier, 2004); their non semilinearity implies the non semilinearity of all those grammatical frameworks. This further justifies the substitutable notion in Rambow et al. (1995)'s original DTG definition, and the local restriction of TDG advocated by Kallmeyer to enforce semilinearity.

Semilinearity, or more exactly the (implied) constant growth property, is one of the characteristics often invoked for natural language syntax, and one of the three requirements for mild context sensitivity. Non semilinearity indicates that dominance grammars are probably more expressive than needed (or at least on this particular point). Nevertheless, all this should be taken with a grain of salt: ℒ still verifies the constant growth property, and mild context sensitivity is more of an empirical assessment than a real formal definition one should strictly adhere to.

Note that the semilinearity requisite has been challenged by an analysis of Old Georgian by Michaelis and Kracht (1997), but this analysis was in turn challenged by Bhatt and Joshi (2004).