Home > Archive > Prolog > February 2005 > Linear Logic Maybe?
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
| Author |
Linear Logic Maybe?
|
|
| Jan Burse 2005-02-09, 8:59 pm |
| Dear All
I am working on an algebra for some
language processing. The language
processing includes the combination
of nouns, verbs and adjectives.
So I came up first with the
following connectives:
A & B: Conjunction
A v B: Disjunction
And some rules, for example
disjunctive normal form:
A & (B v C) --> (A & B) v (A & C)
etc..
This works pretty well for some
language phaenomena. For example
"roof, window and door", kann be
modeled by &, and so on.
Now I was introducing the following
two connectives:
A ! B: Composition
A ? B: Guard
And the rules are as such:
A ! (B ! C) --> (A ! B) ! C
(A & B) ! C --> A ! C & B ! C (i)
A ! (B & C) --> A ! B & A ! C (ii)
etc..
(A ? B) ! C --> (B ! A) & (B ! C) (iii)
etc..
This works pretty well for some
language phaenomena. For example
"the green door is open" can be
modelled by (green?door)!open.
But now, as I dont have any clue
what algebra this might be, so that
I can lookup up the algebras properties,
many questions arise. For example
1) Does the order of application
of the rules (i) and (ii) make
any difference in the normal form?
(answer = yes, guess why?)
2) Similar questions in the interaction
between ? and !, not yet answered
for my self.
Any pointers welcome?
Best Regards
---
Spuntik III
| |
| Bart Demoen 2005-02-10, 8:58 am |
| Jan Burse wrote:
> 1) Does the order of application
> of the rules (i) and (ii) make
> any difference in the normal form?
> (answer = yes, guess why?)
>
> 2) Similar questions in the interaction
> between ? and !, not yet answered
> for my self.
>
> Any pointers welcome?
>
> Best Regards
> ---
> Spuntik III
I think the property you should be looking for is named
confluence - in combination with term rewriting.
It is undecidable in general.
I wish you good luck.
Bart Demoen
| |
|
|
| Jan Burse 2005-02-10, 3:58 pm |
| Dear All
Bart Demoen wrote:
> Jan Burse wrote:
> I think the property you should be looking for is named
> confluence - in combination with term rewriting.
> It is undecidable in general.
Many tanks for the hint. Now lets
assume the system is not confluent,
and by a critical pair algorithm
I want to make it confluent.
What critical pairs would you add
so that it corresponds to the most
common (sic!) interpretation of
! in natural language. Take
the example:
(red v green)!(apples & bananas)
This yields either:
(red!apples & red!bananas) v (green!apples & green!bananas)
(red!apples v green!apples) & (red!bananas v green!bananas)
Which is not equivalent!
A B C D ABvCD (AvC)(BvD)
0 0 0 0 0 0
0 0 0 1 0 0
0 0 1 0 0 0
0 0 1 1 1 1
0 1 0 0 0 0
0 1 0 1 0 0
0 1 1 0 0 1 <<< here
0 1 1 1 1 1
1 0 0 0 0 0
1 0 0 1 0 1 <<< here
1 0 1 0 0 0
1 0 1 1 1 1
1 1 0 0 1 1
1 1 0 1 1 1
1 1 1 0 1 1
1 1 1 1 1 1
Things get even more complicated with
the ? operator.
Any pointers welcome! Namely psycho-
linguistic stuff.
And if the psycholinguistic stuff is
setteled, what model theoretic
interpretion could be given to the
! operator?
Best Regards
---
Spuntik III
| |
| Jan Burse 2005-02-10, 3:58 pm |
| Hi
Jan Burse wrote:
> Dear All
> What critical pairs would you add
> so that it corresponds to the most
Or lets say what other rewriting
system would one use for v, &
and !. (And also for ?)
Best Regards
---
Spuntik III
| |
| tmp123 2005-02-10, 8:57 pm |
| Jan Burse wrote:
>
> (red v green)!(apples & bananas)
>
> This yields either:
>
> (red!apples & red!bananas) v (green!apples & green!bananas)
> (red!apples v green!apples) & (red!bananas v green!bananas)
>
Probably I do not understand something, because if
"!" means "->" ("then")
"&" means "/\" ("and")
"v" means "\/" ("or")
then:
red!apples & red!bananas & green!apples & green!bananas
(red->apples /\ red->bananas /\ green->apples /\ green->bananas)
and if "!" means "<-":
~red \/ ~green \/ apple \/ banana
where ~ means "not".
I suposse I'm missing something.
| |
| Justin Pearson 2005-02-11, 8:58 am |
| "tmp123" <tmp123@menta.net> writes:
> Jan Burse wrote:
>
> red!apples & red!bananas & green!apples & green!bananas
>
> (red->apples /\ red->bananas /\ green->apples /\ green->bananas)
>
> and if "!" means "<-":
>
> ~red \/ ~green \/ apple \/ banana
>
> where ~ means "not".
>
> I suposse I'm missing something.
>
Lambek (of Lambek and Scott fame) did some stuff on various categories
and logics for linguistic modelling. Some of it is is close to Linear
Logic.
If you do a search on Lambick Calculus you might find something.
--
Justin Pearson - Uppsala Sweden http://www.docs.uu.se/~justin
| |
| Jan Burse 2005-02-11, 8:58 am |
| Hi
tmp123 wrote:
> Probably I do not understand something, because if
> "!" means "->" ("then")
> "&" means "/\" ("and")
> "v" means "\/" ("or")
With ! I have more a composition/application
in mind then an implikation.
Let @ denote the application. It takes an
argument f and g, where f is a function A->B
and g is an element of A. Then f@g is an element
of B. Namely:
f:A->B, g:A
-----------
f@g:B
Then ! can denote the inverse composition as
follows. It takes argument h and f, where h
is a function B->C and f is a function A->B.
Then h!f is a function A->C. Namely:
h:B->C, f:A->B
--------------
h!f:A->C
We can model ! by @. Namely h!f = \x.h@(f@x)
where \x. is the lambda abstraction.
Now we can assume that Nouns are "Merkmale",
thus they map Objects to Subobjects. Namely
a Noun is a function O->O, where is O is
the set of a objects, an infinite set.
Further we can assume that Adjects are
"Ausprägungen", thus they map Objects to
Truthvalues. Namely an Adjective is a
function O->2. Where 2 ist the set {0,1},
and 2 and O are disjoint.
In the example we had apples and bananas.
Lets assume apples and bananas refers not
to apples and bananas in general, but we
have a situation which is modeled as a
record {apple:x,banna:y}.
apple:O->O
apple{apple:x,..}=x
banana:O->O
banana{banna:y,..}=y
In the example we had also red and green.
Lets assume that the x and y are futher
records of the form {color:z,...}. Then
we can define:
red:O->T
red{color:"red",..}=true
red{color:"green",..}=false
green:O->T
green{color:"red",..}=false
gren{color:"green",..}=true
Now red!apple means that the apple in the
current situation is red. The expression
is of the type O->T:
red:O->T apple:O->O
--------------------
red!apple:O->T
Now (red v green) can be easily interpreted
as the truth function which results from
the truth function of red and green by
the following rule:
p:O->T, q:O->T
--------------------------------------
(pvq)(x) := p(x) v q(x), (pvq):O->T
But what happens if we make a disjunction
or conjunction of Nouns?
p:O->O, q:O->O
-----------------
pvq ?? q&p ??
What disjunction and conjunction should
be defined. How could a calculus look like?
Best Regards
---
Spuntik III
| |
| tmp123 2005-02-12, 8:57 am |
| OK, I've reason: I was  .
Thanks for your explanation. Just a doubt:
I understand result of "apples" is a subset of objects. Is result of
"red!apples" a subset of objects or a "boolean"?
Kind regards.
| |
| Jan Burse 2005-02-12, 3:57 pm |
| Hi
tmp123 wrote:
> OK, I've reason: I was .
> Thanks for your explanation. Just a doubt:
> I understand result of "apples" is a subset of objects. Is result of
> "red!apples" a subset of objects or a "boolean"?
Result of red is a boolean.
Result of apple is another
object (individual, not set).
Bye
--
Spuntik III
| |
| tmp123 2005-02-13, 8:59 am |
| I though "apples" (plural) was a set of several objects.
If result of red is boolean, it means that there are a red apple in the
set (exist), or that all apples are red (forall)?
| |
| Jan Burse 2005-02-13, 8:59 am |
| Hi
tmp123 wrote:
> I though "apples" (plural) was a set of several objects.
> If result of red is boolean, it means that there are a red
> apple in the set (exist), or that all apples are red (forall)?
A sorry, yes I used the noun apples (plural)
first. And afterwards in my explanation, the
noun apple (singular).
I am first interested in the singular case,
i.e. apple and banana. But suggestions
for the plural cases are also wellcome.
Because I dont want to run into quantifier
discussions, I would also handle plural not
with sets but with individuals.
Consider a situation where we have many apples,
namely a determined number of apples. We can
model this as a list [apple0,apple1,..,applen-1].
The Noun apples could still be interpreted as
O->O. Mapping the situation to a list of individuals.
We only have to allow finite lists of objects
among the objects. Namely n->O subset O, for all n.
Where n denotes {0,..,n-1}.
Then Adjektiv red could also still be interpreted
as O->2. Whether red means then that all apples
are read, half of them or at least one is red,
is private to the red Adjective. Maybe we could
also use Fuzzy Membership, O->R.
I am more interessted in what operations &, v
could be defined on O->O, and how do these
operations interact with ! and O->T.
Best Regards
--
Spuntik III
| |
| tmp123 2005-02-13, 4:01 pm |
| OK, my second try, after the disaster of my explanation with '->'.
First assumption: the operator & when applied to subset, means set
union (?). That is for me a few confusing, because tipically & means
set intersection.
It seems imposible to skip to work the concept of adjectives over sets,
because "a&b" is, even with only one apple and one banana, a set of two
elements.
Now, the first expansion:
| (1) (2)
| (rvg)!(a&b) <-> (rvg)!a & (rvg)!b <-> ( a!a v g!a) & (r!b v g!b).
| step1 : and adjective over a set of two elements (a & b) means
| "for all" (for a and for b).
| step2 : Only usual bool logic.
it seems ok.
Now, the second expansion:
| (1) (2)
| (rvg)!(a&b) <-> r!(a&b) v g!(a&b) <-> (r!a & r!b) v (g!a & g!b)
| step 1: see below
| step 2: again, and adjective over a set means for all.
Problem: step 1 seems not OK (?). The implicit "for all" is broken. If
I write it in "classical logic":
| (rvg)!(a&b) <-> [for all x, x in {a,b} -> (rvg)(x)] <-ERROR->
| [for all x, x in {a,b} -> r(x)]
| v
| [for all x, x in {a,b} -> g(x)] <-> r!(a&b) v g!(a&b)
Well, this is my answer (or it is my question?).
PS1: Do you have a link to a good "smylies" dictionary?
PS2: I suggest you Canarian Island's bananas. They are yellow.
| |
| tmp123 2005-02-13, 4:01 pm |
| Editorial mistakes:
1) Please, forget my comment about smylies. I take by smylies something
that in fact they was characters from a previous line, broken when
google displays the post.
2) "step1 : and adjective ..." must be "step1: an adjective ..."
| |
| Jan Burse 2005-02-13, 8:59 pm |
| Hi
tmp123 wrote:
> First assumption: the operator & when applied to subset, means set
> union (?). That is for me a few confusing, because tipically & means
> set intersection.
In a previous post I defined for adjectives:
(pvq)(x) := p(x) v q(x)
I should also point out that:
(p&q)(x) := p(x) & q(x)
This clearly amounts to set union and intersection.
Because a subset of O, is the same as a mapping O->2.
And set union and intersection are defined exactly
as above.
You need to interpret the conjunction differently.
Namely you define it as follows:
(p &_tmp123 q)(x) := p(x) v q(x)
> Problem: step 1 seems not OK (?). The implicit "for all" is broken. If
> I write it in "classical logic":
>
> | (rvg)!(a&b) <-> [for all x, x in {a,b} -> (rvg)(x)] <-ERROR->
> | [for all x, x in {a,b} -> r(x)]
> | v
> | [for all x, x in {a,b} -> g(x)] <-> r!(a&b) v g!(a&b)
>
> Well, this is my answer (or it is my question?).
In my previous post I defined Nouns as mappings
O->O. Namely selecting someting out of the
current situation. And I also defined ! as the
inverse composition. Namely:
(h ! f)(x) := h(f(x))
It seems to me that you define Nouns as sets
similar to Adjectives. And that you interpret
! as a quantification. Namely your ! is the
following:
h:O->2 f:O->2
------------------------
h !_tmp123 f:2
So it takes two Sets and gives a Truth value.
The disavantage is that it closes the formula,
incontrast where I aim to get formulas that
are situation dependent for sentences.
But lets continue with your interpretation.
Your interpretation is then:
h !_tmp123 f := forall x(h(x)->f(x))
So ist a kind of implication. Maybe this is
the reason why you came up with implication
the first time.
So & and &_tmp123, ! and !_123 are quite
different. And you favor the first expansion.
Maybe we can draw more analogies...
Thanks. Lets see.
Bye
---
Spuntik III
| |
| Jan Burse 2005-02-13, 8:59 pm |
| Hi
> PS1: Do you have a link to a good "smylies"
> dictionary?
#"-\
> PS2: I suggest you Canarian Island's bananas.
> They are yellow.
Yes, the example is not so good. Take (fresh & heavy)!(...).
Then also the conjunction is less problematic.
Bye
---
Spuntik III
| |
| tmp123 2005-02-14, 8:59 am |
| This is the example step by step:
Initial state S with 2 apples, 1 banana, 1 kiwi : S = {the_red_apple,
the_green_apple, the_green_banana, the_green_kiwi}
Basic operators (I introduce also the short forms a,b,r,g):
apples(S) = a(S) = {the_red_apple,the_green_apple}
bananas(S) = b(S) = {the_green_banana}
red(the_red_apple) = r(the_red_apple) = true
green(the_green_apple) = g(the_green_apple) = true
green(the_green_banana) = g(the_green_banana) = true
green(the_green_kiwi) = true
(remainder pairs are false)
Analysis of (r\/g)!(a&b) over the example:
((r v g)!(a&b))(S) =
= (r v g)( (a& b)({the_red_apple,the_green_apple,the_gr
een_banana,
the_green_kiwi}) ) =
(?)= (r v g)({the_red_apple,the_green_apple,the_gr
een_banana}) =
(?)= r({the_red_apple,the_green_apple,the_gre
en_banana}) v
g({the_red_apple,the_green_apple,the_gre
en_banana})
= ? v ?
Sorry, probably, again totally loss.
|
|
|
|
|