Message-Id: <9107081447.AA26127@relay2.UU.NET>
From: cbmvax!uunet!ctr.columbia.edu!shoulson
Date: Mon Jul  8 13:46:23 1991
To: cbmvax!snark.thyrsus.com!lojbab
Cc: lojban-list@snark.thyrsus.com
In-Reply-To: Bob LeChevalier's message of Mon, 8 Jul 91 02:14 EDT <m0jwork-00037yC@snark.thyrsus.com>
Subject: Jeff Prothero on elidable terminators issue from before LogFest
Status: RO

I thought I had a counter-example, but it may run afoul of some conditions
in the proof.  I'm going to send it out anyway, so you all can think about
it.

Consider the language:

A --> e | < A > | < A A >    (e is the empty string)

Now, we can obviously derive strings (1) <<<><>>> and (2) <<<>><>> from
this.  Now, eliding the last two rightbrackets from (1), we get <<<><>.
This is probably legal, though the "not the prefix of any string"
restriction probably cuts me down.  We can also elide the last and
second-to-last rightbracket in (2), yielding <<<><>, the same string.

I noticed this when constructing a tanru, using ke/ke'e brackets.
Basically, the problem is possible ambiguity between ((A(B))) and ((A)(B)).
If you elide all the closing braces from both, you get the same string.

I'm pretty sure you're restriction avoids such a mess, but it's something
to consider.  I mean,

broda ke brode ke brodo brodu

is taken to mean

broda ke brode ke brodo brodu ke'e ke'e

But *could* mean

broda ke brode ke'e ke brodo brodu ke'e  (though why you'd want to is beyond
me)

Simple pragmatics could rule out the latter reading, as could precedence
rules which determine how and when to elide and how to replace terminators.
But it doesn't seem so simple as many think it.  In the tanru examples, I
doubt anyone would deny that the terminators are elidable, but I can't see
how the elided version precludes the second reading without some additional
rules.

This is probably no big deal, as I think I just missed a rule someplace.

~mark