From nobody@digitalkingdom.org Tue Feb 10 04:11:18 2009 Received: with ECARTIS (v1.0.0; list lojban-list); Tue, 10 Feb 2009 04:11:19 -0800 (PST) Received: from nobody by chain.digitalkingdom.org with local (Exim 4.69) (envelope-from ) id 1LWrSM-0003Cp-GZ for lojban-list-real@lojban.org; Tue, 10 Feb 2009 04:11:18 -0800 Received: from qw-out-1920.google.com ([74.125.92.150]) by chain.digitalkingdom.org with esmtp (Exim 4.69) (envelope-from ) id 1LWrSG-0003CR-Uo for lojban-list@lojban.org; Tue, 10 Feb 2009 04:11:14 -0800 Received: by qw-out-1920.google.com with SMTP id 14so114225qwa.58 for ; Tue, 10 Feb 2009 04:11:07 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:mime-version:received:in-reply-to:references :date:message-id:subject:from:to:content-type :content-transfer-encoding; bh=CnuKkEff49hp/R7+xpsamq5Ujp63bERJjWSqG7FrUrM=; b=T0g9vG+p0ZtDjBkcZ/GufOcI3RJwYaE+L9NMNHc47F4J3ak0pKSZqjA6BNjv4Gluj1 kPuKW/FdBgiPrq7sdLva1SAGZaEyQBWCSBVB6dFeSL0scuNBfMVw91EqscBXzRHKMmO3 4j/l86MSEgscC0KHYOVJUTPJzqRoPWrfOWZ38= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :content-type:content-transfer-encoding; b=l1jUYtVMa3L0n4a2FYtNrZgzSGp/8XXVGqmTmVizwQW5g8NVm30UMX74JVCi3Fkzxu HZk+75E1lLj+5wGjBD9nc1saHSEr/hGidsXWDpZJq059/Lx6F6sfIFe/TpRl5HP5uSOl 0FQxicjWn3rly4jwT7qOtENvTN026hEnFSV34= MIME-Version: 1.0 Received: by 10.229.96.6 with SMTP id f6mr1954981qcn.81.1234267867797; Tue, 10 Feb 2009 04:11:07 -0800 (PST) In-Reply-To: <737b61f30902091642h7e41234ufc1bdd8e7ddb5f6c@mail.gmail.com> References: <737b61f30902081336g2818a979sf6a6db307e512c75@mail.gmail.com> <925d17560902091531k16bf93efk7113996d5f786767@mail.gmail.com> <737b61f30902091642h7e41234ufc1bdd8e7ddb5f6c@mail.gmail.com> Date: Tue, 10 Feb 2009 09:11:07 -0300 Message-ID: <925d17560902100411mc814179h1930114009ce8641@mail.gmail.com> Subject: [lojban] Re: CFG prize challenge question From: =?ISO-8859-1?Q?Jorge_Llamb=EDas?= To: lojban-list@lojban.org Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by Ecartis X-Spam-Score: -0.0 X-Spam-Score-Int: 0 X-Spam-Bar: / X-archive-position: 15285 X-ecartis-version: Ecartis v1.0.0 Sender: lojban-list-bounce@lojban.org Errors-to: lojban-list-bounce@lojban.org X-original-sender: jjllambias@gmail.com Precedence: bulk Reply-to: lojban-list@lojban.org X-list: lojban-list On Mon, Feb 9, 2009 at 9:42 PM, Chris Capel wrote: > On Mon, Feb 9, 2009 at 17:31, Jorge Llambías wrote: >> By "blowup" you mean the number of rules increases exponentially with >> the number of terminators, right? > > Well, more like with the number of allowable parent-child phrase > relationships. E.g., you can nest a sumti in a selbri, so that's one. Do you mean things like "ME sumti MEhU" or "BRIVLA BE sumti BEhO"? I'm still not clear what a "phrase" is here. > You can put a selbri in a bridi, so that's two. You can put a TO-TOI > in lots of places, so that's like ten more. Etc. And I don't assert > that the blowup is exponential--I'd sooner believe it's polynomial. > But either way I'm really not to sure how to go about *proving* it. The number of nestings allowed is already infinite with terminators. It doesn't increase when terminators can be elided. >>> The set of valid phrases to be parsed, P, is a set of lists of tokens. >> >> First question: Do I understand correctly that a phrase is something >> like "KOhA BRODA LE BRODA KU VAU"? > > Well, I'm thinking more abstractly. I don't think KOhA has a > terminator, so I'm just assuming that kind of word is irrelevant. And > I'm representing all terminators, so I think you'd need "BRODA LE > BRODA VAU KU VAU". But that's basically it. (Actually, the first VAU doesn't go there, VAU terminates a bridi-tail, not a selbri. A selbri doesn't have a terminator.) >> The number of valid (and finite) such phrases with non-elidable >> terminators is countably infinite, and so is the number with elidable >> terminators. There is no blowup there. It is the number of rules, >> things like "sumti = LE selbri KU", which is finite, that probably >> blows up. > > That's the idea. But do "LE ME KOhA MEhU KU" and "LE NU BRODA KEI KU" count as the same phrase or different phrases? They are both "sumti = LE selbri KU". I'm still not sure what you are counting as a "phrase". >> Or is a phrase something like "LE selbri KU", where "selbri" is one of >> its tokens? > > A selbri has internal structure, including some terminators (I > believe) so it would be represented as various phrase types. "various" or "infinite"? A selbri can have an infinite number of terminators nested inside. It doesn't have any terminator of its own. >> Is "GI NAI" a phrase? It is not by itself "valid" as in a >> valid text to be parsed, but there is a rule "gik = GI NAI". > > I don't think NAI is really a terminator, so "GI NAI" wouldn't be > represented in my formalism. Right, NAI is not a terminator. So a "phrase" is anything that has a terminator? Do "PA BOI" and "PA PA BOI" count as different phrases? >>> There are two types of tokens: start and terminator. Each token is >>> paired with a number identifying the type of phrase it starts or >>> terminates. >> >> What are the types of phrases? Can you give some examples of tokens, >> some examples of phrases, and some examples of types of phrases? > > The concrete syntax I've been using is as follows: "(x" is a start > token of type x, ")x" is a terminator token, non-elided, and "_)x" is > an elided terminator. So an example phrase would be > > (1 (2 (3 (4 )4 _)3 _)2 (3 )3 )1 > > This phrase is invalid, because of the second 3 phrase. Since the 2 > terminator is elided, the second 3 phrase would have to be grouped > under the 2 phrase after the first 3 phrase. In other words, if you > removed the elided terminators and reconstructed them, the 2 > terminator would go after the second 3 phrase. How can you tell that the second 3 phrase can be grouped under the 2 phrase? How can you tell it can't be grouped under the first 3 phrase? > I think you can see how a unique number could be assigned to each > selma'o that starts a terminable phrase, and the allowed nestings > declared as assumptions about the mapPhPh function, to make a mapping > between lojban and the formalism. Not all terminators are coupled with fixed "starter" selmaho, and some terminators can terminate different structures. This may or may not be relevant, I'm still not sure I see how this formalism works. mu'o mi'e xorxes To unsubscribe from this list, send mail to lojban-list-request@lojban.org with the subject unsubscribe, or go to http://www.lojban.org/lsg2/, or if you're really stuck, send mail to secretary@lojban.org for help.