Copy Link
Add to Bookmark
Report
NL-KR Digest Volume 02 No. 55
NL-KR Digest (6/16/87 19:14:20) Volume 2 Number 55
Today's Topics:
Homomorphic grammars
Re: Conceptual Information Research
Re: Could X's inflection in [X (Y) Z] depend on the presense of Y?
----------------------------------------------------------------------
Date: Mon, 8 Jun 87 21:39 EDT
From: Frank Adams <franka@mmintl.UUCP>
Subject: Homomorphic grammars
Some time ago, I came up with a class of grammars which are intermediate in
strength between context free and context sensitive grammars. They seem to
me to be, in many ways, more appropriate for language representation than
either context free or context sensitive grammars.
As usual, we assume that a grammar has a collection of symbols, some
terminals and some non-terminals. One of the non-terminals is distingished
as the initial symbol. The grammar consists of a set of rules applied to
strings of symbols, generating new strings; the language generated is the
set of all strings which consist only of terminal symbols, and which can be
generated by repeated application of one or more of the rules to the string
consisting only of the initial symbol.
The most comprehensive class of homomorphic grammars are what I call
non-deterministic homomorphic grammars. In such a grammar, the rules have
the form of functions from the set of symbols for the grammar to sets of
strings. Applying a rule to a string consists of replacing each symbol in
the string by one of the strings in the set it maps to.
For example, the following is a homomorphic grammar for the class of all
strings of the form:
n n n
a b c ,
which is a classic example of a non-context sensitive language:
1) S |-> {ABC}
2) A |-> {Aa}, B |-> {Bb}, C |-> {Cc}
3) A |-> {^}, B |-> {^}, C |-> {^}
(I am using "^" to represent the empty string. Also, symbols not shown for
a function are mapped to themselves; in particular, rules (2) and (3) must
be regarded as containing the entries a |-> {a}, b |-> {b}, and c |-> {c}.)
This particular example is an example of a deterministic homomorphic
grammar, since each rule maps each symbol to a unique string. It is more
natural to define a deterministic homomorphic grammar as mapping symbols to
strings instead of sets of strings, but this is equivalent.
It is not too hard to show that any homomorphic grammar is equivalent to a
context sensitive grammar. It is known that any language which can be
generated by a non- deterministic Turing machine which is constrained to use
a tape no longer than the final result (but adding however many symbols are
desired) is context sensitive. Any intermediate state in the generation of
a string by a homomorphic grammar can be represented by a string of those
characters which will map to at least one character in the final result, and
a set of symbols which are present in the string at this stage, but which
will ultimately map to the null string. A Turing machine to implement this
is easily constructed. Q.E.D.
Homomorphic grammars can easily express such ideas as agreement of subject
and verb, or (with a little more difficulty) requiring every variable in a
program unit to be declared. They are also easily able to deal with the
phrase repeated twice, which provided the counter-example (that I know of)
to natural languages being context sensitive.
Mathematically, I know very little about these grammars. Certainly, every
context free grammar can be transformed into a non-deterministic homomorphic
grammar. I am not sure that the context free languages are a subset of the
deterministic homomorphic languages. I believe that the homomorphic
grammars are a proper subset of the context sensitive languagues, but I
can't prove it. (In particular, I think the set of all strings of the form
n1 n2 n3 nk
a ba ba ... ba , where the ni are all distinct, is not homomorphic.)
I also know nothing about how one might parse such languages. It feels like
it oughtn't to be hard, but I'm not certain.
Questions:
* Has anybody investigated grammars of this form? If so, what were their
results?
* Is there some relatively easy way to parse homomorphic grammars?
* Are these grammars adequate to parse natural languages? Does it make any
sense to do so?
--
Frank Adams ihnp4!philabs!pwa-b!mmintl!franka
Ashton-Tate 52 Oakland Ave North E. Hartford, CT 06108
------------------------------
Date: Thu, 11 Jun 87 12:40 EDT
From: M.BRILLIANT <marty1@houdi.UUCP>
Subject: Re: Homomorphic grammars
In article <2165@mmintl.UUCP>, franka@mmintl.UUCP (Frank Adams) writes:
> Some time ago, I came up with a class of grammars ....
>
> ..... The grammar consists of a set of rules applied to
> strings of symbols, generating new strings; the language generated is the
> set of all strings which consist only of terminal symbols, and which can be
> generated by repeated application of one or more of the rules ...
Sounds like Chomsky's transformational grammar, formalized. See his
"Syntactic Structures."
> * Has anybody investigated grammars of this form? If so, what were their
> results?
Transformational grammar looked good for a long time, but is not the
end of the road.
> * Is there some relatively easy way to parse homomorphic grammars?
I don't know.
> * Are these grammars adequate to parse natural languages? Does it make any
> sense to do so?
As far as I know, no known grammar is fully adequate to parse natural
languages,
M. B. Brilliant Marty
AT&T-BL HO 3D-520 (201)-949-1858
Holmdel, NJ 07733 ihnp4!houdi!marty1
------------------------------
Date: Sat, 13 Jun 87 00:39 EDT
From: Jeffrey Goldberg <goldberg@su-russell.ARPA>
Subject: Re: Homomorphic grammars
In article <2165@mmintl.UUCP> franka@mmintl.UUCP (Frank Adams) writes:
>The most comprehensive class of homomorphic grammars are what I call
>non-deterministic homomorphic grammars. In such a grammar, the rules have
>the form of functions from the set of symbols for the grammar to sets of
>strings. Applying a rule to a string consists of replacing each symbol in
>the string by one of the strings in the set it maps to.
>For example, the following is a homomorphic grammar for the class of all
>strings of the form:
> n n n
>a b c ,
>which is a classic example of a non-context sensitive language:
^^^^^^^^^
FREE
It is a context sensitive language, but not context-free
(henceforth CSL and CFL, or CSPSG and CFPSG).
>1) S |-> {ABC}
>2) A |-> {Aa}, B |-> {Bb}, C |-> {Cc}
>3) A |-> {^}, B |-> {^}, C |-> {^}
>(I am using "^" to represent the empty string. Also, symbols not shown for
>a function are mapped to themselves; in particular, rules (2) and (3) must
>be regarded as containing the entries a |-> {a}, b |-> {b}, and c |-> {c}.)
>Homomorphic grammars can easily express such ideas as agreement of subject
>and verb, or (with a little more difficulty) requiring every variable in a
>program unit to be declared. They are also easily able to deal with the
>phrase repeated twice, which provided the counter-example (that I know of)
>to natural languages being context sensitive.
The other example has to do with cross serial dependencies which are
essentailly the same problem.
>* Has anybody investigated grammars of this form? If so, what were their
>results?
Not to my knowledge, but that means very little.
>* Is there some relatively easy way to parse homomorphic grammars?
I suspect (unlike a satement of yours that I have edited out) that these
grammars are fully as powerful as CS-PSGs. That is because a rule can only
apply if the entire string being transformed meets a particular pattern.
This restriction on the application of a rewrite rule looks like a CS
grammar, but your system does have addition restrictions which may
ultimately limit its power. So, in short, I guess (and my intuitions about
such things derive from no training are experience in this area) that these
are equivalent to CS grammars and will be just as hard to parse.
>* Are these grammars adequate to parse natural languages? Does it make any
>sense to do so?
These certainly cover the cases which are known to be beyond CF (see a
posting of mine from about three weeks ago on weak generative capicity and
natural language.
I do suspect that what you have is weakly powerful enough. I suspect it is
to powerful. I have problems figuring out what a grammar fragment of a
natural language would look like in your formalism, but I will give it some
thought and maybe post some comments on how it may or may not be
appropriate.
>Frank Adams ihnp4!philabs!pwa-b!mmintl!franka
>Ashton-Tate 52 Oakland Ave North E. Hartford, CT 06108
--
Jeff Goldberg
ARPA goldberg@russell.stanford.edu
UUCP ...!ucbvax!russell.stanford.edu!goldberg
------------------------------
Date: Wed, 10 Jun 87 14:00 EDT
From: William J. Rapaport <rapaport@sunybcs.UUCP>
Subject: Re: Conceptual Information Research
In article <33@aimmi.UUCP> walt@hci.hw.ac.uk (Walter Bunch) writes:
>
>I'm interested in researching knowledge representation as part of a PhD
>program.
>
>What universities are supporting research in the use and properties of
>conceptual information, e.g. in light of Sowa's "Conceptual Structures"
>(1984)?
>Walter Bunch, Scottish HCI Centre, Ben Line Building, Edinburgh, EH1 1TN
>UUCP: walt@uk.ac.hw.aimmi
>ARPA: walt%aimmi.hw.ac.uk@cs.ucl.ac.uk
>JANET: walt@uk.ac.hw.aimmi "Is that you, Dave?"
There is an active research group looking at knowledge representation
issues in the Dept. of Computer Science at SUNY Buffalo. The group is
the SNePS Research Group, directed by Stuart C. Shapiro (I'm its associate
director). You can get more complete information on our graduate
program by writing to:
Mrs. Eloise Benzel
Department of Computer Science
SUNY Buffalo
Buffalo, NY 14260
USA
or contacting me electronically for specific questions:
William J. Rapaport
Assistant Professor
Dept. of Computer Science, SUNY Buffalo, Buffalo, NY 14260
(716) 636-3193, 3180
uucp: ..!{allegra,decvax,watmath,rocksanne}!sunybcs!rapaport
csnet: rapaport@buffalo.csnet
bitnet: rapaport@sunybcs.bitnet
------------------------------
Date: Mon, 15 Jun 87 06:56 EDT
From: Lambert Meertens <lambert@cwi.nl>
Subject: Re: Could X's inflection in [X (Y) Z] depend on the presense of Y?
In article <1645@pbhye.UUCP> rob@pbhye.UUCP (Rob Bernardo) writes:
>
| In article <1425@etlcom.etl.JUNET> hasida@etlcom.etl.JUNET (Hasida Koiti) writes:
| +Wanted: Natural languages which have the property as follows:
| +(1) X's inflection differs between the two contexts [X Y Z]
| + and [X Z], for some (equivalence classes of) grammatical
| + categories X, Y, and Z, such that both [X Y Z] and [X Z]
| + constitute grammatical categories with Z the head, under
| + some inflection (or conjugation, declension, or the like)
| + of X, Y, and Z.
|
| How about English?
|
> an orange house vs a house
Isn't there also something in Hebrew where X in [X Y] is different from
stand-alone [X], something like
ruach elohim vs ruch
(spirit of god) (spirit)
Hebrew isn't one of my strong points, so the transcription and translation
may be off, but there is definitely something of that nature there.
--
Lambert Meertens, CWI, Amsterdam; lambert@cwi.nl
------------------------------
Date: Mon, 15 Jun 87 13:40 EDT
From: Robert Rubinoff <rubinoff@linc.cis.upenn.edu>
Subject: Re: Could X's inflection in [X (Y) Z] depend on the presense of Y?
In article <7421@boring.cwi.nl> lambert@boring.UUCP (Lambert Meertens) writes:
>Isn't there also something in Hebrew where X in [X Y] is different from
>stand-alone [X], something like
>
> ruach elohim vs ruch
> (spirit of god) (spirit)
Well, actually, "ruach" is a word that is the same in both cases. There is
no form "ruch". There are, however, two different forms of many nouns, but
they have a different meaning. If the root form means "x", the other form
means "the X of". For example "Bahyeet" means "house", and "bayt" means
"the house of". (Incidentally, the "Beth" that appears in the name of
many synagogues is a transliteration of "Bayt"; the "th" is because there are
two letters in Hebrew that are pronounced "t": "tet" and "tahf". "Tahf" is
sometimes transliterated as "th" to distinguish it. There is no "th" sound
in Hebrew, though.)
Robert
------------------------------
End of NL-KR Digest
*******************
