text: 3. Density Matrices in Categorical Compositional Table 1: Table of diagrams in CPM(C) and C Distributional Semantics C C CPM( ) 3.1 Positive Operators and Density Matrices ⊗ ∗ ⊗ ∗ ⊗ ⊗ → E(ε) = ε∗ ε ε : A A A A I ∗ ∗ ∗ The methods outlined in section can be applied to the richer A A A A A A setting of density matrices. Density matrices are used in quan- tum mechanics to express uncertainty about the state of a system. | (cid:105) | (cid:105) (cid:104) | | (cid:105) ⊗ | (cid:105) ⊗ | (cid:105) ⊗ | (cid:105) (cid:55)→ (cid:104) | (cid:105) (cid:104) | (cid:105) For unit vector v |, t(cid:105)he projection operator v v onto the sub- ε : ei ej ek el ei ek ej el space spanned by v is called a pure state. Pure states can be ⊗ → ⊗ ⊗ ∗ ⊗ ∗ thought of as giving sharp, unambiguous information. In general, E(η) = η∗ η η : I A A A A density matrices are given by a convex sum of pure states, describ- ing a probabilistic mixture. States that are not pure are referred to as (cid:80) mixed states. Necessary and sufﬁcient conditions for an operator ρ ∗ ∗ ∗ A A A A A A to encode such a probabilistic mixture are: (cid:55)→ | (cid:105) ⊗ | (cid:105) ⊗ | (cid:105) ⊗ | (cid:105) • ∀ ∈ (cid:104) | | (cid:105) ≥ η : 1 e e e e v V. v ρ v 0 ij i j i j • ∗ ∗ ρ is self-adjoint. B D B D D B • ρ has trace 1. Operators satisfying the ﬁrst two axioms are called positive opera- f f f f 1 2 1 2 tors. The third axiom ensures that the operator represents a convex mixture of pure states. However, relaxing this condition gives us ∗ ∗ different choices for normalization, which we will outline in sec- A C A C C A ⊗ ∗ ⊗ ∗ ⊗ ⊗ → ∗ ⊗ ∗ ⊗ ⊗ tion . f f : A C C A B D D B 1 2 In distributional models of meaning, we can consider the mean- {| (cid:105)} iw(cid:80)nhgeoref aeawcohrd|ww(cid:105)torebperegsiveenntsbaynaicnostlalenccteioonfotfhuencitovneccetpotrsexpwreisseid, k (cid:55)→ k∗ ⊗ k i | (cid:105) ∈ † by the word. Each w is weighted by p [0, 1], such that This functor preserves the -compact closed structure, and is faith- i i p = 1. These weights de(cid:88)scribe the meaning of w as a weighted ful “up to a global phase” (Selinger 2007). i i combination of exemp(cid:74)lar(cid:75)s. Then the density operator: w = p |w (cid:105) (cid:104)w | 3.3 Diagrammatic calculus for CPM(C) i i i C † i As CPM( ) is also a -compact closed category, we can use represents the word w. For example a cat is a fairly typical pet, the graphical calculus described inC section . By convention, the and a tarantula is less typical, so a simple density operator for the diagrammatic calculus for CPM( ) is drawn using thick wires. C word(cid:74)pet(cid:75)might be: The corresponding diagrams in are given in table 1. × | (cid:105) (cid:104) | × | (cid:105) (cid:104) | 3.3.1 Sentence Meaning in the category CPM(FHilb) pet = 0.9 cat cat + 0.1 tarantula tarantula In the vector space model of distributional models of meaning the transition between syntax and semantics was achieved via a 3.2 The CPM Construction → strong monoidal functor Q : Preg FHilb. Language can Applying Selinger’s CPM construction (Selinger 2007) to FHilb be assigned semantics in CPM(FHilb) in an entirely analogous † produces a new -compact closed category in which the states are way via a strong monoidal functor: positive operators. This construction has previously been exploited → S : Preg CPM(FHilb) in a linguistic setting in (Kartsaklis 2015; Piedeleu et al. 2015; Balkır et al. 2016). Deﬁnition 3. Let w , w ...w be a string of words with corre- C † 1 2 n Throughout this section denotes an arbitrary -compact closed sponding grammatical types t in PregB. Suppose that the type (cid:74) (cid:75) i −→ ∈ cDae∗teﬁ⊗gnoitriyo→.n 1 (∗C⊗ompletely positive morphism). A C-morphism ϕ : rLeedtucwtiionbeisthgei→vmeneabnyintg1,o.f..wtnordrwixinfCorPsMom(eFxHilbO),bi.(eP. arestgaBte. Aif therAe exisBts C ∈B Oisbs(aCid)taonbdekco∈mpCl(eCtel⊗y pAos,iBtiv)e, s(uScehlinthgaetrϕ20c0a7n) obfy:the form I(cid:74) S(ti). (cid:75)Then the m(cid:74) ean(cid:75)ing of w(cid:74)1w2(cid:75)...wn is given be written in the form: ⊗ ⊗ w w ...w = S(r)( w ... w ) ⊗ ◦ ⊗ ⊗ 1 2 n 1 n (k∗ k) (1A∗ ηC 1A) We now have all the ingredients to derive sentence meanings Identity morphisms are completely positive, and completely in CPM(FHilb). C positive morphisms are closed under composition in , leading to Example 1. We ﬁrstly show that the results from FHilb lift to the following: CPM(FHilb). Let the noun space N be a real Hilbert space with C † C {| (cid:105)} | (cid:105) | (cid:105) Diseaﬁcnaittieognor2y.wIifth tihseasam-ceomobpjaeccttscalossCedacnadteitgsomryorthpehnisCmsPaMre(the) banasdisfovrescotomrsegji,v|enn b(cid:105)y=(cid:88)|nbieeri(cid:105),. wLhetertehefosrenstoemnceei,spnacie b=e aCnolathraer j{| (cid:105)} | (cid:105) completely positive morphisms. space S with basis s . The verb likes is given by: i i † | (cid:105) | (cid:105) ⊗ | (cid:105) ⊗ | (cid:105) The -compact structurCe required for interpreting language in likes = Cpqr np sq nr our setting lifts to CPM( ): pqr C † Theorem 1. CPM( ) is also a -compact closed category. There The density matrices for the nouns Clara and beer are in fact pure is a functor: states g(cid:74)iven by(cid:75): (cid:74) (cid:75) C → C | (cid:105) (cid:104) | | (cid:105) (cid:104) | E : CPM( ) Clara = n n and beer = n n i i j j ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: Density

text: Matrices

text: in

text: Categorical

text: Compositional

text: Table

text: Table

text: of

text: diagrams

text: in

text: CPM(C)

text: and

text: C

text: Distributional

text: Semantics

text: C

label: table

text: C

text: CPM(

text: Positive

text: Operators

text: and

text: Density

text: Matrices

text: E(ε)

text: ε∗

text: ε

text: ε

text: A

text: A

text: A

text: A

text: I

text: The

text: methods

text: outlined

text: in

text: section

text: can

text: be

text: applied

text: to

text: the

text: richer

text: A

text: A

text: A

text: A

text: A

text: A

text: setting

text: of

text: density

text: matrices.

text: Density

text: matrices

text: are

text: used

text: in

text: quan-

text: tum

text: mechanics

text: to

text: express

text: uncertainty

text: about

text: the

text: state

text: of

text: a

text: system.

text: For

text: unit

text: vector

text: v

text: projection

text: operator

text: v

text: v

text: onto

text: the

text: sub-

text: ε

text: ei

text: ej

text: ek

text: el

text: ei

text: ek

text: ej

text: el

text: space

text: spanned

text: by

text: v

text: is

text: called

text: a

text: pure

text: state.

text: Pure

text: states

text: can

text: be

text: thought

text: of

text: as

text: giving

text: sharp,

text: unambiguous

text: information.

text: In

text: general,

text: E(η)

text: η∗

text: η

text: η

text: I

text: A

text: A

text: A

text: A

text: density

text: matrices

text: are

text: given

text: by

text: a

text: convex

text: sum

text: of

text: pure

text: states,

text: describ-

text: ing

text: a

text: probabilistic

text: mixture.

text: States

text: that

text: are

text: not

text: pure

text: are

text: referred

text: to

text: as

text: mixed

text: states.

text: Necessary

text: and

text: sufﬁcient

text: conditions

text: for

text: an

text: operator

text: ρ

text: A

text: A

text: A

text: A

text: A

text: A

text: to

text: encode

text: such

text: a

text: probabilistic

text: mixture

text: are:

text: η

text: e

text: e

text: e

text: e

text: v

text: V.

text: v

text: ρ

text: v

text: ij

text: i

text: j

text: i

text: j

text: ρ

text: is

text: self-adjoint.

text: B

text: D

text: B

text: D

text: D

text: B

text: ρ

text: has

text: trace

text: Operators

text: satisfying

text: the

text: ﬁrst

text: two

text: axioms

text: are

text: called

text: positive

text: opera-

text: f

text: f

text: f

text: f

text: tors.

text: The

text: third

text: axiom

text: ensures

text: that

text: the

text: operator

text: represents

text: a

text: convex

text: mixture

text: of

text: pure

text: states.

text: However,

text: relaxing

text: this

text: condition

text: gives

text: us

text: different

text: choices

text: for

text: normalization,

text: which

text: we

text: will

text: outline

text: in

text: sec-

text: A

text: C

text: A

text: C

text: C

text: A

text: tion

text: f

text: f

text: A

text: C

text: C

text: A

text: B

text: D

text: D

text: B

text: In

text: distributional

text: models

text: of

text: meaning,

text: we

text: can

text: consider

text: the

text: mean-

text: k

text: k∗

text: k

text: i

text: by

text: the

text: word.

text: Each

text: w

text: is

text: weighted

text: by

text: p

text: such

text: that

text: This

text: functor

text: preserves

text: the

text: -compact

text: closed

text: structure,

text: and

text: is

text: faith-

text: i

text: i

text: p

text: These

text: weights

text: the

text: meaning

text: of

text: w

text: as

text: a

text: weighted

text: ful

text: “up

text: to

text: a

text: global

text: phase”

text: (Selinger

text: i

text: i

text: combination

text: of

text: Then

text: the

text: density

text: operator:

text: w

text: p

text: |w

text: Diagrammatic

text: calculus

text: for

text: CPM(C)

text: i

text: i

text: i

text: C

text: i

text: As

text: CPM(

text: is

text: also

text: a

text: -compact

text: closed

text: category,

text: we

text: can

text: use

text: represents

text: the

text: word

text: w.

text: For

text: example

text: a

text: cat

text: is

text: a

text: fairly

text: typical

text: pet,

text: the

text: graphical

text: calculus

text: described

text: inC

text: section

text: By

text: convention,

text: the

text: and

text: a

text: tarantula

text: is

text: less

text: typical,

text: so

text: a

text: simple

text: density

text: operator

text: for

text: the

text: diagrammatic

text: calculus

text: for

text: CPM(

text: is

text: drawn

text: using

text: thick

text: wires.

text: C

text: be:

text: The

text: corresponding

text: diagrams

text: in

text: are

text: given

text: in

text: table

text: Sentence

text: Meaning

text: in

text: the

text: category

text: CPM(FHilb)

text: pet

text: cat

text: cat

text: tarantula

text: tarantula

text: In

text: the

text: vector

text: space

text: model

text: of

text: distributional

text: models

text: of

text: meaning

text: the

text: transition

text: between

text: syntax

text: and

text: semantics

text: was

text: achieved

text: via

text: a

text: The

text: CPM

text: Construction

text: strong

text: monoidal

text: functor

text: Q

text: Preg

text: FHilb.

text: Language

text: can

text: Applying

text: Selinger’s

text: CPM

text: construction

text: (Selinger

text: to

text: FHilb

text: be

text: assigned

text: semantics

text: in

text: CPM(FHilb)

text: in

text: an

text: entirely

text: analogous

text: produces

text: a

text: new

text: -compact

text: closed

text: category

text: in

text: which

text: the

text: states

text: are

text: way

text: via

text: a

text: strong

text: monoidal

text: functor:

text: positive

text: operators.

text: This

text: construction

text: has

text: previously

text: been

text: exploited

text: S

text: Preg

text: CPM(FHilb)

text: in

text: a

text: linguistic

text: setting

text: in

text: (Kartsaklis

text: Piedeleu

text: et

text: al.

text: Balkır

text: et

text: al.

text: Deﬁnition

text: Let

text: w

text: w

text: ...w

text: be

text: a

text: string

text: of

text: words

text: with

text: corre-

text: C

text: n

text: Throughout

text: this

text: section

text: denotes

text: an

text: arbitrary

text: -compact

text: closed

text: sponding

text: grammatical

text: types

text: t

text: in

text: PregB.

text: Suppose

text: that

text: the

text: type

text: i

text: cDae∗teﬁ⊗gnoitriyo→.n

text: (∗C⊗ompletely

text: positive

text: morphism).

text: A

text: C-morphism

text: ϕ

text: arestgaBte.

text: Aif

text: therAe

text: exisBts

text: C

text: ∈B

text: Oisbs(aCid)taonbdekco∈mpCl(eCtel⊗y

text: pAos,iBtiv)e,

text: obfy:the

text: form

text: S(ti).

text: the

text: of

text: is

text: given

text: be

text: written

text: in

text: the

text: form:

text: w

text: w

text: ...w

text: S(r)(

text: w

text: w

text: n

text: n

text: (k∗

text: k)

text: ηC

text: We

text: now

text: have

text: all

text: the

text: ingredients

text: to

text: derive

text: sentence

text: meanings

text: Identity

text: morphisms

text: are

text: completely

text: positive,

text: and

text: completely

text: in

text: CPM(FHilb).

text: C

text: positive

text: morphisms

text: are

text: closed

text: under

text: composition

text: in

text: leading

text: to

text: Example

text: We

text: ﬁrstly

text: show

text: that

text: the

text: results

text: from

text: FHilb

text: lift

text: to

text: the

text: following:

text: CPM(FHilb).

text: Let

text: the

text: noun

text: space

text: N

text: be

text: a

text: real

text: Hilbert

text: space

text: with

text: C

text: C

text: banasdisfovrescotomrsegji,v|enn

text: wLhetertehefosrenstoemnceei,spnacie

text: b=e

text: aCnolathraer

text: j{|

text: completely

text: positive

text: morphisms.

text: space

text: S

text: with

text: basis

text: s

text: The

text: verb

text: likes

text: is

text: given

text: by:

text: i

text: i

text: The

text: -compact

text: structurCe

text: required

text: for

text: interpreting

text: language

text: in

text: likes

text: Cpqr

text: np

text: sq

text: nr

text: our

text: setting

text: lifts

text: to

text: CPM(

text: pqr

text: C

text: Theorem

text: CPM(

text: is

text: also

text: a

text: -compact

text: closed

text: category.

text: There

text: The

text: density

text: matrices

text: for

text: the

text: nouns

text: Clara

text: and

text: beer

text: are

text: in

text: fact

text: pure

text: is

text: a

text: functor:

text: states

text: C

text: C

text: E

text: CPM(

text: Clara

text: n

text: n

text: and

text: beer

text: n

text: n

text: i

text: i

text: j

text: j

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: We then write: We can see that the general error terms are strictly more general A |= B than consideringthe k-hyponymy case.If we consider positive operators with matrix representations: and say A entails B if there exists a proposition D such that:     1 0 0 1 0 0 A + D = B A = 0 1 0 B = 0 0 0 If our commutative monoid is the powerset of some set X, with 0 0 0 0 0 1 union the binary operation and unit the empty set, then we recover our non-deterministic computation example from the previous sec- Predic−ate A cannot entail B with any positive strength k. We can tion. If on the other hand we take our commutative monoid to be see B kA is never a positive operator as thefollowing expression is always nega(cid:0)tive: (cid:1) the positive operators on some Hilbert space, with addition of oper-     − ators and the zero operator as the monoid structure, we recover the 1 k 0 0 0 − Lo¨wner ordering. 0 1 0 0 k 0 1 In linguistics, we may ask ourselves does dog entail pet? 0 0 1 0 Na¨ıvely, the answer is clearly no, not every dog is a pet. This seems (cid:118) too crude for realistic applications though, most dogs are pets, and We can ﬁnda more generalpositive operatorE such that A  so we might say dog entails pet to some extent. This motivates our B+ E though, as:      need for an approximate notion of entailment. 1 0 0 0 0 0 1 0 0 0 0 0 For proposition E, we say that A entails B to the extent E if: 0 1 0 + 0 0 0 = 0 0 0 + 0 1 0 | 0 0 0 0 0 1 0 0 1 0 0 0 A = B + E We think of E as a error term, for instance in our dogs and pets Therefore the general error terms offer strictly more freedom than example, E adds back in dogs that are not pets. Expanding deﬁni- k-hyponymy. tions, we ﬁnd A entails B to extent E if there exists D such that: 5. Hyponymy in Categorical Compositional Distributional Semantics A + D = B + E (2) Modelling hyponymy in the categorical compositional distribu- tional semantics framework was ﬁrst considered in (Balkır 2014). From this more symmetrical formulation it is easy to see that She introduced an asymmetric similarity measure called repre- for arbitrary propositions A, B, proposition A trivially entails B to sentativeness on density matrices based on quantum relative en- extent A, as by commutativity: tropy. This can be used to translate hyponym-hypernym relations to the level of positive transitive sentences. Our aim here will be A + B = B + A to provide an alternative measure which relies only on the prop- It is therefore clear that the mere existence of a suitable error erties of density matrices and the fact that they are the states term is not sufﬁcient for a weakened notion of entailment. EIf we in CPM(FHilb). This will enable us to quantify the strength of restrict our attention to errors in a complete meet semilattice A,B, the hyponymy relationship, described as k-hyponymy. The mea- we can take the lower bound on the E satisfying equation (2) as sure of hyponymy that we use has two advantages over the repre- our canonical choice. Finally, if we wish to be able to compare sentativeness measure. Firstly, it combines with the linear sentence entailment stKrengths globally, this can be achieved by choosing a maps so that we can work with sentence-level entailment across partial order of “error sizes” and monotone functions: a larger range of sentences. Secondly, due to the way it combines E −κ−A−,B→ K with linear maps, we can give a quantitative measure to sentence- A,B level entailment based on the entailment strengths between words, sending errors to their corresponding size. whereas representativeness is not shown to combine in this way. For example, if A and B are positive operators, we take our 5.1 Properties of hyponymy E complete lattice of error terms to be all operators of the − ∈ A,B − Before proceeding with deﬁning the concept of k-hyponymy, we form (1 k)A for k [0, 1], ordered by the size of 1 k. We will list a couple of properties of hyponymy. We will show later that then take k as the strength of the entailment, and refer to it as these can be captured by our new measure. k-hyponymy. E P • Asymmetry. If A is a hyponym of B, then this does not imply In the case of ﬁnite sets A, B, we take A,B = (A), and take that Y is a hyponym of X. In fact, we may even assume that only the size of the error terms as: one of these relationships is possible, and that they are mutually cardinality of E exclusive. For example, football is a type of sport and hence cardinality of A football-sport is a hyponym-hypernym pair. However, sport is not a type of football. measuring “how much” of A we have to supplement B with, as • indicated in the shaded region below: Pseudo-transitivity. If X is a hyponym of Y and Y is a hy- ponym of Z, then X is a hyponym of Z. However, if the hy- ponymy is not perfect, then we get a weakened form of tran- B sitivity. For example, dog is a hyponym of pet, and pet is a hyponym of things that are cared for. However, not every dog A is well cared-for, so the transitivity weakens. An outstanding question is where the entailment strength reverses. For exam- ple, dog imperfectly entails pet, and pet imperfectly entails In terms of conditional probability, the error size is then: mammal, but dog perfectly entails mammal. | ¬ P(A B) The measure of hyponymy that we described above and named 4.3.1 k-hyponymy Versus General Error Terms k-hyponymy will be deﬁned in terms of density matrices - the con- tainers for word meanings. The idea is then to deﬁne a quantita- ##LTLine##

text: We

label: paragraph

text: then

text: write:

text: We

text: can

text: see

text: that

text: the

text: general

text: error

text: terms

text: are

text: strictly

text: more

text: general

text: A

text: B

text: than

text: consideringthe

text: k-hyponymy

text: case.If

text: we

text: consider

text: positive

text: operators

text: with

text: matrix

text: representations:

text: and

text: say

text: A

text: entails

text: B

text: if

text: there

text: exists

text: a

text: proposition

text: D

text: such

text: that:

text: A

text: D

text: B

text: A

text: B

text: If

text: our

text: commutative

text: monoid

text: is

text: the

text: powerset

text: of

text: some

text: set

text: X,

text: with

text: union

text: the

text: binary

text: operation

text: and

text: unit

text: the

text: empty

text: set,

text: then

text: we

text: recover

text: our

text: non-deterministic

text: computation

text: example

text: from

text: the

text: previous

text: sec-

text: Predic−ate

text: A

text: cannot

text: entail

text: B

text: with

text: any

text: positive

text: strength

text: k.

text: We

text: can

text: tion.

text: If

text: on

text: the

text: other

text: hand

text: we

text: take

text: our

text: commutative

text: monoid

text: to

text: be

text: see

text: B

text: kA

text: is

text: never

text: a

text: positive

text: operator

text: as

text: thefollowing

text: expression

text: is

text: always

text: the

text: positive

text: operators

text: on

text: some

text: Hilbert

text: space,

text: with

text: addition

text: of

text: oper-

text: ators

text: and

text: the

text: zero

text: operator

text: as

text: the

text: monoid

text: structure,

text: we

text: recover

text: the

text: k

text: Lo¨wner

text: ordering.

text: k

text: In

text: linguistics,

text: we

text: may

text: ask

text: ourselves

text: does

text: dog

text: entail

text: pet?

text: Na¨ıvely,

text: the

text: answer

text: is

text: clearly

text: no,

text: not

text: every

text: dog

text: is

text: a

text: pet.

text: This

text: seems

text: too

text: crude

text: for

text: realistic

text: applications

text: though,

text: most

text: dogs

text: are

text: pets,

text: and

text: We

text: can

text: ﬁnda

text: more

text: generalpositive

text: operatorE

text: such

text: that

text: A

text: so

text: we

text: might

text: say

text: dog

text: entails

text: pet

text: to

text: some

text: extent.

text: This

text: motivates

text: our

text: B+

text: E

text: though,

text: as:

text: need

text: for

text: an

text: approximate

text: notion

text: of

text: entailment.

text: For

text: proposition

text: E,

text: we

text: say

text: that

text: A

text: entails

text: B

text: to

text: the

text: extent

text: E

text: if:

text: A

text: B

text: E

text: We

text: think

text: of

text: E

text: as

text: a

text: error

text: term,

text: for

text: instance

text: in

text: our

text: dogs

text: and

text: pets

text: Therefore

text: the

text: general

text: error

text: terms

text: offer

text: strictly

text: more

text: freedom

text: than

text: example,

text: E

text: adds

text: back

text: in

text: dogs

text: that

text: are

text: not

text: pets.

text: Expanding

text: deﬁni-

text: k-hyponymy.

text: tions,

text: we

text: ﬁnd

text: A

text: entails

text: B

text: to

text: extent

text: E

text: if

text: there

text: exists

text: D

text: such

text: that:

text: Hyponymy

text: in

text: Categorical

text: Compositional

text: Distributional

text: Semantics

text: A

text: D

text: B

text: E

text: Modelling

text: hyponymy

text: in

text: the

text: categorical

text: compositional

text: distribu-

text: tional

text: semantics

text: framework

text: was

text: ﬁrst

text: considered

text: in

text: (Balkır

text: From

text: this

text: more

text: symmetrical

text: formulation

text: it

text: is

text: easy

text: to

text: see

text: that

text: She

text: introduced

text: an

text: asymmetric

text: similarity

text: measure

text: called

text: repre-

text: for

text: arbitrary

text: propositions

text: A,

text: B,

text: proposition

text: A

text: trivially

text: entails

text: B

text: to

text: sentativeness

text: on

text: density

text: matrices

text: based

text: on

text: quantum

text: relative

text: en-

text: extent

text: A,

text: as

text: by

text: commutativity:

text: tropy.

text: This

text: can

text: be

text: used

text: to

text: translate

text: hyponym-hypernym

text: relations

text: to

text: the

text: level

text: of

text: positive

text: transitive

text: sentences.

text: Our

text: aim

text: here

text: will

text: be

text: A

text: B

text: B

text: A

text: to

text: provide

text: an

text: alternative

text: measure

text: which

text: relies

text: only

text: on

text: the

text: prop-

text: It

text: is

text: therefore

text: clear

text: that

text: the

text: mere

text: existence

text: of

text: a

text: suitable

text: error

text: erties

text: of

text: density

text: matrices

text: and

text: the

text: fact

text: that

text: they

text: are

text: the

text: states

text: term

text: is

text: not

text: sufﬁcient

text: for

text: a

text: weakened

text: notion

text: of

text: entailment.

text: EIf

text: we

text: in

text: CPM(FHilb).

text: This

text: will

text: enable

text: us

text: to

text: quantify

text: the

text: strength

text: of

text: restrict

text: our

text: attention

text: to

text: errors

text: in

text: a

text: complete

text: meet

text: semilattice

text: A,B,

text: the

text: hyponymy

text: relationship,

text: described

text: as

text: k-hyponymy.

text: The

text: mea-

text: we

text: can

text: take

text: the

text: lower

text: bound

text: on

text: the

text: E

text: satisfying

text: equation

text: as

text: sure

text: of

text: hyponymy

text: that

text: we

text: use

text: has

text: two

text: advantages

text: over

text: the

text: repre-

text: our

text: canonical

text: choice.

text: Finally,

text: if

text: we

text: wish

text: to

text: be

text: able

text: to

text: compare

text: sentativeness

text: measure.

text: Firstly,

text: it

text: combines

text: with

text: the

text: linear

text: sentence

text: entailment

text: stKrengths

text: globally,

text: this

text: can

text: be

text: achieved

text: by

text: choosing

text: a

text: maps

text: so

text: that

text: we

text: can

text: work

text: with

text: sentence-level

text: entailment

text: across

text: partial

text: order

text: of

text: “error

text: sizes”

text: and

text: monotone

text: functions:

text: a

text: larger

text: range

text: of

text: sentences.

text: Secondly,

text: due

text: to

text: the

text: way

text: it

text: combines

text: E

text: −κ−A−,B→

text: K

text: with

text: linear

text: maps,

text: we

text: can

text: give

text: a

text: quantitative

text: measure

text: to

text: sentence-

text: A,B

text: level

text: entailment

text: based

text: on

text: the

text: entailment

text: strengths

text: between

text: words,

text: sending

text: errors

text: to

text: their

text: corresponding

text: size.

text: whereas

text: representativeness

text: is

text: not

text: shown

text: to

text: combine

text: in

text: this

text: way.

text: For

text: example,

text: if

text: A

text: and

text: B

text: are

text: positive

text: operators,

text: we

text: take

text: our

text: Properties

text: of

text: hyponymy

text: E

text: complete

text: lattice

text: of

text: error

text: terms

text: to

text: be

text: all

text: operators

text: of

text: the

text: A,B

text: Before

text: proceeding

text: with

text: deﬁning

text: the

text: concept

text: of

text: k-hyponymy,

text: we

text: form

text: k)A

text: for

text: k

text: ordered

text: by

text: the

text: size

text: of

text: k.

text: We

text: will

text: list

text: a

text: couple

text: of

text: properties

text: of

text: hyponymy.

text: We

text: will

text: show

text: later

text: that

text: then

text: take

text: k

text: as

text: the

text: strength

text: of

text: the

text: entailment,

text: and

text: refer

text: to

text: it

text: as

text: these

text: can

text: be

text: captured

text: by

text: our

text: new

text: measure.

text: k-hyponymy.

text: E

text: P

text: Asymmetry.

text: If

text: A

text: is

text: a

text: hyponym

text: of

text: B,

text: then

text: this

text: does

text: not

text: imply

text: In

text: the

text: case

text: of

text: ﬁnite

text: sets

text: A,

text: B,

text: we

text: take

text: A,B

text: (A),

text: and

text: take

text: that

text: Y

text: is

text: a

text: hyponym

text: of

text: X.

text: In

text: fact,

text: we

text: may

text: even

text: assume

text: that

text: only

text: the

text: size

text: of

text: the

text: error

text: terms

text: as:

text: one

text: of

text: these

text: relationships

text: is

text: possible,

text: and

text: that

text: they

text: are

text: mutually

text: cardinality

text: of

text: E

text: exclusive.

text: For

text: example,

text: football

text: is

text: a

text: type

text: of

text: sport

text: and

text: hence

text: cardinality

text: of

text: A

text: football-sport

text: is

text: a

text: hyponym-hypernym

text: pair.

text: However,

text: sport

text: is

text: not

text: a

text: type

text: of

text: football.

text: measuring

text: “how

text: much”

text: of

text: A

text: we

text: have

text: to

text: supplement

text: B

text: with,

text: as

text: indicated

text: in

text: the

text: shaded

text: region

text: below:

text: Pseudo-transitivity.

text: If

text: X

text: is

text: a

text: hyponym

text: of

text: Y

text: and

text: Y

text: is

text: a

text: hy-

text: ponym

text: of

text: Z,

text: then

text: X

text: is

text: a

text: hyponym

text: of

text: Z.

text: However,

text: if

text: the

text: hy-

text: ponymy

text: is

text: not

text: perfect,

text: then

text: we

text: get

text: a

text: weakened

text: form

text: of

text: tran-

text: B

text: sitivity.

text: For

text: example,

text: dog

text: is

text: a

text: hyponym

text: of

text: pet,

text: and

text: pet

text: is

text: a

text: hyponym

text: of

text: things

text: that

text: are

text: cared

text: for.

text: However,

text: not

text: every

text: dog

text: A

text: is

text: well

text: cared-for,

text: so

text: the

text: transitivity

text: weakens.

text: An

text: outstanding

text: question

text: is

text: where

text: the

text: entailment

text: strength

text: reverses.

text: For

text: exam-

text: ple,

text: dog

text: imperfectly

text: entails

text: pet,

text: and

text: pet

text: imperfectly

text: entails

text: In

text: terms

text: of

text: conditional

text: probability,

text: the

text: error

text: size

text: is

text: then:

text: mammal,

text: but

text: dog

text: perfectly

text: entails

text: mammal.

text: P(A

text: B)

text: The

text: measure

text: of

text: hyponymy

text: that

text: we

text: described

text: above

text: and

text: named

text: k-hyponymy

text: Versus

text: General

text: Error

text: Terms

text: k-hyponymy

text: will

text: be

text: deﬁned

text: in

text: terms

text: of

text: density

text: matrices

text: the

text: con-

text: tainers

text: for

text: word

text: meanings.

text: The

text: idea

text: is

text: then

text: to

text: deﬁne

text: a

text: quantita-

text: ##LTLine##


text: (cid:74) (cid:75) (cid:74) (cid:75) (cid:74) (cid:75) (cid:74) (cid:75) then some dogs bark does entail some pets bark, and the problem is 1 1 ⊗ ⊗ = s +(cid:74) (ϕ(cid:75)( M(cid:74)ary (cid:75)scof(cid:74)fs (cid:75) choc ) averted. Discussion of the behaviour of quantiﬁers and other word 4 1 4 ⊗ ⊗ types is given in (MacCartney and Manning 2007). + ϕ((cid:74)Mary(cid:75) (cid:74)nibbles(cid:75) (cid:74)cake(cid:75)) · · · The quantity k1 kn is not necessarily maximal, and indeed + ϕ( Mary ⊗ nibbles ⊗ choc )) usually is not. As we only have a lower bound, zero entailment strength between a pair of components does not imply zero entail- Therefore: (cid:74) (cid:75) (cid:74) (cid:75) (cid:74) (cid:75) (cid:74) (cid:75) (cid:74) (cid:75) ment strength between entire sentences. Results for phrases involv- − 1 ⊗ ⊗ ing relative clauses ma(cid:79)y be found in appe(cid:79)ndix . s2 4 s1 = ϕ( Mar(cid:74)y (cid:75)choc(cid:74) ch(cid:75)oc )(cid:74) (cid:75) ⊗ ⊗ Corollary 1. Consider tw(cid:74)o se(cid:75)ntences: (cid:74) (cid:75) + ϕ((cid:74)Mary(cid:75) (cid:74)nibbles(cid:75) (cid:74)cake(cid:75)) ⊗ ⊗ (cid:74) (cid:75) + ϕ(cid:74)( M(cid:75)ary nibbles choc )) Φ = A Ψ = B i i (cid:74) (cid:75) (cid:74) (cid:75) − i i We can see that s 1 s is positive by positivity of the such that for each i ∈ {1, ..., n} we have A (cid:118) B , i.e. there is individual elements a2nd the4 fac1t that positivity is preserved under i i strict entailment in each component. Then there is strict entailment addition and tensor produc(cid:74)t. T(cid:75)herefo(cid:74)re:(cid:75) between the sentences ϕ(Φ) and ϕ(Ψ). (cid:50) s s 1 kl 2 We consider a concrete example. as required. Compositionality of k-hyponymy in a transitive sentence. More examples may be found in appendix . Suppose we have a noun {| (cid:105)} 7. Conclusion space N with basis e , and sentence space S with basis {|x (cid:105)} We consi(cid:88)der theiveirbs nibble, scoff and the nouns cake, Integrating a logical framework with compositional distribu- j j choco(cid:74)late, w(cid:75)ith semantics: tional semantics is an important step in improving this model of nibble = (cid:88) a a |e (cid:105) (cid:104)e | ⊗ |x (cid:105) (cid:104)x | ⊗ |e (cid:105) (cid:104)e | language. By moving to the setting of density matrices, we have de- pqr tuv p t q u r v scribed a graded measure of entailment that may be used to describe (cid:74) (cid:75) pqrtuv the extent of entailment between two words represented within this scoff = (cid:88) b b |e (cid:105) (cid:104)e | ⊗ |x (cid:105) (cid:104)x | ⊗ |e (cid:105) (cid:104)e | enriched framework. This approach extends uniformly to provide pqr tuv p t q u r v (cid:74) (cid:75) entailment strengths between phrases of any type. We have also pqrtuv (cid:88) | (cid:105) (cid:104) | shown how a lower bound on entailment strength of phrases of the cake = cicj ei ej same structure can be calculated from their components. (cid:74) (cid:75) i We can extend this work in several directions. Firstly, we can | (cid:105) (cid:104) | chocolate = d d e e examine how narrowing down a concept using an adjective might i j i j operate. For example, we should have that red car entails car. i Other adjectives should not operate in this way, such as former which make these nouns and verbs pure states. The more general in former president. eat and sweets are given by: (cid:74) (cid:75) (cid:74) (cid:75) (cid:74) (cid:75) Another line of inquiry is to examine transitivity behaves. In eat = 1( nibble + scoff ) some cases entailment can strengthen. We had that dog entails pet (cid:74) (cid:75) 2 (cid:74) (cid:75) (cid:74) (cid:75) to a certain extent, and that pet entails mammal to a certain extent, 1 but that dog completely entails mammal. sweets = ( cake + chocolate ) 2 Our framework supports different methods of scaling the pos- Then (cid:74) (cid:75) (cid:74) (cid:75) itive operators representing propositions. Empirical work will be (cid:50) required to establish the most appropriate method in linguistic ap- (cid:74)scoff(cid:75) (cid:74)eat (cid:75) 1/2 plications. (cid:50) cake sweets Sentences with non-identical structure must also be taken into 1/2 account. One approach to this might be to look at the ﬁrst stage in We consider the sentences: the sentence reductions at which the elementwise comparison can s = John scoffs cake be made. For example, in the two sentences John runs very slowly, 1 s = John eats sweets and Hungry boys sprint quickly, we can compare the noun phrases 2 John, and Hungry boys, the verbs runs and sprints, and the adverb The semantic(cid:74)s of(cid:75)these s(cid:74)entenc(cid:75)es a(cid:74)re: (cid:75) (cid:74) (cid:75) phrases very slowly and quickly. Further, the inclusion of negative (cid:74)s (cid:75) = ϕ((cid:74)Mary(cid:75) ⊗ (cid:74)scoff(cid:75)s ⊗(cid:74) cake(cid:75)) words like not, or negative preﬁxes, should be modelled. 1 ⊗ ⊗ Acknowledgments s = ϕ( Mary eats (cid:74) (cid:75)sweet(cid:74)s )(cid:75) 2 (cid:74) (cid:75) (cid:50) Bob Coecke, Martha Lewis, and Daniel Marsden gratefully ac- and as per theorem 5, we will show that s s where kl = × 1 kl 2 knowledge funding from AFOSR grant Algorithmic and Logical 1 1 = 1 Expanding s we obtain: 2 2 (cid:74) 4(cid:75) (cid:74) (cid:75) 2 (cid:74) (cid:75) (cid:74) (cid:75) Aspects when Composing Meanings. ⊗ 1 s = ϕ( Mary ( nibbles + scoffs ) 2 (cid:74) (cid:75)2 (cid:74) (cid:75) References ⊗ 1 2(cid:74)( cak(cid:75)e +(cid:74) choc(cid:75))) (cid:74) (cid:75) E. Balkır. Using density matrices in a compositional distributional model 1 ⊗ ⊗ of meaning. Master’s thesis, University of Oxford, 2014. = (ϕ( M(cid:74)ary (cid:75) s(cid:74)coffs (cid:75) c(cid:74)ake )(cid:75) 4 E. Balkır, D. Kartsaklis, and M. Sadrzadeh. Sentence entailment in compo- + ϕ((cid:74)Mary(cid:75) ⊗ (cid:74)scoffs (cid:75)⊗ c(cid:74)hoc )(cid:75) sitional distributional semantics, 2015. To appear ISAIM 2016. + ϕ((cid:74)Mary(cid:75) ⊗ (cid:74)nibbles(cid:75) ⊗ (cid:74)cake(cid:75)) E. Balkır, M. Sadrzadeh, and B. Coecke. Distributional sentence entailment using density matrices. In Topics in Theoretical Computer Science, ⊗ ⊗ + ϕ( Mary nibbles choc )) pages 1–22. Springer, 2016. ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: then

text: some

text: dogs

text: bark

text: does

text: entail

text: some

text: pets

text: bark,

text: and

text: the

text: problem

text: is

text: s

text: choc

text: averted.

text: Discussion

text: of

text: the

text: behaviour

text: of

text: quantiﬁers

text: and

text: other

text: word

text: types

text: is

text: given

text: in

text: (MacCartney

text: and

text: Manning

text: The

text: quantity

text: kn

text: is

text: not

text: necessarily

text: maximal,

text: and

text: indeed

text: ϕ(

text: Mary

text: nibbles

text: choc

text: usually

text: is

text: not.

text: As

text: we

text: only

text: have

text: a

text: lower

text: bound,

text: zero

text: entailment

text: strength

text: between

text: a

text: pair

text: of

text: components

text: does

text: not

text: imply

text: zero

text: entail-

text: Therefore:

text: ment

text: strength

text: between

text: entire

text: sentences.

text: Results

text: for

text: phrases

text: involv-

text: ing

text: relative

text: clauses

text: be

text: found

text: in

text: ϕ(

text: Corollary

text: Consider

text: nibbles

text: choc

text: Φ

text: A

text: Ψ

text: B

text: i

text: i

text: i

text: i

text: We

text: can

text: see

text: that

text: s

text: s

text: is

text: positive

text: by

text: positivity

text: of

text: the

text: such

text: that

text: for

text: each

text: i

text: n}

text: we

text: have

text: A

text: B

text: i.e.

text: there

text: is

text: individual

text: elements

text: that

text: positivity

text: is

text: preserved

text: under

text: i

text: i

text: strict

text: entailment

text: in

text: each

text: component.

text: Then

text: there

text: is

text: strict

text: entailment

text: addition

text: and

text: tensor

text: between

text: the

text: sentences

text: ϕ(Φ)

text: and

text: ϕ(Ψ).

text: s

text: s

text: kl

text: We

text: consider

text: a

text: concrete

text: example.

text: as

text: required.

text: Compositionality

text: of

text: k-hyponymy

text: in

text: a

text: transitive

text: sentence.

text: More

text: examples

text: may

text: be

text: found

text: in

text: appendix

text: Suppose

text: we

text: have

text: a

text: noun

text: Conclusion

text: space

text: N

text: with

text: basis

text: e

text: and

text: sentence

text: space

text: S

text: with

text: basis

text: {|x

text: We

text: theiveirbs

text: nibble,

text: scoff

text: and

text: the

text: nouns

text: cake,

text: Integrating

text: a

text: logical

text: framework

text: with

text: compositional

text: distribu-

text: j

text: j

text: semantics:

text: tional

text: semantics

text: is

text: an

text: important

text: step

text: in

text: improving

text: this

text: model

text: of

text: nibble

text: a

text: a

text: |e

text: |x

text: |e

text: language.

text: By

text: moving

text: to

text: the

text: setting

text: of

text: density

text: matrices,

text: we

text: have

text: de-

text: pqr

text: tuv

text: p

text: t

text: q

text: u

text: r

text: v

text: scribed

text: a

text: graded

text: measure

text: of

text: entailment

text: that

text: may

text: be

text: used

text: to

text: describe

text: pqrtuv

text: the

text: extent

text: of

text: entailment

text: between

text: two

text: words

text: represented

text: within

text: this

text: scoff

text: b

text: b

text: |e

text: |x

text: |e

text: enriched

text: framework.

text: This

text: approach

text: extends

text: uniformly

text: to

text: provide

text: pqr

text: tuv

text: p

text: t

text: q

text: u

text: r

text: v

text: entailment

text: strengths

text: between

text: phrases

text: of

text: any

text: type.

text: We

text: have

text: also

text: pqrtuv

text: shown

text: how

text: a

text: lower

text: bound

text: on

text: entailment

text: strength

text: of

text: phrases

text: of

text: the

text: cake

text: cicj

text: ei

text: ej

text: same

text: structure

text: can

text: be

text: calculated

text: from

text: their

text: components.

text: i

text: We

text: can

text: extend

text: this

text: work

text: in

text: several

text: directions.

text: Firstly,

text: we

text: can

text: chocolate

text: d

text: d

text: e

text: e

text: examine

text: how

text: narrowing

text: down

text: a

text: concept

text: using

text: an

text: adjective

text: might

text: i

text: j

text: i

text: j

text: operate.

text: For

text: example,

text: we

text: should

text: have

text: that

text: red

text: car

text: entails

text: car.

text: i

text: Other

text: adjectives

text: should

text: not

text: operate

text: in

text: this

text: way,

text: such

text: as

text: former

text: which

text: make

text: these

text: nouns

text: and

text: verbs

text: pure

text: states.

text: The

text: more

text: general

text: in

text: former

text: president.

text: eat

text: and

text: sweets

text: are

text: given

text: by:

text: Another

text: line

text: of

text: inquiry

text: is

text: to

text: examine

text: transitivity

text: behaves.

text: In

text: eat

text: nibble

text: scoff

text: some

text: cases

text: entailment

text: can

text: strengthen.

text: We

text: had

text: that

text: dog

text: entails

text: pet

text: to

text: a

text: certain

text: extent,

text: and

text: that

text: pet

text: entails

text: mammal

text: to

text: a

text: certain

text: extent,

text: but

text: that

text: dog

text: completely

text: entails

text: mammal.

text: sweets

text: cake

text: chocolate

text: Our

text: framework

text: supports

text: different

text: methods

text: of

text: scaling

text: the

text: pos-

text: Then

text: itive

text: operators

text: representing

text: propositions.

text: Empirical

text: work

text: will

text: be

text: required

text: to

text: establish

text: the

text: most

text: appropriate

text: method

text: in

text: linguistic

text: ap-

text: plications.

text: cake

text: sweets

text: Sentences

text: with

text: non-identical

text: structure

text: must

text: also

text: be

text: taken

text: into

text: account.

text: One

text: approach

text: to

text: this

text: might

text: be

text: to

text: look

text: at

text: the

text: ﬁrst

text: stage

text: in

text: We

text: consider

text: the

text: sentences:

text: the

text: sentence

text: reductions

text: at

text: which

text: the

text: elementwise

text: comparison

text: can

text: s

text: John

text: scoffs

text: cake

text: be

text: made.

text: For

text: example,

text: in

text: the

text: two

text: sentences

text: John

text: runs

text: very

text: slowly,

text: s

text: John

text: eats

text: sweets

text: and

text: Hungry

text: boys

text: sprint

text: quickly,

text: we

text: can

text: compare

text: the

text: noun

text: phrases

text: John,

text: and

text: Hungry

text: boys,

text: the

text: verbs

text: runs

text: and

text: sprints,

text: and

text: the

text: adverb

text: The

text: phrases

text: very

text: slowly

text: and

text: quickly.

text: Further,

text: the

text: inclusion

text: of

text: negative

text: words

text: like

text: not,

text: or

text: negative

text: preﬁxes,

text: should

text: be

text: modelled.

text: Acknowledgments

text: s

text: ϕ(

text: Mary

text: eats

text: Bob

text: Coecke,

text: Martha

text: Lewis,

text: and

text: Daniel

text: Marsden

text: gratefully

text: ac-

text: and

text: as

text: per

text: theorem

text: we

text: will

text: show

text: that

text: s

text: s

text: where

text: kl

text: kl

text: knowledge

text: funding

text: from

text: AFOSR

text: grant

text: Algorithmic

text: and

text: Logical

text: Expanding

text: s

text: we

text: obtain:

text: Aspects

text: when

text: Composing

text: Meanings.

text: s

text: ϕ(

text: Mary

text: nibbles

text: scoffs

text: References

text: E.

text: Balkır.

text: Using

text: density

text: matrices

text: in

text: a

text: compositional

text: distributional

text: model

text: of

text: meaning.

text: Master’s

text: thesis,

text: University

text: of

text: Oxford,

text: (ϕ(

text: E.

text: Balkır,

text: D.

text: Kartsaklis,

text: and

text: M.

text: Sadrzadeh.

text: Sentence

text: entailment

text: in

text: compo-

text: sitional

text: distributional

text: semantics,

text: To

text: appear

text: ISAIM

text: E.

text: Balkır,

text: M.

text: Sadrzadeh,

text: and

text: B.

text: Coecke.

text: Distributional

text: sentence

text: entailment

text: using

text: density

text: matrices.

text: In

text: Topics

text: in

text: Theoretical

text: Computer

text: Science,

text: ϕ(

text: Mary

text: nibbles

text: choc

text: pages

text: Springer,

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: Vol. 00, XX Term inequalities in ﬁnite algebras 3 a uniﬁer and the corresponding substitution is a uniﬁcation. In other words, the terms s and t can be uniﬁed iﬀ they can not be separated in a free algebra. While much work on uniﬁcation is concerned with algorithms, we will follow the more abstract approach in [1], which was ﬁrst presented by G.P. Huet in [6]. As in its Deﬁnition 2.11, we consider equivalence relations on groupoid terms, which we call term relations. A term relation is said to be homogeneous if no terms of the form f(. . . ) and g(. . . ) are ever equivalent for distinct operation symbols f and g. ≡ ≺ Given a term relation , we let be the “is equivalent to a subterm of” ≺ ≡ relation. That is, p q iﬀ there is some subterm r of q with p r. We say ≺ ≺ ≺ that a sequence p p . . . p is a -cycle iﬀ p = p and at least one of 0 1 m m 0 ≡ the subterm relationships is proper. Then the term relation is acyclic iﬀ it ≺ has no -cycles. (This follows the deﬁnition of ‘acyclic’ used in papers such as [4]. The deﬁnition in [1] merely says that a term relation is ‘acyclic’ if no term is equivalent to one of its proper subterms, which is incorrect.) This leads to the following deﬁnition. ≡ Deﬁnition 1.1. A term relation is a uniﬁcation relation iﬀ it is homoge- ≡ neous, acyclic, and satisﬁes the following uniﬁcation axiom: Whenever s t where s is f(p , p , . . . p ) and t is f(q , q , . . . q ) for the same n-ary basic 1 2 ≡ n ≡ 1 ≡2 n operation f, then p q , p q , . . . p q . 1 1 2 2 n n Referring again to [1] for the details, we have that terms s and t can be ≡ ≡ uniﬁed iﬀ there is a uniﬁcation relation with s t. If there is such a uniﬁcation relation, then there is a unique minimal one, the uniﬁcation closure of s and t. If s and t can be uniﬁed, they also have a most general uniﬁer or mgu, where any uniﬁer of s and t can be obtained from their mgu by uniformly substituting terms for its variables. This most general uniﬁer is unique up to renaming its variables, and can be easily constructed from the uniﬁcation closure of s and t. For example, let (cid:63) be an inﬁx binary operation, and consider s = (x(cid:63)y)(cid:63)(z(cid:63) y) and t = z (cid:63) ((x (cid:63) y) (cid:63) (x (cid:63) x)). We will attempt to construct their uniﬁcation ≡ ≡ closure and the corresponding mgu. We must have s t, and start with ≡ ≡ this. Using the uniﬁcation axiom, we obtain x(cid:63)y z and z(cid:63)y (x(cid:63)y)(cid:63)(x(cid:63)x). ≡ Applying the uniﬁcation axiom again to the last equivalence, we get z x(cid:63)y (a ≡ ≡ duplicate) and y x(cid:63)x. The non-singleton classes of that contain variables { } { } are now y, x (cid:63) x and z, x (cid:63) y , where x is in a class by itself. To construct the mgu, we pick a representative of each class, where we must pick a non-variable term if there is one in the class. Letting u, v and w be arbitrary terms, we let ς(w) be the representative of the class of w. In our example, this gives ς(y) = x (cid:63) x, ς(z) = x (cid:63) y, and ς(x) = x. Now we recursively deﬁne the function σ from terms to terms by letting σ(w) be ς(w) if ς(w) is a variable, and letting σ(w) be σ(u) (cid:63) σ(v) if ς(w) is u (cid:63) v. In our example, this gives σ(s) = σ(x (cid:63) y) (cid:63) σ(z (cid:63) y) = (σ(x) (cid:63) σ(y)) (cid:63) (σ(z) (cid:63) σ(y)) = (x(cid:63)(σ(x)(cid:63)σ(x)))(cid:63)((σ(x)(cid:63)σ(y))(cid:63)(σ(x)(cid:63)σ(x))) = (x(cid:63)(x(cid:63)x))(cid:63)((x(cid:63)(x(cid:63)x))(cid:63)(x(cid:63)x)),

text: Vol.

text: XX

text: Term

text: inequalities

text: in

text: ﬁnite

text: algebras

text: a

text: uniﬁer

text: and

text: the

text: corresponding

text: substitution

text: is

text: a

text: uniﬁcation.

text: In

text: other

text: words,

text: the

text: terms

text: s

text: and

text: t

text: can

text: be

text: uniﬁed

text: iﬀ

text: they

text: can

text: not

text: be

text: separated

text: in

text: a

text: free

text: algebra.

text: While

text: much

text: work

text: on

text: uniﬁcation

text: is

text: concerned

text: with

text: algorithms,

text: we

text: will

text: follow

text: the

text: more

text: abstract

text: approach

text: in

text: which

text: was

text: ﬁrst

text: presented

text: by

text: G.P.

text: Huet

text: in

text: As

text: in

text: its

text: Deﬁnition

text: we

text: consider

text: equivalence

text: relations

text: on

text: groupoid

text: terms,

text: which

text: we

text: call

text: term

text: relations.

text: A

text: term

text: relation

text: is

text: said

text: to

text: be

text: homogeneous

text: if

text: no

text: terms

text: of

text: the

text: form

text: f(.

text: and

text: g(.

text: are

text: ever

text: equivalent

text: for

text: distinct

text: operation

text: symbols

text: f

text: and

text: g.

text: Given

text: a

text: term

text: relation

text: we

text: let

text: be

text: the

text: “is

text: equivalent

text: to

text: a

text: subterm

text: of”

text: relation.

text: That

text: is,

text: p

text: q

text: iﬀ

text: there

text: is

text: some

text: subterm

text: r

text: of

text: q

text: with

text: p

text: r.

text: We

text: say

text: that

text: a

text: sequence

text: p

text: p

text: p

text: is

text: a

text: -cycle

text: iﬀ

text: p

text: p

text: and

text: at

text: least

text: one

text: of

text: m

text: m

text: the

text: subterm

text: relationships

text: is

text: proper.

text: Then

text: the

text: term

text: relation

text: is

text: acyclic

text: iﬀ

text: it

text: has

text: no

text: -cycles.

text: (This

text: follows

text: the

text: deﬁnition

text: of

text: ‘acyclic’

text: used

text: in

text: papers

text: such

text: as

text: The

text: deﬁnition

text: in

text: merely

text: says

text: that

text: a

text: term

text: relation

text: is

text: ‘acyclic’

text: if

text: no

text: term

text: is

text: equivalent

text: to

text: one

text: of

text: its

text: proper

text: subterms,

text: which

text: is

text: incorrect.)

text: This

text: leads

text: to

text: the

text: following

text: deﬁnition.

text: Deﬁnition

text: A

text: term

text: relation

text: is

text: a

text: uniﬁcation

text: relation

text: iﬀ

text: it

text: is

text: homoge-

text: neous,

text: acyclic,

text: and

text: satisﬁes

text: the

text: following

text: uniﬁcation

text: axiom:

text: Whenever

text: s

text: t

text: where

text: s

text: is

text: f(p

text: p

text: p

text: and

text: t

text: is

text: f(q

text: q

text: q

text: for

text: the

text: same

text: n-ary

text: basic

text: n

text: ≡2

text: n

text: operation

text: f,

text: then

text: p

text: q

text: p

text: q

text: p

text: q

text: n

text: n

text: Referring

text: again

text: to

text: for

text: the

text: details,

text: we

text: have

text: that

text: terms

text: s

text: and

text: t

text: can

text: be

text: uniﬁed

text: iﬀ

text: there

text: is

text: a

text: uniﬁcation

text: relation

text: with

text: s

text: t.

text: If

text: there

text: is

text: such

text: a

text: uniﬁcation

text: relation,

text: then

text: there

text: is

text: a

text: unique

text: minimal

text: one,

text: the

text: uniﬁcation

text: closure

text: of

text: s

text: and

text: t.

text: If

text: s

text: and

text: t

text: can

text: be

text: uniﬁed,

text: they

text: also

text: have

text: a

text: most

text: general

text: uniﬁer

text: or

text: mgu,

text: where

text: any

text: uniﬁer

text: of

text: s

text: and

text: t

text: can

text: be

text: obtained

text: from

text: their

text: mgu

text: by

text: uniformly

text: substituting

text: terms

text: for

text: its

text: variables.

text: This

text: most

text: general

text: uniﬁer

text: is

text: unique

text: up

text: to

text: renaming

text: its

text: variables,

text: and

text: can

text: be

text: easily

text: constructed

text: from

text: the

text: uniﬁcation

text: closure

text: of

text: s

text: and

text: t.

text: For

text: example,

text: let

text: be

text: an

text: inﬁx

text: binary

text: operation,

text: and

text: consider

text: s

text: y)

text: and

text: t

text: z

text: ((x

text: y)

text: (x

text: x)).

text: We

text: will

text: attempt

text: to

text: construct

text: their

text: uniﬁcation

text: closure

text: and

text: the

text: corresponding

text: mgu.

text: We

text: must

text: have

text: s

text: t,

text: and

text: start

text: with

text: this.

text: Using

text: the

text: uniﬁcation

text: axiom,

text: we

text: obtain

text: z

text: and

text: Applying

text: the

text: uniﬁcation

text: axiom

text: again

text: to

text: the

text: last

text: equivalence,

text: we

text: get

text: z

text: (a

text: duplicate)

text: and

text: y

text: The

text: non-singleton

text: classes

text: of

text: that

text: contain

text: variables

text: are

text: now

text: y,

text: x

text: x

text: and

text: z,

text: x

text: y

text: where

text: x

text: is

text: in

text: a

text: class

text: by

text: itself.

text: To

text: construct

text: the

text: mgu,

text: we

text: pick

text: a

text: representative

text: of

text: each

text: class,

text: where

text: we

text: must

text: pick

text: a

text: non-variable

text: term

text: if

text: there

text: is

text: one

text: in

text: the

text: class.

text: Letting

text: u,

text: v

text: and

text: w

text: be

text: arbitrary

text: terms,

text: we

text: let

text: ς(w)

text: be

text: the

text: representative

text: of

text: the

text: class

text: of

text: w.

text: In

text: our

text: example,

text: this

text: gives

text: ς(y)

text: x

text: x,

text: ς(z)

text: x

text: y,

text: and

text: ς(x)

text: x.

text: Now

text: we

text: recursively

text: deﬁne

text: the

text: function

text: σ

text: from

text: terms

text: to

text: terms

text: by

text: letting

text: σ(w)

text: be

text: ς(w)

text: if

text: ς(w)

text: is

text: a

text: variable,

text: and

text: letting

text: σ(w)

text: be

text: σ(u)

text: σ(v)

text: if

text: ς(w)

text: is

text: u

text: v.

text: In

text: our

text: example,

text: this

text: gives

text: σ(s)

text: σ(x

text: y)

text: σ(z

text: y)

text: (σ(x)

text: σ(y))

text: (σ(z)

text: σ(y))


text: 8 D. Hobby Algebra univers. explicitly represented with equivalent expressions. This can be easily achieved by appropriate choices of values for the indices, and will not jeopardize the ﬁniteness of any algebras we produce. As long as there are no collisions, alge- bras obtained for diﬀerent values of a will be isomorphic. Accordingly, we will (cid:107) (cid:107) speak of the algebra operation 2, f f , 0 , etc. 2 3 (cid:107) (cid:107) Extending this idea, we can deﬁne the transformation j, ρ, k that takes the j-th component to the k-th component along path ρ, where ρ is any non-empty string. Deﬁnition 2.1. If ρ is f for some operation symbol f = f(x , . . . , x , . . . , x ), (cid:107) (cid:107) i 1 i (cid:54) n we deﬁne j, f , k by the equation f[k] := x [j]. If ρ is f σ where σ = Λ, we (cid:107) (cid:107)i (cid:107) (cid:107) (cid:107) (cid:107) i i deﬁne j, ρ, k to be j, σ, m + m, f , k , where m is understood to be an i index not used elsewhere. This deﬁnition produces a sum of transformations for possibly many dif- ferent operations, which is not a problem. To recover the actual operations from a sum of transformations, Σ, we merely let each operation be the sum of the transformations and constant vectors that reference that operation, where (cid:104) (cid:105) operations that are not referenced have constant value 0, 0, 0, . . . . We denote the algebra with operations deﬁned this way by Alg(Σ). Our understanding is that only indices with non-zero components are used in Alg(Σ), so it is ﬁnite and unique up to isomorphism. (cid:107) (cid:107) The idea is that m, ρ, n transfers the value of the m-th component of the vector with path ρ in the term s to the n-th component of the result of s, with as few side eﬀects as possible. We are assuming that none of the indices used (cid:107) (cid:107) to deﬁne m, ρ, n is equal to any of the others, except that possibly m = n. (cid:107) (cid:107) In other words, the operation m, ρ, n is duplicate free. If m is distinct 1 from both m and m , and µ and ν are strings in P, then the operation (cid:107) (cid:107) 2(cid:107) 0 (cid:107) m , ν, m + m , µ, m is duplicate free by our convention that indices are 2 1 1 0 (cid:107) (cid:107) (cid:107) (cid:107) chosen to minimize collisions. In isolation, the sum m , ν, m + m , µ, m (cid:107) (cid:107) 2 1 1 0 is equivalent to m , µν, m . The one diﬀerence is that the former explicitly 2 0 mentions the index m . 1 (cid:107) (cid:107) Lemma 2.2. Let the algebra operation m, ρ, n be duplicate free where ∈ ρ P. Suppose that t is a term, and let s be a subterm of t with path ρ. Then t[n] = s[m]. · · · Proof. We let ρ = ρ ρ ρ ρ , where each of the ρ is a subscripted basic 0 1 2 j i operation symbol. We will prove the lemma by induction on j. Our basis is (cid:107) (cid:107) when j = 0, making the operation m, ρ , n . Assume that ρ is f and 0 0 i f is k-ary, so s is f(u , . . . u − , t, u , . . . u ), where the u are terms. The 1 i 1 i+1 k j only assignment to t[n] is then made by f[n] := x [m] , giving t[n] = f[n] = i x [m] = s[m], as desired. For the induction step, assume the statement is i − · · · true for j 1, and that we want to show it for the path ρ = ρ ρ ρ ρ . (cid:107) (cid:107) (cid:107) (cid:107) (cid:107) · · · (cid:107) 0 1 2 j We write m, ρ, n as m, ρ , b + b, ρ ρ ρ ρ − , n for some new index · · · j 0 1 2 j 1 − b, and let ψ be ρ ρ ρ − , so ρ = ψρ . By the statement for j 1, 0 1 j 1 j t[n] = u[b], where u is the subterm of s with path ψ. We assume ρ is f , and j i

text: D.

text: Hobby

text: Algebra

font: NTGOIH+NimbusSanL-Regu

text: univers.

text: explicitly

text: represented

text: with

text: equivalent

text: expressions.

text: This

text: can

text: be

text: easily

text: achieved

text: by

text: appropriate

text: choices

text: of

text: values

text: for

text: the

text: indices,

text: and

text: will

text: not

text: jeopardize

text: the

text: ﬁniteness

text: of

text: any

text: algebras

text: we

text: produce.

text: As

text: long

text: as

text: there

text: are

text: no

text: collisions,

text: alge-

text: bras

text: obtained

text: for

text: diﬀerent

text: values

text: of

text: a

text: will

text: be

text: isomorphic.

text: Accordingly,

text: we

text: will

text: speak

text: of

text: the

text: algebra

text: operation

text: f

text: f

text: etc.

text: Extending

text: this

text: idea,

text: we

text: can

text: deﬁne

text: the

text: transformation

text: j,

text: ρ,

text: k

text: that

text: takes

text: the

text: j-th

text: component

text: to

text: the

text: k-th

text: component

text: along

text: path

text: ρ,

text: where

text: ρ

text: is

text: any

text: non-empty

text: string.

text: Deﬁnition

text: If

text: ρ

text: is

text: f

text: for

text: some

text: operation

text: symbol

text: f

text: f(x

text: x

text: x

text: i

text: i

text: n

text: we

text: deﬁne

text: j,

text: f

text: k

text: by

text: the

text: equation

text: f[k]

text: x

text: [j].

text: If

text: ρ

text: is

text: f

text: σ

text: where

text: σ

text: Λ,

text: we

text: i

text: i

text: deﬁne

text: j,

text: ρ,

text: k

text: to

text: be

text: j,

text: σ,

text: m

text: m,

text: f

text: k

text: where

text: m

text: is

text: understood

text: to

text: be

text: an

text: i

text: index

text: not

text: used

text: elsewhere.

text: This

text: deﬁnition

text: produces

text: a

text: sum

text: of

text: transformations

text: for

text: possibly

text: many

text: dif-

text: ferent

text: operations,

text: which

text: is

text: not

text: a

text: problem.

text: To

text: recover

text: the

text: actual

text: operations

text: from

text: a

text: sum

text: of

text: transformations,

text: Σ,

text: we

text: merely

text: let

text: each

text: operation

text: be

text: the

text: sum

text: of

text: the

text: transformations

text: and

text: constant

text: vectors

text: that

text: reference

text: that

text: operation,

text: where

text: operations

text: that

text: are

text: not

text: referenced

text: have

text: constant

text: value

text: We

text: denote

text: the

text: algebra

text: with

text: operations

text: deﬁned

text: this

text: way

text: by

text: Alg(Σ).

text: Our

text: understanding

text: is

text: that

text: only

text: indices

text: with

text: non-zero

text: components

text: are

text: used

text: in

text: Alg(Σ),

text: so

text: it

text: is

text: ﬁnite

text: and

text: unique

text: up

text: to

text: isomorphism.

text: The

text: idea

text: is

text: that

text: m,

text: ρ,

text: n

text: transfers

text: the

text: value

text: of

text: the

text: m-th

text: component

text: of

text: the

text: vector

text: with

text: path

text: ρ

text: in

text: the

text: term

text: s

text: to

text: the

text: n-th

text: component

text: of

text: the

text: result

text: of

text: s,

text: with

text: as

text: few

text: side

text: eﬀects

text: as

text: possible.

text: We

text: are

text: assuming

text: that

text: of

text: the

text: indices

text: used

text: to

text: deﬁne

text: m,

text: ρ,

text: n

text: is

text: equal

text: to

text: any

text: of

text: the

text: others,

text: except

text: that

text: possibly

text: m

text: n.

text: In

text: other

text: words,

text: the

text: operation

text: m,

text: ρ,

text: n

text: is

text: duplicate

text: free.

text: If

text: m

text: is

text: distinct

text: from

text: both

text: m

text: and

text: m

text: and

text: µ

text: and

text: ν

text: are

text: strings

text: in

text: P,

text: then

text: the

text: operation

text: m

text: ν,

text: m

text: m

text: µ,

text: m

text: is

text: duplicate

text: free

text: by

text: our

text: convention

text: that

text: indices

text: are

text: chosen

text: to

text: minimize

text: collisions.

text: In

text: isolation,

text: the

text: sum

text: m

text: ν,

text: m

text: m

text: µ,

text: m

text: is

text: equivalent

text: to

text: m

text: µν,

text: m

text: The

text: one

text: diﬀerence

text: is

text: that

text: the

text: former

text: explicitly

text: mentions

text: the

text: index

text: m

text: Lemma

text: Let

text: the

text: algebra

text: operation

text: m,

text: ρ,

text: n

text: be

text: duplicate

text: free

text: where

text: ρ

text: P.

text: Suppose

text: that

text: t

text: is

text: a

text: term,

text: and

text: let

text: s

text: be

text: a

text: subterm

text: of

text: t

text: with

text: path

text: ρ.

text: Then

text: t[n]

text: s[m].

text: Proof.

text: We

text: let

text: ρ

text: ρ

text: ρ

text: ρ

text: ρ

text: where

text: each

text: of

text: the

text: ρ

text: is

text: a

text: subscripted

text: basic

text: j

text: i

text: operation

text: symbol.

text: We

text: will

text: prove

text: the

text: lemma

text: by

text: induction

text: on

text: j.

text: Our

text: basis

text: is

text: when

text: j

text: making

text: the

text: operation

text: m,

text: ρ

text: n

text: Assume

text: that

text: ρ

text: is

text: f

text: and

text: i

text: f

text: is

text: k-ary,

text: so

text: s

text: is

text: f(u

text: u

text: t,

text: u

text: u

text: where

text: the

text: u

text: are

text: terms.

text: The

text: i

text: k

text: j

text: only

text: assignment

text: to

text: t[n]

text: is

text: then

text: made

text: by

text: f[n]

text: x

text: [m]

text: giving

text: t[n]

text: f[n]

text: i

text: x

text: [m]

text: s[m],

text: as

text: desired.

text: For

text: the

text: induction

text: step,

text: assume

text: the

text: statement

text: is

text: i

text: true

text: for

text: j

text: and

text: that

text: we

text: want

text: to

text: show

text: it

text: for

text: the

text: path

text: ρ

text: ρ

text: ρ

text: ρ

text: ρ

text: j

text: We

text: write

text: m,

text: ρ,

text: n

text: as

text: m,

text: ρ

text: b

text: b,

text: ρ

text: ρ

text: ρ

text: ρ

text: n

text: for

text: some

text: new

text: index

text: j

text: j

text: b,

text: and

text: let

text: ψ

text: be

text: ρ

text: ρ

text: ρ

text: so

text: ρ

text: ψρ

text: By

text: the

text: statement

text: for

text: j

text: j

text: j

text: t[n]

text: u[b],

text: where

text: u

text: is

text: the

text: subterm

text: of

text: s

text: with

text: path

text: ψ.

text: We

text: assume

text: ρ

text: is

text: f

text: and

text: j

text: i


text: ∈ H Proof. The variational formulation of problem (2.17), (2.24), (2.25) reads: to ﬁnd w fulﬁlling the integral identity (cid:18) (cid:19) (cid:0) (cid:1) (cid:0) (cid:1) (cid:88) (cid:16) (cid:17) 2 AD ∇ D ∇ ∂v ∀ ∈ H ( )w, ( )v = g0, v + (g , v ) + gi, 3 , v . (2.35) y y ω 3 3 ω i i ω 3 ∂yi ω i=1 The latter, as usual, is obtained by multiplying system (2.17) scalarly with a test function ∈ H v and integrating by parts in ω with the help of conditions (2.24), (2.25) for v and the formula for g in (2.33). Clearly, the right-hand side of (2.35) is a continuous linear functional H (cid:51) 3 H in v. The left-hand side of (2.35) may be chosen as a scalar product in . Indeed, the necessary properties of this bi-linear form are inherited from the positive deﬁniteness of the A matrix 0 together with the following Friedrichs and Korn inequalities: || || ≤ ||∇ || ∀ ∈ u; L2 (ω) c u; L2 (ω) , u H1 (ω; ∂ω) , (2.36) ω y 0 ||∇ (cid:48) || ≤ ||D(cid:48) ∇ (cid:48) || ∀ (cid:48) ∈ w ; L2 (ω) c ( ) w ; L2 (ω) , w H1 (ω; ∂ω)2 . y ω y 0 (cid:26) (cid:27) (cid:0) (cid:1) Equivalently, we may write equation (2.35) as the minimization problem 1 AD ∇ D ∇ − ∈ H min ( )w, ( )w (g, w) : w 2 y y ω ω ⊂ where g = (g , g , g ) is given by (2.33). Notice that the Sobolev embedding theorem H2 C R 1 2 3H × in 2 assures that is a closed subspace in H1 (ω)2 H2 (ω) and the second inequality in (cid:48) (2.36) can be easily derived by integration by parts because w vanishes at ∂ω. Now the Riesz representation theorem guarantees the existence of a unique weak solution to problem (2.35) and the estimate || × || ≤ N w; H1 (ω)2 H2 (ω) c . Finally, a result in [14, Ch.2] on lifting smoothness of solutions to elliptic problems, see also [5] ∈ × for details about the fourth-order equation, concludes with the inclusion w H2 (ω)2 H3 (ω) (cid:4) and inequality (2.34). A classical assertion, cf. [7, 8, 13, 32] and others, was outlined in Theorem 7 of [4], namely the rescaled displacements h3/2u (h, y, hζ) and h1/2u (h, y, hζ) , i = 1, 2, taken from the three- 3 ×i − → dimensional problem (1.4)-(1.7), converge in L2 (ω ( 1/2, 1/2)) as h +0 to the functions − (cid:62) w (y) and w (y) ζ ∂w3 (y) , respectively, where w = (w , w , w ) is the solution of the two- 3 i ∂yi 1 2 3 dimensional Dirichlet-Sobolev problem given in Proposition 3. Moreover, the convergence rate | |− O( ln h 1/2), see Theorem 8 and Remark 6, is rather slow and in the next section we will improve the asymptotic result by constructing three-dimensional boundary layers studied in [4, 18, 21]. 11 ##LTLine## ##LTLine## ##LTLine##

text: H

text: Proof.

text: The

text: variational

text: formulation

text: of

text: problem

text: reads:

text: to

text: ﬁnd

text: w

text: fulﬁlling

text: the

text: integral

text: identity

label: equation

text: AD

text: D

text: ∂v

text: H

text: )w,

text: )v

text: v

text: (g

text: v

text: gi,

text: v

text: y

text: y

text: ω

text: ω

text: i

text: i

text: ω

text: ∂yi

text: ω

text: The

text: latter,

text: as

text: usual,

text: is

text: obtained

text: by

text: multiplying

text: system

text: scalarly

text: with

text: a

text: test

text: function

text: H

text: v

text: and

text: integrating

text: by

text: parts

text: in

text: ω

text: with

text: the

text: help

text: of

text: conditions

text: for

text: v

text: and

text: the

text: formula

text: for

text: g

text: in

text: Clearly,

text: the

text: right-hand

text: side

text: of

text: is

text: a

text: continuous

text: linear

text: functional

text: H

text: H

text: in

text: v.

text: The

text: left-hand

text: side

text: of

text: may

text: be

text: chosen

text: as

text: a

text: scalar

text: product

text: in

text: Indeed,

text: the

text: necessary

text: properties

text: of

text: this

text: bi-linear

text: form

text: are

text: inherited

text: from

text: the

text: positive

text: deﬁniteness

text: of

text: the

text: A

text: matrix

text: together

text: with

text: the

text: following

text: Friedrichs

text: and

text: Korn

text: inequalities:

text: u;

text: (ω)

text: c

text: u;

text: (ω)

text: u

text: (ω;

text: ∂ω)

text: ω

text: y

text: w

text: (ω)

text: c

text: w

text: (ω)

text: w

text: (ω;

text: ∂ω)2

text: y

text: ω

text: y

text: Equivalently,

text: we

text: may

text: write

text: equation

text: as

text: the

text: minimization

text: problem

text: AD

text: D

text: H

text: min

text: )w,

text: )w

text: (g,

text: w)

text: w

text: y

text: y

text: ω

text: ω

text: where

text: g

text: (g

text: g

text: g

text: is

text: given

text: by

text: Notice

text: that

text: the

text: Sobolev

text: embedding

text: theorem

text: C

text: R

text: in

text: assures

text: that

text: is

text: a

text: closed

text: subspace

text: in

text: (ω)

text: and

text: the

text: second

text: inequality

text: in

text: can

text: be

text: easily

text: derived

text: by

text: integration

text: by

text: parts

text: because

text: w

text: vanishes

text: at

text: ∂ω.

text: Now

text: the

text: Riesz

text: representation

text: theorem

text: guarantees

text: the

text: existence

text: of

text: a

text: unique

text: weak

text: solution

text: to

text: problem

text: and

text: the

text: estimate

text: N

text: w;

text: (ω)

text: c

text: Finally,

text: a

text: result

text: in

text: on

text: lifting

text: smoothness

text: of

text: solutions

text: to

text: elliptic

text: problems,

text: see

text: also

text: for

text: details

text: about

text: the

text: fourth-order

text: equation,

text: concludes

text: with

text: the

text: inclusion

text: w

text: (ω)

text: and

text: inequality

text: A

text: classical

text: assertion,

text: cf.

text: and

text: others,

text: was

text: outlined

text: in

text: Theorem

text: of

text: namely

text: the

text: rescaled

text: displacements

text: (h,

text: y,

text: hζ)

text: and

text: (h,

text: y,

text: hζ)

text: i

text: taken

text: from

text: the

text: three-

text: ×i

text: dimensional

text: problem

text: converge

text: in

text: (ω

text: as

text: h

text: to

text: the

text: functions

text: w

text: (y)

text: and

text: w

text: (y)

text: ζ

text: (y)

text: respectively,

text: where

text: w

text: (w

text: w

text: w

text: is

text: the

text: solution

text: of

text: the

text: two-

text: i

text: ∂yi

text: dimensional

text: Dirichlet-Sobolev

text: problem

text: given

text: in

text: Proposition

text: Moreover,

text: the

text: convergence

text: rate

text: O(

text: ln

text: h

text: see

text: Theorem

text: and

text: Remark

text: is

text: rather

text: slow

text: and

text: in

text: the

text: next

text: section

text: we

text: will

text: improve

text: the

text: asymptotic

text: result

text: by

text: constructing

text: three-dimensional

text: boundary

text: layers

text: studied

text: in

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: see Theorem 8, becomes too sluggish so that cannot maintain an engineering application. (cid:0) (cid:1) An acceptable error estimate in Theorem 7, comparable with the usual one in the Kirchhoﬀ theory, requires to include into the asymptotic form the three-dimensional elastic ﬁeld, that is P − the elastic logarithmical capacit(cid:98)y potential ε 1x in Section 3.5 of [4] which is not described (cid:0) (cid:1) explicitly yet even for the disk θ of radius h and the isotropic material. However, replacing h∈ × in (4.17) the regular solution w H1 (ω)2 H2 (ω) of the Dirichlet-Sobolev problem (2.17), | | (2.24), (2.25) for the singular solution (3.17) procures the convergence rate O h1/2 ln h in (cid:98) − → h1/2u (h, y, hζ) w (ln h, y) + ζ ∂w3 (ln h, y) 0, i = 1, 2, (4.18) i i −∂yi → × − h3/2u (h, y, hζ) w (ln h, y) 0 in L2 (ω ( 1/2, 1/2)) , 3 3 however in the Lebesgue, not Sobolev norm. ∈ × The problem to determine the necessary singular solution w L2 (ω)2 H1 (ω) is well-posed with diﬀerent formulations in Sections 4.3 and 4.4. Its structure (3.17), (3.23) of w, refers to the Green matrix (3.15), (3.16) and the integral characteristics C(cid:93) (A, θ) in the representation P of the logarithmic elastic potential in the elastic layer, see Theorem 13 in [4]. The elastic × logarithmic capacity matrix is a numeral 4 4-matrix and can be computed numerically. Convergence (4.18) does not provide information about the stress and strain ﬁelds in the plate, however, using a technique of local estimates in [19, 23], it is possible to verify that, under certain restrictions on the volume forces (3.26), this convergence becomes pointwise outside a neighborhood of θ . We mention that, as discovered in [34], see also [24], pointwise convergence h of stresses and strains is always broken near the clamped edge υ of the plate with or without h small perturbation at θ . h Both, the asymptotic procedure and the models, can be easily adapted to the plate (1.1) ± with several small support areas θ1, ..., θJ sparsely distributed on one or two bases Σ . h h A h In view of block-diagonal structure (2.26) of the matrix the Dirichlet-Sobolev problem (cid:48) (2.17), (2.24), (2.25) naturally decouples into independent problems for the vector w = (w , w ) (cid:8) (cid:9) 1 2 of longitudinal displacements and the deﬂection w . Since the elasticity problem for the inﬁnite R × − 3 × {− } layer Λ = 2 ( 1/2, 1/2) clamped over the only area θ 1/2 loses the symmetry with ∈ R respect to the plane ξ 3 : ξ = ζ = 0 , the elastic capacity matrix C(cid:93) does not get in general 3 a block-diagonal structure and thus the relationship imposed in (4.4) on the regular and similar (cid:48) (cid:48) components of the solution w = (w , w ) of the model equation (4.9) couples the vector w and | |− 3 the scalar w at the level O( ln h 1). 3 References [1] Berezin F.A., Faddeev L.D., Remark on the Schr¨odinger equation with singular potential. Dokl. Akad. Nauk SSSR, 137 (1961) 1011–1014. [2] Birman M. S., Solomyak M.Z., Spectral Theory of Self-Adjoint Operators in Hilbert Space. Reidel Publishing Company, Dordrecht, 1986. [3] Bunoiu R., Cardone G., Nazarov S.A., Scalar boundary value problems on junctions of thin rods and plates. I. Asymptotic analysis and error estimates, ESAIM: Math. Model. Num. Anal., 48 (2014), 1495–1528. 32 ##LTLine## ##LTLine##

text: see

text: Theorem

text: becomes

text: too

text: sluggish

text: so

text: that

text: cannot

text: maintain

text: an

text: engineering

text: application.

text: An

text: acceptable

text: error

text: estimate

text: in

text: Theorem

text: comparable

text: with

text: the

text: usual

text: one

text: in

text: the

text: Kirchhoﬀ

text: theory,

text: requires

text: to

text: include

text: into

text: the

text: asymptotic

text: form

text: the

text: three-dimensional

text: elastic

text: ﬁeld,

text: that

text: is

text: P

text: the

text: elastic

text: logarithmical

text: potential

text: ε

text: in

text: Section

text: of

text: which

text: is

text: not

text: described

text: explicitly

text: yet

text: even

text: for

text: the

text: disk

text: θ

text: of

text: radius

text: h

text: and

text: the

text: isotropic

text: material.

text: However,

text: replacing

text: h∈

text: in

text: the

text: regular

text: solution

text: w

text: (ω)

text: of

text: the

text: Dirichlet-Sobolev

text: problem

text: for

text: the

text: singular

text: solution

text: procures

text: the

text: convergence

text: rate

text: O

text: ln

text: h

text: in

text: (h,

text: y,

text: hζ)

text: w

text: (ln

text: h,

text: y)

text: ζ

text: (ln

text: h,

text: y)

text: i

text: i

text: i

text: −∂yi

text: (h,

text: y,

text: hζ)

text: w

text: (ln

text: h,

text: y)

text: in

text: (ω

text: however

text: in

text: the

text: Lebesgue,

text: not

text: Sobolev

text: norm.

text: The

text: problem

text: to

text: determine

text: the

text: necessary

text: singular

text: solution

text: w

text: (ω)

text: is

text: well-posed

text: with

text: diﬀerent

text: formulations

text: in

text: Sections

text: and

text: Its

text: structure

text: of

text: w,

text: refers

text: to

text: the

text: Green

text: matrix

text: and

text: the

text: integral

text: characteristics

text: (A,

text: θ)

text: in

text: the

text: representation

text: P

text: of

text: the

text: logarithmic

text: elastic

text: potential

text: in

text: the

text: elastic

text: layer,

text: see

text: Theorem

text: in

text: The

text: elastic

text: logarithmic

text: capacity

text: matrix

text: is

text: a

text: numeral

text: and

text: can

text: be

text: computed

text: numerically.

text: Convergence

text: does

text: not

text: provide

text: information

text: about

text: the

text: stress

text: and

text: strain

text: ﬁelds

text: in

text: the

text: plate,

text: however,

text: using

text: a

text: technique

text: of

text: local

text: estimates

text: in

text: it

text: is

text: possible

text: to

text: verify

text: that,

text: under

text: certain

text: restrictions

text: on

text: the

text: volume

text: forces

text: this

text: convergence

text: becomes

text: pointwise

text: outside

text: a

text: neighborhood

text: of

text: θ

text: We

text: mention

text: that,

text: as

text: discovered

text: in

text: see

text: also

text: pointwise

text: convergence

text: h

text: of

text: stresses

text: and

text: strains

text: is

text: always

text: broken

text: near

text: the

text: clamped

text: edge

text: υ

text: of

text: the

text: plate

text: with

text: or

text: without

text: h

text: small

text: perturbation

text: at

text: θ

text: h

text: Both,

text: the

text: asymptotic

text: procedure

text: and

text: the

text: models,

text: can

text: be

text: easily

text: adapted

text: to

text: the

text: plate

text: with

text: several

text: small

text: support

text: areas

text: θJ

text: sparsely

text: distributed

text: on

text: one

text: or

text: two

text: bases

text: Σ

text: h

text: h

text: A

text: h

text: In

text: view

text: of

text: block-diagonal

text: structure

text: of

text: the

text: matrix

text: the

text: Dirichlet-Sobolev

text: problem

text: naturally

text: decouples

text: into

text: independent

text: problems

text: for

text: the

text: vector

text: w

text: (w

text: w

text: of

text: longitudinal

text: displacements

text: and

text: the

text: deﬂection

text: w

text: Since

text: the

text: elasticity

text: problem

text: for

text: the

text: inﬁnite

text: R

text: layer

text: Λ

text: clamped

text: over

text: the

text: only

text: area

text: θ

text: loses

text: the

text: symmetry

text: with

text: R

text: respect

text: to

text: the

text: plane

text: ξ

text: ξ

text: ζ

text: the

text: elastic

text: capacity

text: matrix

text: does

text: not

text: get

text: in

text: general

text: a

text: block-diagonal

text: structure

text: and

text: thus

text: the

text: relationship

text: imposed

text: in

text: on

text: the

text: regular

text: and

text: similar

text: components

text: of

text: the

text: solution

text: w

text: (w

text: w

text: of

text: the

text: model

text: equation

text: couples

text: the

text: vector

text: w

text: and

text: the

text: scalar

text: w

text: at

text: the

text: level

text: O(

text: ln

text: h

text: References

text: Berezin

text: F.A.,

text: Faddeev

text: L.D.,

text: Remark

text: on

text: the

text: Schr¨odinger

text: equation

text: with

text: singular

text: potential.

text: Dokl.

text: Akad.

text: Nauk

text: SSSR,

text: Birman

text: M.

text: S.,

text: Solomyak

text: M.Z.,

text: Spectral

text: Theory

text: of

text: Self-Adjoint

text: Operators

text: in

text: Hilbert

text: Space.

text: Reidel

text: Publishing

text: Company,

text: Dordrecht,

text: Bunoiu

text: R.,

text: Cardone

text: G.,

text: Nazarov

text: S.A.,

text: Scalar

text: boundary

text: value

text: problems

text: on

text: junctions

text: of

text: thin

text: rods

text: and

text: plates.

text: I.

text: Asymptotic

text: analysis

text: and

text: error

text: estimates,

text: ESAIM:

text: Math.

text: Model.

text: Num.

text: Anal.,

text: ##LTLine##

text: ##LTLine##


text: (cid:90) 1/2 ∈ f0 (y, ζ) dζ = 0, f1 (y) = f1 (y) = 0, y ω. (2.2) − 3 1 2 1/2 (cid:101) Now we assume f0 and f1 smooth and postpone a detailed description of properties of f0, f1 and f to Section 3.2. We emphasize that, owing to linearity of the problem, any reasonable right-hand side can be represented as in (2.1), (2.2). After appropriate rescaling our choice of − the factors h 1/2 and h1/2 in (2.1) as well as the orthogonality condition in (2.2) ensures that the potential energy stored by the plate Ω under the volume force (2.1) gets order 1 = h0, see h Section 4.4. As shown in [22], [23, Ch.4], the asymptotic ansatz − − u (h, x) = h 3/2U0 (y) + h 1/2U1 (y, ζ) + h1/2U2 (y, ζ) + ... (2.3) of the solution to problem (1.4)-(1.6) is perfectly adjusted with decomposition (2.1). The (cid:55)→ ∇ ± ∇ coordinate change x (y, ζ) splits the diﬀerential operators L ( ) and N ( ) in (1.4) and (1.5), respectively, as follows: ∇ −∇ (cid:62) ∇ − − ∇ ∇ L ( ) := D ( ) AD ( ) = h 2L0 (∂ ) + h 1L1 ( , ∂ ) + h0L2 ( ) , (2.4) ζ y ζ y ± ∇ ± (cid:62) ∇ − ± ± ∇ N ( ) := D (0, 0, 1) AD ( ) = h 1N0 (∂ ) + h0N1 ( ) , ζ y where − (cid:62) − (cid:62) − (cid:62) − (cid:62) L0 = D AD , L1 = D AD D AD , L2 = D AD , ζ ζ ζ y y ζ y y ± ± (cid:62) ± ± (cid:62) N0 = D AD , N1 = D AD 3 ζ 3 y ∇ D = D (0, 0, ∂ ) , D = D ( , 0) , D = (0, 0, 1) , (2.5) ζ ζ y y 3 ∇ ∂ = ∂/∂ζ, = (∂/∂y , ∂/∂y ) . ζ y 1 2 We now insert formulas (2.4) and (2.3), (2.1) into (1.4) and (1.5) and collect coeﬃcients of − − hp 2 and hp 1, respectively. Equalizing their sums yields a recursive sequence of the Neumann − (cid:51) ∈ problems on the interval ( 1/2, 1/2) ζ with the parameter y (cid:0)ω. For(cid:1)p = 0, 1, 2, we have − − − − ∈ − L0Up = F p := L1Up 1 L2Up 2 for ζ 1, 1 , (2.6) 2 2 ± ± − ± − ± N0 Up = Gp := N1 Up 1 at ζ = 1, 2 − − ± ± ∓ (cid:62) where U 2 = U 1 = 0. Since F 0 = 0, G0 = 0 and F 1 = 0, G1 = D AD U0, we readily (cid:18) (cid:19)3 y take (cid:88) 2 − ∂w U0 (y) = w (y) e , U1 (y) = e w (y) ζ 3 (y) (2.7) 3 3 i i ∂y i i=1 5 ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: (y,

text: ζ)

text: dζ

text: (y)

text: (y)

text: y

text: ω.

text: Now

text: we

text: assume

text: and

text: smooth

text: and

text: postpone

text: a

text: detailed

text: description

text: of

text: properties

text: of

text: and

text: f

text: to

text: Section

text: We

text: emphasize

text: that,

text: owing

text: to

text: linearity

text: of

text: the

text: problem,

text: any

text: reasonable

text: right-hand

text: side

text: can

text: be

text: represented

text: as

text: in

text: After

text: appropriate

text: rescaling

text: our

text: choice

text: of

text: the

text: factors

text: h

text: and

text: in

text: as

text: well

text: as

text: the

text: orthogonality

text: condition

text: in

text: ensures

text: that

text: the

text: potential

text: energy

text: stored

text: by

text: the

text: plate

text: Ω

text: under

text: the

text: volume

text: force

text: gets

text: order

text: see

text: h

text: Section

text: As

text: shown

text: in

text: the

text: asymptotic

text: ansatz

text: u

text: (h,

text: x)

text: h

text: (y)

text: h

text: (y,

text: ζ)

text: (y,

text: ζ)

text: of

text: the

text: solution

text: to

text: problem

text: is

text: perfectly

text: adjusted

text: with

text: decomposition

text: The

text: coordinate

text: change

text: x

text: (y,

text: ζ)

text: splits

text: the

text: diﬀerential

text: operators

text: L

text: and

text: N

text: in

text: and

text: respectively,

text: as

text: follows:

text: L

text: D

text: AD

text: h

text: h

text: ζ

text: y

text: ζ

text: y

text: N

text: D

text: AD

text: h

text: ζ

text: y

text: where

text: D

text: AD

text: D

text: AD

text: D

text: AD

text: D

text: AD

text: ζ

text: ζ

text: ζ

text: y

text: y

text: ζ

text: y

text: y

text: D

text: AD

text: D

text: AD

text: ζ

text: y

text: D

text: D

text: D

text: D

text: D

text: ζ

text: ζ

text: y

text: y

text: ∂/∂ζ,

text: (∂/∂y

text: ∂/∂y

text: ζ

text: y

text: We

text: now

text: insert

text: formulas

text: and

text: into

text: and

text: and

text: collect

text: coeﬃcients

text: of

text: hp

text: and

text: hp

text: respectively.

text: Equalizing

text: their

text: sums

text: yields

text: a

text: recursive

text: sequence

text: of

text: the

text: Neumann

text: problems

text: on

text: the

text: interval

text: ζ

text: with

text: the

text: parameter

text: y

text: we

text: have

text: F

text: p

text: for

text: ζ

text: Up

text: Gp

text: Up

text: at

text: ζ

text: where

text: U

text: U

text: Since

text: F

text: and

text: F

text: D

text: AD

text: we

text: readily

text: y

text: take

text: ∂w

text: (y)

text: w

text: (y)

text: e

text: (y)

text: e

text: w

text: (y)

text: ζ

text: (y)

text: i

text: i

text: ∂y

text: i

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: × X inherited from (1.9), (2.5), and ﬁnally recalled problem (2.12) for the 3 6-matrix . Let us demonstrate that the third line of system (2.17) is equivalent to the equality I4 (y) = 0, (2.21) 3 (cid:0) (cid:1) that is the third compatibility condition (2.15) in problem (2.13) with the right-hand sides − − (cid:62) (cid:62) F 3 = L1U3 L0U2 + f1 = D AD U3 + D A D U3 + D U2 + f1, ζ y y ζ y 3 ± ∓ ± ∓ (cid:62) G4 = N1 U3 = D AD U3. 3 y We have(cid:90) (cid:0) (cid:1) 1/2 (cid:62) (cid:62) I34 (y) = (cid:88)− e3(cid:90)Dy A DζU3 + D(cid:0)yU2 dζ + f31 (cid:1) (2.22) 1/2 2 ∂ 1/2 (cid:32) (cid:62) (cid:33) = ∂(cid:88)y − (Dζζe(cid:90)i) A DζU3(cid:0)+ DyU2 dζ + f(cid:1)31 (cid:16) (cid:0) (cid:1)(cid:17) i 1/2 i=1 2 ∂ (cid:62) − 1/2 (cid:62) (cid:62) | = f31 + (cid:88) ∂y ei (cid:90) − (cid:16) ζDζ (cid:0)A DζU3 + DyU(cid:1)2 dζ (cid:17)+ ζD3 A DζU3 + DyU2 1ζ/=2−1/2 i 1/2 i=1 2 ∂ (cid:62) 1/2 (cid:62) = f31 +(cid:88) ∂y ei − (cid:90) ζ Dy A DζU2 + DyU1 + f0 dζ i 1/2 i=1 2 ∂ (cid:62) (cid:62) 1/2 X Y D ∇ = g + e D ζA (D + ) dζ ( ) w 3 ∂y i y − ζ y i 1/2 i=1 (cid:90) where (cid:88) 2 1/2 ∂f0 g (y) = f1 (y) + ζ i (y, ζ) dζ. (2.23) 3 3 − ∂y 1/2 i i=1 Let us clarify calculation (2.22). First, we used identity (2.20) and integrate by parts in the − interval ( 1/2, 1/2) . Then we took into account problem (2.6) with p = 3 and its right-hand sides (2.14). Finally, formula (2.16) was applied. In view of (1.9) and (2.10) o(cid:88)ne observes that 2 ∂ (cid:62) (cid:62) (cid:62)D ∇ Y e D ζ = e ( ) (ζ) ∂y i y 3 y i i=1 and, hence, equality (2.21) indeed implies the third line of system (2.17) due to deﬁnition (2.18). 2.2 The plate equations Owing to the Dirichlet condition (1.7) on the lateral side υ of the plate Ω , we supply h h system (2.17) with the boundary conditions 8 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: X

text: inherited

text: from

text: and

text: ﬁnally

text: recalled

text: problem

text: for

text: the

text: Let

text: us

text: demonstrate

text: that

text: the

text: third

text: line

text: of

text: system

text: is

text: equivalent

text: to

text: the

text: equality

text: (y)

text: that

text: is

text: the

text: third

text: compatibility

text: condition

text: in

text: problem

text: with

text: the

text: right-hand

text: sides

text: F

text: D

text: AD

text: D

text: A

text: D

text: D

text: ζ

text: y

text: y

text: ζ

text: y

text: D

text: AD

text: y

text: We

text: (y)

text: A

text: dζ

text: A

text: dζ

text: i

text: ∂y

text: ei

text: ζDζ

text: dζ

text: A

text: i

text: ∂y

text: ei

text: ζ

text: Dy

text: A

text: dζ

text: i

text: X

text: Y

text: D

text: g

text: e

text: D

text: ζA

text: (D

text: dζ

text: w

text: ∂y

text: i

text: y

text: ζ

text: y

text: i

text: where

text: g

text: (y)

text: (y)

text: ζ

text: i

text: (y,

text: ζ)

text: dζ.

text: ∂y

text: i

text: Let

text: us

text: clarify

text: calculation

text: First,

text: we

text: used

text: identity

text: and

text: integrate

text: by

text: parts

text: in

text: the

text: interval

text: Then

text: we

text: took

text: into

text: account

text: problem

text: with

text: p

text: and

text: its

text: right-hand

text: sides

text: Finally,

text: formula

text: was

text: applied.

text: In

text: view

text: of

text: and

text: observes

text: that

text: Y

text: e

text: D

text: ζ

text: e

text: (ζ)

text: ∂y

text: i

text: y

text: y

text: i

text: and,

text: hence,

text: equality

text: indeed

text: implies

text: the

text: third

text: line

text: of

text: system

text: due

text: to

text: deﬁnition

text: The

text: plate

text: equations

text: Owing

text: to

text: the

text: Dirichlet

text: condition

text: on

text: the

text: lateral

text: side

text: υ

text: of

text: the

text: plate

text: Ω

text: we

text: supply

text: h

text: h

text: system

text: with

text: the

text: boundary

text: conditions

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##