text: Vincent Wens Physical Review E 91, 012823 (2015) Subtracting this from the uncorrected reconstruction Ψ(r, t) and using the deﬁni(cid:20)tions (18) (cid:21)and (17) for the corrected ones then yields Φ⊥(r, t) = Φgcs(r, t) − Re ΦΨg(crs(r,,t)t) Ψ(r0, t) . (D5) 0 This is equivalent to the sought Eq. (24). Appendix E: Amplitude correlation for a model of FIG. 3. Linear approximation of squared amplitude. The coherent Gaussian signals Rayleigh distribution of A(t) with maximum reached at value α = 1 is shown together with the function A2. The Taylor ≈ − In this appendix, we consider the model of coherent expansion A2 2αA α2 around A = α is seen to be a good ± Gaussian signals introduced in Ref. [23] and derive an- approximation in the α σ interval (green shaded region), A alytically an expression for the true and orthogonalized which contains about 80% of samples. Over a larger interval, amplitude correlations. linear regression still yields a reasonable approximation. Model deﬁnition The model assumes that the spatial-leakage-free recon- Approximation scheme struction Φgcs(r, t) is linearly related to the seed signal Our basic observation is that all amplitudes in the prob- Ψ(r , t). Explicitly, − 0 lem have ﬁnite variance, e.g., σ2 = (2 π/2)α2 for A the Reyleigh distribution. Therefore, they are eﬀectively supported on a region where the amplitude squared can Ψ(r , t) = A (t) exp iθ (t) , (E1) 0 0 0 be reasonably approximated by a linear function, as il- c√exp iψ Φgcs(r, t) = A1(t) exp iθ1(t) + − Ψ(r0, t) . (E2) lustrated in Fig. 3. Now an elementary property of the 1 c2 correlation coeﬃcient (E3) is to be invariant under aﬃne transformations, i.e., The linear coupling is contr≤olled ≤by two parameters: (cid:48) (cid:48) corr[A , A ] = corr[aA + b, a A + b ] the coherence parameter 0 c 1 quantiﬁes the I 0 I 0 strength of this coupling, whereas ψ denotes the mean (cid:48) (cid:48) whatever the coeﬃcients a, b, a , b . Using the choice of phase lag between Ψ(r0, t) and Φgcs(r, t). In the absence these coeﬃcients for optimal linearizations A2 ≈ aA + b of coupling (c = 0), the two ﬁelds are assumed to be un- ≈ (cid:48) (cid:48) I I and A2 a A + b , we obtain the approximate formula correlated white noises with identical (complex-valued) 0 0 ≈ Gaussian distribution. This means that A0(t) and A1(t) ρI corr[A2I, A20] . (E5) are distributed according to a Rayleigh distribution (i.e., their fraction of time spent between values A and A+dA − − Solution is d exp( A2/2α2) for some α > 0, see Fig. 3) and that θ (t) and θ (t) are uniformly distributed on the circle, 0 1 The right-hand side of Eq. (E5) can be computed ana- all four signals being independent of each other. lytically in terms of c and ψ, as we detail below. The ⊥ Our goal is to evaluate the amplitude correlations resulting expressions for I = gcs and I = are (cid:104) (cid:105) − (cid:104) (cid:105)(cid:104) (cid:105) A A A A ρ = corr[A , A ] = I 0 I 0 (E3) ≈ I I 0 σAI σA0 ρgcs c(cid:112)2 , (E6) ⊥ ≈ c˜2 between ΦI(r, t) (I = g(cid:112)cs or ) and Ψ(r0, t). In this ρ⊥ , (E7) deﬁnition, σ denotes the standard deviation c˜4 + 2c˜2 + 1/2 A (cid:112) (cid:104) (cid:105) − (cid:104) (cid:105) σ = A2 A 2 . (E4) where we deﬁned the eﬀective coupling constant A − Computing these nonlinear correlations exactly as func- c˜ = c sin ψ/ 1 c2 . (E8) tions of the model parameters c and ψ is diﬃcult but Figure 4 shows that these equations based on an approx- illustrates the nontrivial eﬀect of orthogonalization on imation agree with numerical simulations. amplitude correlation. This computation was performed numerically in Ref. [23]. However, analytical derivations Eliminating c for ρgcs and plugging into Eq. (E7) illus- trates the nontrivial phase-dependent relation between are possible using an appropriate approximation. orthogonalized and true amplitude correlations. Depend- ing on the values of c and ψ, we observe the underesti- mation and overestimation eﬀects described in Sec. . For 16 ##LTFigure## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: Vincent

text: Wens

text: Physical

text: Review

text: E

text: Subtracting

text: this

text: from

text: the

text: uncorrected

text: reconstruction

text: Ψ(r,

text: t)

text: and

text: using

text: the

text: for

text: the

text: corrected

text: ones

text: then

text: yields

text: Φ⊥(r,

text: t)

text: Φgcs(r,

text: t)

text: Re

text: ΦΨg(crs(r,,t)t)

text: t)

text: This

text: is

text: equivalent

text: to

text: the

text: sought

text: Eq.

text: Appendix

label: section

text: E:

text: Amplitude

text: correlation

text: for

text: a

text: model

text: of

text: FIG.

text: Linear

text: approximation

text: of

text: squared

text: amplitude.

text: The

text: coherent

text: Gaussian

text: signals

text: Rayleigh

text: distribution

text: of

text: A(t)

text: with

text: maximum

text: reached

text: at

text: value

text: α

text: is

text: shown

text: together

text: with

text: the

text: function

text: The

text: Taylor

text: In

text: this

text: appendix,

text: we

text: consider

text: the

text: model

text: of

text: coherent

text: expansion

text: α2

text: around

text: A

text: α

text: is

text: seen

text: to

text: be

text: a

text: good

text: Gaussian

text: signals

text: introduced

text: in

text: Ref.

text: and

text: derive

text: an-

text: approximation

text: in

text: the

text: α

text: σ

text: interval

text: (green

text: shaded

text: region),

text: A

text: alytically

text: an

text: expression

text: for

text: the

text: true

text: and

text: orthogonalized

text: which

text: contains

text: about

text: of

text: samples.

text: Over

text: a

text: larger

text: interval,

text: amplitude

text: correlations.

text: linear

text: regression

text: still

text: yields

text: a

text: reasonable

text: approximation.

text: Model

text: deﬁnition

text: The

text: model

text: assumes

text: that

text: the

text: spatial-leakage-free

text: recon-

text: Approximation

text: scheme

text: struction

text: Φgcs(r,

text: t)

text: is

text: linearly

text: related

text: to

text: the

text: seed

text: signal

text: Our

text: basic

text: observation

text: is

text: that

text: all

text: amplitudes

text: in

text: the

text: prob-

text: Ψ(r

text: t).

text: Explicitly,

text: lem

text: have

text: ﬁnite

text: variance,

text: e.g.,

text: σ2

text: for

text: A

text: the

text: Reyleigh

text: distribution.

text: Therefore,

text: they

text: are

text: eﬀectively

text: supported

text: on

text: a

text: region

text: where

text: the

text: amplitude

text: squared

text: can

text: Ψ(r

text: t)

text: A

text: (t)

text: exp

text: iθ

text: (t)

text: be

text: reasonably

text: approximated

text: by

text: a

text: linear

text: function,

text: as

text: il-

text: c√exp

text: iψ

text: Φgcs(r,

text: t)

text: exp

text: t)

text: lustrated

text: in

text: Fig.

text: Now

text: an

text: elementary

text: property

text: of

text: the

text: correlation

text: coeﬃcient

text: is

text: to

text: be

text: invariant

text: under

text: aﬃne

text: transformations,

text: i.e.,

text: The

text: linear

text: coupling

text: is

text: contr≤olled

text: ≤by

text: two

text: parameters:

text: corr[A

text: A

text: corr[aA

text: b,

text: a

text: A

text: b

text: the

text: coherence

text: parameter

text: c

text: quantiﬁes

text: the

text: I

text: I

text: strength

text: of

text: this

text: coupling,

text: whereas

text: ψ

text: denotes

text: the

text: mean

text: whatever

text: the

text: coeﬃcients

text: a,

text: b,

text: a

text: b

text: Using

text: the

text: choice

text: of

text: phase

text: lag

text: between

text: t)

text: and

text: Φgcs(r,

text: t).

text: In

text: the

text: absence

text: these

text: coeﬃcients

text: for

text: optimal

text: linearizations

text: aA

text: b

text: of

text: coupling

text: (c

text: the

text: two

text: ﬁelds

text: are

text: assumed

text: to

text: be

text: un-

text: I

text: I

text: and

text: a

text: A

text: b

text: we

text: obtain

text: the

text: approximate

text: formula

text: correlated

text: white

text: noises

text: with

text: identical

text: (complex-valued)

text: Gaussian

text: distribution.

text: This

text: means

text: that

text: and

text: ρI

text: are

text: distributed

text: according

text: to

text: a

text: Rayleigh

text: distribution

text: (i.e.,

text: their

text: fraction

text: of

text: time

text: spent

text: between

text: values

text: A

text: and

text: A+dA

text: Solution

text: is

text: d

text: exp(

text: for

text: some

text: α

text: see

text: Fig.

text: and

text: that

text: θ

text: (t)

text: and

text: θ

text: (t)

text: are

text: uniformly

text: distributed

text: on

text: the

text: circle,

text: The

text: right-hand

text: side

text: of

text: Eq.

text: can

text: be

text: computed

text: ana-

text: all

text: four

text: signals

text: being

text: independent

text: of

text: each

text: other.

text: lytically

text: in

text: terms

text: of

text: c

text: and

text: ψ,

text: as

text: we

text: detail

text: below.

text: The

text: Our

text: goal

text: is

text: to

text: evaluate

text: the

text: amplitude

text: correlations

text: resulting

text: expressions

text: for

text: I

text: gcs

text: and

text: I

text: are

text: A

text: A

text: A

text: A

text: ρ

text: corr[A

text: A

text: I

text: I

text: I

text: I

text: σAI

text: ρgcs

text: between

text: ΦI(r,

text: t)

text: (I

text: or

text: and

text: t).

text: In

text: this

text: ρ⊥

text: deﬁnition,

text: σ

text: denotes

text: the

text: standard

text: deviation

text: A

text: σ

text: A

text: where

text: we

text: deﬁned

text: the

text: eﬀective

text: coupling

text: constant

text: A

text: Computing

text: these

text: nonlinear

text: correlations

text: exactly

text: as

text: func-

text: c˜

text: c

text: sin

text: ψ/

text: tions

text: of

text: the

text: model

text: parameters

text: c

text: and

text: ψ

text: is

text: diﬃcult

text: but

text: Figure

text: shows

text: that

text: these

text: equations

text: based

text: on

text: an

text: approx-

text: illustrates

text: the

text: nontrivial

text: eﬀect

text: of

text: orthogonalization

text: on

text: imation

text: agree

text: with

text: numerical

text: simulations.

text: amplitude

text: correlation.

text: This

text: computation

text: was

text: performed

text: numerically

text: in

text: Ref.

text: However,

text: analytical

text: derivations

text: Eliminating

text: c

text: for

text: ρgcs

text: and

text: plugging

text: into

text: Eq.

text: illus-

text: trates

text: the

text: nontrivial

text: phase-dependent

text: relation

text: between

text: are

text: possible

text: using

text: an

text: appropriate

text: approximation.

text: orthogonalized

text: and

text: true

text: amplitude

text: correlations.

text: Depend-

text: ing

text: on

text: the

text: values

text: of

text: c

text: and

text: ψ,

text: we

text: observe

text: the

text: underesti-

text: mation

text: and

text: overestimation

text: eﬀects

text: described

text: in

text: Sec.

text: For

text: ##LTFigure##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: Investigating complex networks with inverse models Physical Review E 91, 012823 (2015) [27] C. J. Stam, G. Nolte, and A. Daﬀertshofer, Hum. Brain Mapp., N28a,ga1r1a7j8an(2, 0ib0i7d).., 49, 641 (2010). [28] A. Hillebrand, G. R. Barnes, J. L. Bosboom, H. W. Berendse[3, 6a] nPdoiCn.t-Js.prSetaadmf,uNncetuiroonIsmaargeeo,f5te9n, u3s9e0d9to(2a0s1s2es)s. the localization biases and spatial resolution of inverse models. For example, [29] For a proof of concept on simulated and experimental neuromagsneeetiKc.dSaetkai,hsaerea,VM. .WSeanhsa,nBi,. aMnadrtSy.,SA. .NMagaarrya,jMan., BNoeuurr-oImage, 25, 1056 (2005). guignon, M. Op de beeck, S. Goldman, P. Van Bogaert, P. P[e3ig7n] eGu.x,BaacnkdusXa.nDdeFT.iG`egielb, esrutb, mPihtitle.dT.rans. R. Soc. Lond. A, 266, 123 (1970). [30] Spatial leakage diﬀers from the notion of spectral leakage, whi[c3h8]orAig.iKna.tLesiuf,roAm. Mﬁn.itDea-dleim, eannsdioJn.alWtr.uBneclalitvioenaus,oHf tuhme.spBarcaein Mapp., 16, 47 (2002). of ﬁelds Ψ(r, t); see J. Trampert and R. Snieder, Science, 27[319,]1S25. 7H.(1S9t9ro6g).atz, Nonlinear Dynamics and Chaos with Applications to Physics, Biology, Chemistry, and Engineering (Perseus [31] I. Daubechies, M. Defrise, and C. De Mol, Comm. Pure Appl. MBatoho.k,s5G7,ro1u4p13, N(2e0w04Y)o.rk, 1994). [32] D. Malioutov, M. Cetin, and A. S. Willsky, IEEE Trans. Sig[.40P]roAc..,P5i3ko, v3s0k1y0, (M20.0R5)o.senblum, and J. Kurths, Synchronization: A Universal Concept in Nonlinear Sciences (Cambridge [33] W. Ou, M. S. Ha¨ma¨la¨inen, and P. Golland, NeuroImage, 44, U93n2iv(e2r0si0t9y);PrAes.s,GCraammbforridt,geD,.USKtr,o2h0m03e)ie.r, J. Haueisen, M. Ha¨ma¨la¨inen, and M. Kowalski, ibid., 70, 410 (2013). [41] More precisely, the original deﬁnition of the phase lag index requires replacing θgcs(t) by the phase θ(t) of the uncorrected [34] B. D. Van Veen and K. M. Buckley, IEEE ASSP Mag., 5, 4 (1988r)e.construction Ψ(r, t) in the right-hand side of Eq. (29). This replacement can indeed be applied, as was noted below the [35] D. Wipf and S. Nagarajan, NeuroImage, 44, 947 (2009); D. P. Wbaispifc, rJe.laPt.ioOnw(e2n4,).H. T. Attias, K. Sekihara, and S. S. 19

text: Investigating

label: paragraph

text: complex

text: networks

text: with

text: inverse

text: models

text: Physical

text: Review

text: E

text: C.

text: J.

text: Stam,

text: G.

text: Nolte,

text: and

text: A.

text: Daﬀertshofer,

text: Hum.

text: Brain

text: Mapp.,

text: A.

text: Hillebrand,

text: G.

text: R.

text: Barnes,

text: J.

text: L.

text: Bosboom,

text: H.

text: W.

text: the

text: localization

text: biases

text: and

text: spatial

text: resolution

text: of

text: inverse

text: models.

text: For

text: example,

text: For

text: a

text: proof

text: of

text: concept

text: on

text: simulated

text: and

text: experimental

text: neuromagsneeetiKc.dSaetkai,hsaerea,VM.

text: .WSeanhsa,nBi,.

text: aMnadrtSy.,SA.

text: .NMagaarrya,jMan.,

text: BNoeuurr-oImage,

text: guignon,

text: M.

text: Op

text: de

text: beeck,

text: S.

text: Goldman,

text: P.

text: Van

text: Bogaert,

text: P.

text: eGu.x,BaacnkdusXa.nDdeFT.iG`egielb,

text: esrutb,

text: mPihtitle.dT.rans.

text: R.

text: Soc.

text: Lond.

text: A,

text: Spatial

text: leakage

text: diﬀers

text: from

text: the

text: notion

text: of

text: spectral

text: leakage,

text: Mﬁn.itDea-dleim,

text: eannsdioJn.alWtr.uBneclalitvioenaus,oHf

text: tuhme.spBarcaein

text: Mapp.,

text: of

text: ﬁelds

text: Ψ(r,

text: t);

text: see

text: J.

text: Trampert

text: and

text: R.

text: Snieder,

text: Science,

text: Nonlinear

text: Dynamics

text: and

text: Chaos

text: with

text: Applications

text: to

text: Physics,

text: Biology,

text: Chemistry,

text: and

text: Engineering

text: (Perseus

text: I.

text: Daubechies,

text: M.

text: Defrise,

text: and

text: C.

text: De

text: Mol,

text: Comm.

text: Pure

text: Appl.

text: D.

text: Malioutov,

text: M.

text: Cetin,

text: and

text: A.

text: S.

text: Willsky,

text: IEEE

text: Trans.

text: and

text: J.

text: Kurths,

text: Synchronization:

text: A

text: Universal

text: Concept

text: in

text: Nonlinear

text: Sciences

text: (Cambridge

text: W.

text: Ou,

text: M.

text: S.

text: Ha¨ma¨la¨inen,

text: and

text: P.

text: Golland,

text: NeuroImage,

text: J.

text: Haueisen,

text: M.

text: Ha¨ma¨la¨inen,

text: and

text: M.

text: Kowalski,

text: ibid.,

text: More

text: precisely,

text: the

text: original

text: deﬁnition

text: of

text: the

text: phase

text: lag

text: index

text: requires

text: replacing

text: θgcs(t)

text: by

text: the

text: phase

text: θ(t)

text: of

text: the

text: uncorrected

text: B.

text: D.

text: Van

text: Veen

text: and

text: K.

text: M.

text: Buckley,

text: IEEE

text: ASSP

text: Mag.,

text: Ψ(r,

text: t)

text: in

text: the

text: right-hand

text: side

text: of

text: Eq.

text: This

text: replacement

text: can

text: indeed

text: be

text: applied,

text: as

text: was

text: noted

text: below

text: the

text: D.

text: Wipf

text: and

text: S.

text: Nagarajan,

text: NeuroImage,

text: D.

text: P.

text: Wbaispifc,

text: T.

text: Attias,

text: K.

text: Sekihara,

text: and

text: S.

text: S.


text: Vincent Wens Physical Review E 91, 012823 (2015) B. Geometric correction scheme versus It is state independent and determined by the direct and orthogonalization inverse models only, contrary to the regression coeﬃcient (20). Actually, this is the sole remaining diﬀerence be- In the remaining sections, we shall compare the geo- tween the two correction approaches. metric correction scheme (Sec. ) and the orthogonaliza- Quantitative comparison tion method. We start with a qualitative general discus- sion and then turn to more quantitative aspects. We now compare the coupling estimates k(r, r , t) and 0 Qualitative comparison k⊥(r, r , t) that are eliminated by the geometric cor- 0 rection scheme and orthogona(cid:2)lization, respective(cid:3)ly. As Some features are common to both techniques, e.g., the shown in Appendix , they are related via linearity hypothesis (Secs. and ) or the nonelimination of spatial leakage eﬀects other than those emanating from k⊥(r, r0, t) = k(r, r0, t) + Re Φgcs(r, t)/Ψ(r0, t) . (23) r (Sec. ). But other hypotheses induce diﬀerences. 0 The main conceptual advantage of the geometric cor- This embodies the general observation that the linear rection scheme is that it relies on a structural descrip- regression includes both spatial leakage eﬀects and true tion of spatial leakage adapted to the inverse operator, connectivity. More precisely, the regression coeﬃcient whereas orthogonalization uses statistical features of re- (20) appears to be the sum of the spatial leakage model constructed signals without explicit reference to the in- coupling and of the linear instantaneous connectivity es- verse model. This implies that the second and third hy- timate after geometric correction. In the limit where the potheses used by orthogonalization (Sec. ) are not nec- model is exact, this second term represents a true state essary for the geometric correction scheme. Indeed, the interaction (see property (ii) of Sec. ) that is eliminated latter automatically conforms to the temporal character- by orthogonalization (overcorrection bias). istics of spatial leakage (and more precisely of the re- It will be useful for our subsequent analyses to promote solving operator, see Secs. and ), which may or may this relation at the(cid:2)level of the correcte(cid:3)d ﬁelds. Plugging not have instantaneous eﬀects depending on the inverse Eq. (23) into the linear regression (18–20) yields model. Furthermore, it does not confound true connec- tivity with spatial leakage eﬀects and so does not ex- Φ⊥(r, t) = i Im Φgcs(r, t)/Ψ(r0, t) Ψ(r0, t) , (24) hibit the overcorrection bias of orthogonalization. For see Appendix for details. Geometrically, this means that example, this bias implies that the reconstruction may the orthogonalized ﬁeld Φ⊥(r, t) equals to the projection be nontrivially aﬀected by orthogonalization even in the of the corrected ﬁeld Φgcs(r, t) onto the direction per- absence of spatial leakage, whereas this does not happen pendicular to Ψ(r , t). A similar formula was derived in 0 with the geometric correction scheme (see property (i) of Ref. [23] with the uncorrected reconstruction Ψ(r, t) in Sec. ). place of the corrected one Φgcs(r, t). This interchange- On the other hand, some hypotheses of the geometric ability is indicative that the linear instantaneous spatial correction are not required for orthogonalization. First, leakage eﬀect has been completely eliminated by orthog- measurement noise was neglected in our derivation of the onalization (notwithstanding its overcorrection eﬀect). spatial leakage model (Sec. ), whereas the regression au- tomatically takes care of noise contributions. This rep- Polar coordinates resents an advantage of orthogonalization. Second, the In the next two sections, we shall focus on two speciﬁc condition that spatial leakage eﬀects to r are negligi- 0 connectivity indices classically applied to oscillatory or ble (Sec. ) was not explicitly assumed in orthogonaliza- narrow-band time series: phase coherence and amplitude tion. It is noteworthy, however, that this hypothesis was correlation. Their deﬁnition and analysis will be sim- instrumental to characterize spatial leakage exactly and pliﬁed by using ﬁeld coordinates emphasizing phase and avoid any overcorrection bias in the geometric correction amplitude ﬂuctuations, scheme. Ψ(r , t) = A (t) exp iθ (t) , Framework for quantitative analysis 0 0 0 Φgcs(r, t) = Agcs(t) exp iθgcs(t) , (25) We now turn to some quantitative considerations, our Φ⊥(r, t) = A⊥(t) exp iθ⊥(t) . goal being to illustrate the overcorrection eﬀect of or- thogonalization (compared to the geometric approach). In these notations, the relation (24) becomes To single out this overcorrection bias, we shall work from − now on in a restricted framework where spatial leakage A⊥(t) eiθ⊥(t) = i Agcs(t) sin(θgcs(t) θ0(t)) eiθ0(t) , eﬀects are both linear and instantaneous, so our model which directly implies (15) assumes the form Λ(r, t) = k(r, r0, t) Ψ(r0, t) . (22) − π − θ⊥(t) θ0(t) = 2 sign[sin(θgcs(t) θ0(t))] , (26) An explicit example is given in Appendix . The coupling | − | constant k(r, r , t) ∈ R encodes the spatial leakage eﬀect. A⊥(t) = Agcs(t) sin(θgcs(t) θ0(t)) . (27) 0 10 ##LTLine##

text: Vincent

text: Wens

text: Physical

text: Review

text: E

text: B.

text: Geometric

text: correction

text: scheme

text: versus

text: It

text: is

text: state

text: independent

text: and

text: determined

text: by

text: the

text: direct

text: and

text: orthogonalization

text: inverse

text: models

text: only,

text: contrary

text: to

text: the

text: regression

text: coeﬃcient

text: Actually,

text: this

text: is

text: the

text: sole

text: remaining

text: diﬀerence

text: be-

text: In

text: the

text: remaining

text: sections,

text: we

text: shall

text: compare

text: the

text: geo-

text: tween

text: the

text: two

text: correction

text: approaches.

text: metric

text: correction

text: scheme

text: (Sec.

text: and

text: the

text: orthogonaliza-

text: Quantitative

text: comparison

text: tion

text: method.

text: We

text: start

text: with

text: a

text: qualitative

text: general

text: discus-

text: sion

text: and

text: then

text: turn

text: to

text: more

text: quantitative

text: aspects.

text: We

text: now

text: compare

text: the

text: coupling

text: estimates

text: k(r,

text: r

text: t)

text: and

text: Qualitative

text: comparison

text: k⊥(r,

text: r

text: t)

text: that

text: are

text: eliminated

text: by

text: the

text: geometric

text: cor-

text: rection

text: scheme

text: and

text: As

text: Some

text: features

text: are

text: common

text: to

text: both

text: techniques,

text: e.g.,

text: the

text: shown

text: in

text: Appendix

text: they

text: are

text: related

text: via

text: linearity

text: hypothesis

text: (Secs.

text: and

text: or

text: the

text: nonelimination

text: of

text: spatial

text: leakage

text: eﬀects

text: other

text: than

text: those

text: emanating

text: from

text: k⊥(r,

text: t)

text: k(r,

text: t)

text: Re

text: Φgcs(r,

text: t)

text: r

text: (Sec.

text: But

text: other

text: hypotheses

text: induce

text: diﬀerences.

text: The

text: main

text: conceptual

text: advantage

text: of

text: the

text: geometric

text: cor-

text: This

text: embodies

text: the

text: general

text: observation

text: that

text: the

text: linear

text: rection

text: scheme

text: is

text: that

text: it

text: relies

text: on

text: a

text: structural

text: descrip-

text: regression

text: includes

text: both

text: spatial

text: leakage

text: eﬀects

text: and

text: true

text: tion

text: of

text: spatial

text: leakage

text: adapted

text: to

text: the

text: inverse

text: operator,

text: connectivity.

text: More

text: precisely,

text: the

text: regression

text: coeﬃcient

text: whereas

text: orthogonalization

text: uses

text: statistical

text: features

text: of

text: re-

text: appears

text: to

text: be

text: the

text: sum

text: of

text: the

text: spatial

text: leakage

text: model

text: constructed

text: signals

text: without

text: explicit

text: reference

text: to

text: the

text: in-

text: coupling

text: and

text: of

text: the

text: linear

text: instantaneous

text: connectivity

text: es-

text: verse

text: model.

text: This

text: implies

text: that

text: the

text: second

text: and

text: third

text: hy-

text: timate

text: after

text: geometric

text: correction.

text: In

text: the

text: limit

text: where

text: the

text: potheses

text: used

text: by

text: orthogonalization

text: (Sec.

text: are

text: not

text: nec-

text: model

text: is

text: exact,

text: this

text: second

text: term

text: represents

text: a

text: true

text: state

text: essary

text: for

text: the

text: geometric

text: correction

text: scheme.

text: Indeed,

text: the

text: interaction

text: (see

text: property

text: (ii)

text: of

text: Sec.

text: that

text: is

text: eliminated

text: latter

text: automatically

text: conforms

text: to

text: the

text: temporal

text: character-

text: by

text: orthogonalization

text: (overcorrection

text: bias).

text: istics

text: of

text: spatial

text: leakage

text: (and

text: more

text: precisely

text: of

text: the

text: re-

text: It

text: will

text: be

text: useful

text: for

text: our

text: subsequent

text: analyses

text: to

text: promote

text: solving

text: operator,

text: see

text: Secs.

text: and

text: which

text: may

text: or

text: may

text: this

text: relation

text: at

text: of

text: the

text: ﬁelds.

text: Plugging

text: not

text: have

text: instantaneous

text: eﬀects

text: depending

text: on

text: the

text: inverse

text: Eq.

text: into

text: the

text: linear

text: regression

text: yields

text: model.

text: Furthermore,

text: it

text: does

text: not

text: confound

text: true

text: connec-

text: tivity

text: with

text: spatial

text: leakage

text: eﬀects

text: and

text: so

text: does

text: not

text: ex-

text: Φ⊥(r,

text: t)

text: i

text: Im

text: Φgcs(r,

text: t)

text: t)

text: hibit

text: the

text: overcorrection

text: bias

text: of

text: orthogonalization.

text: For

text: see

text: Appendix

text: for

text: details.

text: Geometrically,

text: this

text: means

text: that

text: example,

text: this

text: bias

text: implies

text: that

text: the

text: reconstruction

text: may

text: the

text: orthogonalized

text: ﬁeld

text: Φ⊥(r,

text: t)

text: equals

text: to

text: the

text: projection

text: be

text: nontrivially

text: aﬀected

text: by

text: orthogonalization

text: even

text: in

text: the

text: of

text: the

text: corrected

text: ﬁeld

text: Φgcs(r,

text: t)

text: onto

text: the

text: direction

text: per-

text: absence

text: of

text: spatial

text: leakage,

text: whereas

text: this

text: does

text: not

text: happen

text: pendicular

text: to

text: Ψ(r

text: t).

text: A

text: similar

text: formula

text: was

text: derived

text: in

text: with

text: the

text: geometric

text: correction

text: scheme

text: (see

text: property

text: (i)

text: of

text: Ref.

text: with

text: the

text: uncorrected

text: reconstruction

text: Ψ(r,

text: t)

text: in

text: Sec.

text: place

text: of

text: the

text: corrected

text: one

text: Φgcs(r,

text: t).

text: This

text: interchange-

text: On

text: the

text: other

text: hand,

text: some

text: hypotheses

text: of

text: the

text: geometric

text: ability

text: is

text: indicative

text: that

text: the

text: linear

text: instantaneous

text: spatial

text: correction

text: are

text: not

text: required

text: for

text: orthogonalization.

text: First,

text: leakage

text: eﬀect

text: has

text: been

text: completely

text: eliminated

text: by

text: orthog-

text: measurement

text: noise

text: was

text: neglected

text: in

text: our

text: derivation

text: of

text: the

text: onalization

text: (notwithstanding

text: its

text: overcorrection

text: eﬀect).

text: spatial

text: leakage

text: model

text: (Sec.

text: whereas

text: the

text: regression

text: au-

text: tomatically

text: takes

text: care

text: of

text: noise

text: contributions.

text: This

text: rep-

text: Polar

text: coordinates

text: resents

text: an

text: advantage

text: of

text: orthogonalization.

text: Second,

text: the

text: In

text: the

text: next

text: two

text: sections,

text: we

text: shall

text: focus

text: on

text: two

text: speciﬁc

text: condition

text: that

text: spatial

text: leakage

text: eﬀects

text: to

text: r

text: are

text: negligi-

text: connectivity

text: indices

text: classically

text: applied

text: to

text: oscillatory

text: or

text: ble

text: (Sec.

text: was

text: not

text: explicitly

text: assumed

text: in

text: orthogonaliza-

text: narrow-band

text: time

text: series:

text: phase

text: coherence

text: and

text: amplitude

text: tion.

text: It

text: is

text: noteworthy,

text: however,

text: that

text: this

text: hypothesis

text: was

text: correlation.

text: Their

text: deﬁnition

text: and

text: analysis

text: will

text: be

text: sim-

text: instrumental

text: to

text: characterize

text: spatial

text: leakage

text: exactly

text: and

text: pliﬁed

text: by

text: using

text: ﬁeld

text: coordinates

text: emphasizing

text: phase

text: and

text: avoid

text: any

text: overcorrection

text: bias

text: in

text: the

text: geometric

text: correction

text: amplitude

text: ﬂuctuations,

text: scheme.

text: Ψ(r

text: t)

text: A

text: (t)

text: exp

text: iθ

text: (t)

text: Framework

text: for

text: quantitative

text: analysis

text: Φgcs(r,

text: t)

text: Agcs(t)

text: exp

text: iθgcs(t)

text: We

text: now

text: turn

text: to

text: some

text: quantitative

text: considerations,

text: our

text: Φ⊥(r,

text: t)

text: A⊥(t)

text: exp

text: iθ⊥(t)

text: goal

text: being

text: to

text: illustrate

text: the

text: overcorrection

text: eﬀect

text: of

text: or-

text: thogonalization

text: (compared

text: to

text: the

text: geometric

text: approach).

text: In

text: these

text: notations,

text: the

text: relation

text: becomes

text: To

text: single

text: out

text: this

text: overcorrection

text: bias,

text: we

text: shall

text: work

text: from

text: now

text: on

text: in

text: a

text: restricted

text: framework

text: where

text: spatial

text: leakage

text: A⊥(t)

text: eiθ⊥(t)

text: i

text: Agcs(t)

text: sin(θgcs(t)

text: eﬀects

text: are

text: both

text: linear

text: and

text: instantaneous,

text: so

text: our

text: model

text: which

text: directly

text: implies

text: assumes

text: the

text: form

text: Λ(r,

text: t)

text: k(r,

text: t)

text: t)

text: π

text: θ⊥(t)

text: sign[sin(θgcs(t)

text: An

text: explicit

text: example

text: is

text: given

text: in

text: Appendix

text: The

text: coupling

text: constant

text: k(r,

text: r

text: t)

text: R

text: encodes

text: the

text: spatial

text: leakage

text: eﬀect.

text: A⊥(t)

text: Agcs(t)

text: sin(θgcs(t)

text: ##LTLine##


text: 2 S. ANANTHARAMAN, C. BOUCHARD, PALIATH NARENDRANc, AND M. RUSINOWITCH of integers, with a given ‘base’ integer; such a list of partial sums (resp. products) can be calculated, incrementally, with the help of the following two equations: bc(nil, z) = nil, bc(cons(x, Y ), z) = cons(h(x, z), bc(Y, h(x, z))) where nil is the empty list, z is the given base integer, x is an integer variable, and Y is the given list of integers. The partial sums (resp. products) are returned as a list, by evaluating the function bc, when h(x, z) is interpreted as the sum (resp. product) of x with the given base integer z. A more sophisticated example is the Cipher Block Chaining encryption mode (CBC, in short), employed in cryptography, a mode which uses the AC-operator exclusive-or (XOR) ⊕ for ‘chaining the ciphers across the message blocks’; here is how this is done: Let stand for XOR (which we let distribute over block concatenation), and let M = p . . . p be a message 1 n given as a list of n ‘plaintext’ message subblocks. Then the encryption of M, with any given public key k and an initialization vector v, is deﬁned as the list c . . . c of ciphertext ⊕ ⊕ 1 n ≤ message subblocks, where: c = e (p v), and c = e (p c − ), for any 1 < i n. (Note: 1 k 1 i k i i 1 It is usual in Cryptography to see a message as a sequence of “records”, each record being decomposed into a sequence of blocks of the same size; what we refer to as ‘message’ in this paper, would then correspond to a ‘record’ in the sense of cryptography.) The above set of equations also models this CBC encryption mode: for this, we interpret the function h(x, y) ⊕ as the encryption e (x y) of any single block message x, XOR-ed with the initialization k vector y, using the given public key k. Under such a vision, a message M is decomposed as (cid:48) the concatenation of its ﬁrst message block m with the rest of the message list M , i.e., we · (cid:48) write M = m M ; then, the encryption of M with any given public key k, with x taken as · (cid:48) initialization vector (IV), is derived by bc(M, x) = h(m, x) bc(M , h(m, x)). Actually, our interest in the equational theory deﬁned by the above two equations was motivated by the possibility of such a modeling for Cipher Block Chaining, and the fact that rewrite as well as uniﬁcation techniques are often employable, with success, for the formal analysis of cryptographic protocols (cf. e.g., [1, 3, 7, 8, 9], and also the concluding section). This paper is organized as follows. In Section we introduce our notation and the basic notions used in the sequel; we shall observe, in particular, that the two equations above can be turned into rewrite rules and form a convergent rewrite system over a 2-sorted signature: lists and elements. Our concern in Section is the uniﬁcation problem modulo this rewrite BC system, that we denote by ; we present a 2-level inference system (corresponding, in a way, to the two sorts of the signature) for solving this problem. Although our main aim is to investigate the uniﬁcation problem for the case where h is an interpreted function symbol (as in the two situations illustrated above), we shall also be considering the case where h is a free uninterpreted symbol. The soundness and completeness of our inference procedure are established in Section . While the complexity of the uniﬁcation problem is polynomial over the size of the problem when h is uninterpreted, it turns out to be NP-complete when h is interpreted so that the rewrite system models CBC encryption. We then present, in DBC Section , a 2-sorted convergent system that fully models at an abstract level, a block chaining cipher-decipher mode without using any AC-operators; this is done by adding a couple of equations to the above two: one for specifying a left-inverse g for h (g does the deciphering), and the other for specifying the block chaining mode for deciphering. A 2-level inference procedure extending the one given in Section is presented, and is shown to be DBC sound and complete for uniﬁcation modulo this extended system ; uniﬁcation modulo

text: S.

text: ANANTHARAMAN,

text: C.

text: BOUCHARD,

text: PALIATH

text: NARENDRANc,

text: AND

text: M.

text: RUSINOWITCH

text: of

text: integers,

text: with

text: a

text: given

text: ‘base’

text: integer;

text: such

text: a

text: list

text: of

text: partial

text: sums

text: (resp.

text: products)

text: can

text: be

text: calculated,

text: incrementally,

text: with

text: the

text: help

text: of

text: the

text: following

text: two

text: equations:

text: bc(nil,

text: z)

text: nil,

text: bc(cons(x,

text: Y

text: z)

text: cons(h(x,

text: z),

text: bc(Y,

text: h(x,

text: z)))

text: where

text: is

text: the

text: empty

text: list,

text: z

text: is

text: the

text: given

text: base

text: integer,

text: x

text: is

text: an

text: integer

text: variable,

text: and

text: Y

text: is

text: the

text: given

text: list

text: of

text: integers.

text: The

text: partial

text: sums

text: (resp.

text: products)

text: are

text: returned

text: as

text: a

text: list,

text: by

text: evaluating

text: the

text: function

text: bc,

text: when

text: h(x,

text: z)

text: is

text: interpreted

text: as

text: the

text: sum

text: (resp.

text: product)

text: of

text: x

text: with

text: the

text: given

text: base

text: integer

text: z.

text: A

text: more

text: sophisticated

text: example

text: is

text: the

text: Cipher

text: Block

text: Chaining

text: encryption

text: mode

text: (CBC,

text: in

text: short),

text: employed

text: in

text: cryptography,

text: a

text: mode

text: which

text: uses

text: the

text: AC-operator

text: exclusive-or

text: (XOR)

text: for

text: ‘chaining

text: the

text: ciphers

text: across

text: the

text: message

text: blocks’;

text: here

text: is

text: how

text: this

text: is

text: done:

text: Let

text: stand

text: for

text: XOR

text: (which

text: we

text: let

text: distribute

text: over

text: block

text: concatenation),

text: and

text: let

text: M

text: p

text: p

text: be

text: a

text: message

text: n

text: given

text: as

text: a

text: list

text: of

text: n

text: ‘plaintext’

text: message

text: subblocks.

text: Then

text: the

text: encryption

text: of

text: M,

text: with

text: any

text: given

text: public

text: key

text: k

text: and

text: an

text: initialization

text: vector

text: v,

text: is

text: deﬁned

text: as

text: the

text: list

text: c

text: c

text: of

text: ciphertext

text: n

text: message

text: subblocks,

text: where:

text: c

text: e

text: (p

text: v),

text: and

text: c

text: e

text: (p

text: c

text: for

text: any

text: i

text: n.

text: (Note:

text: k

text: i

text: k

text: i

text: i

text: It

text: is

text: usual

text: in

text: Cryptography

text: to

text: see

text: a

text: message

text: as

text: a

text: sequence

text: of

text: “records”,

text: each

text: record

text: being

text: decomposed

text: into

text: a

text: sequence

text: of

text: blocks

text: of

text: the

text: same

text: size;

text: what

text: we

text: refer

text: to

text: as

text: ‘message’

text: in

text: this

text: paper,

text: would

text: then

text: correspond

text: to

text: a

text: ‘record’

text: in

text: the

text: sense

text: of

text: cryptography.)

text: The

text: above

text: set

text: of

text: equations

text: also

text: models

text: this

text: CBC

text: encryption

text: mode:

text: for

text: this,

text: we

text: interpret

text: the

text: function

text: h(x,

text: y)

text: as

text: the

text: encryption

text: e

text: (x

text: y)

text: of

text: any

text: single

text: block

text: message

text: x,

text: XOR-ed

text: with

text: the

text: initialization

text: k

text: vector

text: y,

text: using

text: the

text: given

text: public

text: key

text: k.

text: Under

text: such

text: a

text: vision,

text: a

text: message

text: M

text: is

text: decomposed

text: as

text: the

text: concatenation

text: of

text: its

text: ﬁrst

text: message

text: block

text: m

text: with

text: the

text: rest

text: of

text: the

text: message

text: list

text: M

text: i.e.,

text: we

text: write

text: M

text: m

text: M

text: then,

text: the

text: encryption

text: of

text: M

text: with

text: any

text: given

text: public

text: key

text: k,

text: with

text: x

text: taken

text: as

text: initialization

text: vector

text: (IV),

text: is

text: derived

text: by

text: bc(M,

text: x)

text: h(m,

text: x)

text: bc(M

text: h(m,

text: x)).

text: Actually,

text: our

text: interest

text: in

text: the

text: equational

text: theory

text: deﬁned

text: by

text: the

text: above

text: two

text: equations

text: was

text: motivated

text: by

text: the

text: possibility

text: of

text: such

text: a

text: modeling

text: for

text: Cipher

text: Block

text: Chaining,

text: and

text: the

text: fact

text: that

text: rewrite

text: as

text: well

text: as

text: uniﬁcation

text: techniques

text: are

text: often

text: employable,

text: with

text: success,

text: for

text: the

text: formal

text: analysis

text: of

text: cryptographic

text: protocols

text: (cf.

text: e.g.,

text: and

text: also

text: the

text: concluding

text: section).

text: This

text: paper

text: is

text: organized

text: as

text: follows.

text: In

text: Section

text: we

text: introduce

text: our

text: notation

text: and

text: the

text: basic

text: notions

text: used

text: in

text: the

text: sequel;

text: we

text: shall

text: observe,

text: in

text: particular,

text: that

text: the

text: two

text: equations

text: above

text: can

text: be

text: turned

text: into

text: rewrite

text: rules

text: and

text: form

text: a

text: convergent

text: rewrite

text: system

text: over

text: a

text: signature:

text: lists

text: and

text: elements.

text: Our

text: concern

text: in

text: Section

text: is

text: the

text: uniﬁcation

text: problem

text: modulo

text: this

text: rewrite

text: BC

text: system,

text: that

text: we

text: denote

text: by

text: we

text: present

text: a

text: inference

text: system

text: (corresponding,

text: in

text: a

text: way,

text: to

text: the

text: two

text: sorts

text: of

text: the

text: signature)

text: for

text: solving

text: this

text: problem.

text: Although

text: our

text: main

text: aim

text: is

text: to

text: investigate

text: the

text: uniﬁcation

text: problem

text: for

text: the

text: case

text: where

text: h

text: is

text: an

text: interpreted

text: function

text: symbol

text: (as

text: in

text: the

text: two

text: situations

text: illustrated

text: above),

text: we

text: shall

text: also

text: be

text: considering

text: the

text: case

text: where

text: h

text: is

text: a

text: free

text: uninterpreted

text: symbol.

text: The

text: soundness

text: and

text: completeness

text: of

text: our

text: inference

text: procedure

text: are

text: established

text: in

text: Section

text: While

text: the

text: complexity

text: of

text: the

text: uniﬁcation

text: problem

text: is

text: polynomial

text: over

text: the

text: size

text: of

text: the

text: problem

text: when

text: h

text: is

text: uninterpreted,

text: it

text: turns

text: out

text: to

text: be

text: NP-complete

text: when

text: h

text: is

text: interpreted

text: so

text: that

text: the

text: rewrite

text: system

text: models

text: CBC

text: encryption.

text: We

text: then

text: present,

text: in

text: DBC

text: Section

text: a

text: convergent

text: system

text: that

text: fully

text: models

text: at

text: an

text: abstract

text: level,

text: a

text: block

text: chaining

text: cipher-decipher

text: mode

text: without

text: using

text: any

text: AC-operators;

text: this

text: is

text: done

text: by

text: adding

text: a

text: couple

text: of

text: equations

text: to

text: the

text: above

text: two:

text: one

text: for

text: specifying

text: a

text: left-inverse

text: g

text: for

text: h

text: (g

text: does

text: the

text: deciphering),

text: and

text: the

text: other

text: for

text: specifying

text: the

text: block

text: chaining

text: mode

text: for

text: deciphering.

text: A

text: inference

text: procedure

text: extending

text: the

text: one

text: given

text: in

text: Section

text: is

text: presented,

text: and

text: is

text: shown

text: to

text: be

text: DBC

text: sound

text: and

text: complete

text: for

text: uniﬁcation

text: modulo

text: this

text: extended

text: system

text: uniﬁcation

text: modulo


text: 20 S. ANANTHARAMAN, C. BOUCHARD, PALIATH NARENDRANc, AND M. RUSINOWITCH DBC P A(cid:48)(cid:48) Given any -uniﬁcation problem in standard form, let denote the inference IN F(cid:48)(cid:48) procedure based on the rules of , given above for its list-equations; we augment the A(cid:48)(cid:48) l procedure with any given complete procedure for solving the residual set of element- IN F(cid:48)(cid:48) equations in the problem, when the list-inference rules of are no longer applicable. l We have then the following result: A(cid:48)(cid:48) DBC Proposition 5.4. The procedure is sound and complete for solving -uniﬁcation problems given in standard form. A(cid:48)(cid:48) Proof. The proof uses the same lines of reasoning as for Proposition 4.1. The procedure is sound, because to any solution of a problem derived under any of its inferences, corresponds A(cid:48)(cid:48) a solution for the initial problem. The completeness of is again proved, for any given problem, by induction on the maximum number of inference steps needed for the termination A(cid:48)(cid:48) of the procedure on the problem; and using case analysis when necessary, based on the “don’t-know” inference rules (DB6.a)–(DB8) above, for such an analysis. We leave out the details, which are straightforward. P DBC Proposition 5.5. Let be a -uniﬁcation problem in standard form, to which none of IN F(cid:48)(cid:48) the inferences of is applicable. Then its subset of list-equations with non-nil variables l on the left-hand side is in d-solved form. IN F(cid:48)(cid:48) Proof. This extends Proposition 3.6 to the inference system . Note that we just l need to show the following: From any given node [U] on any given connected component Γ of the Propagation graph G , there is an unambiguous, cycle-free, directed path to a l well-determined end-node on Γ. Now, given that any directed arc on G is labeled with l either > , or > , or > , there can be at most one outgoing arc from [U]: otherwise cons bc db one of the inferences (DB2)–(DB8) would have been applicable; there can be no directed (cid:31) -cycle either at [U], otherwise the Occur-Check violation rule would have been applicable. l Thus, the proof of that earlier proposition carries over, essentially verbatim. DBC Proposition 5.6. Uniﬁcation modulo the theory is NP-complete. DBC P Proof. Given any -uniﬁcation problem , computing a standard form can be done in P polynomial time (wrt the number of variables of ); the same holds also for constructing the IN F(cid:48)(cid:48) propagation graph for the standard form. Applying then the inference rules of till l termination, on this standard form, takes only polynomially many steps, by Proposition 5.3. In case of non-failure, extracting the set of element-equations from the resulting problem can obviously be done in polynomial time. P To show that solving is in NP, it suﬃces therefore to show that the set of its element- equations can be solved, modulo the theory deﬁned by the single equation g(h(x, y), y) = x, in nondeterministic polynomial time. But this is a collapsing convergent system, and the uniﬁcation problem for such theories is known to be decidable and ﬁnitary [13, 18]. In ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: S.

text: ANANTHARAMAN,

text: C.

text: BOUCHARD,

text: PALIATH

text: NARENDRANc,

text: AND

text: M.

text: RUSINOWITCH

text: DBC

text: P

text: Given

text: any

text: -uniﬁcation

text: problem

text: in

text: standard

text: form,

text: let

text: denote

text: the

text: inference

text: IN

text: procedure

text: based

text: on

text: the

text: rules

text: of

text: given

text: above

text: for

text: its

text: list-equations;

text: we

text: augment

text: the

text: l

text: procedure

text: with

text: any

text: given

text: complete

text: procedure

text: for

text: solving

text: the

text: residual

text: set

text: of

text: element-

text: IN

text: equations

text: in

text: the

text: problem,

text: when

text: the

text: list-inference

text: rules

text: of

text: are

text: no

text: longer

text: applicable.

text: l

text: We

text: have

text: then

text: the

text: following

text: result:

text: DBC

text: Proposition

text: The

text: procedure

text: is

text: sound

text: and

text: complete

text: for

text: solving

text: -uniﬁcation

text: problems

text: given

text: in

text: standard

text: form.

text: Proof.

text: The

text: proof

text: uses

text: the

text: same

text: lines

text: of

text: reasoning

text: as

text: for

text: Proposition

text: The

text: procedure

text: is

text: sound,

text: because

text: to

text: any

text: solution

text: of

text: a

text: problem

text: derived

text: under

text: any

text: of

text: its

text: inferences,

text: corresponds

text: a

text: solution

text: for

text: the

text: initial

text: problem.

text: The

text: completeness

text: of

text: is

text: again

text: proved,

text: for

text: any

text: given

text: problem,

text: by

text: induction

text: on

text: the

text: maximum

text: number

text: of

text: inference

text: steps

text: needed

text: for

text: the

text: termination

text: of

text: the

text: procedure

text: on

text: the

text: problem;

text: and

text: using

text: case

text: analysis

text: when

text: necessary,

text: based

text: on

text: the

text: “don’t-know”

text: inference

text: rules

text: above,

text: for

text: such

text: an

text: analysis.

text: We

text: leave

text: out

text: the

text: details,

text: which

text: are

text: straightforward.

text: P

text: DBC

text: Proposition

text: Let

text: be

text: a

text: -uniﬁcation

text: problem

text: in

text: standard

text: form,

text: to

text: which

text: of

text: IN

text: the

text: inferences

text: of

text: is

text: applicable.

text: Then

text: its

text: subset

text: of

text: list-equations

text: with

text: non-nil

text: variables

text: l

text: on

text: the

text: left-hand

text: side

text: is

text: in

text: d-solved

text: form.

text: IN

text: Proof.

text: This

text: extends

text: Proposition

text: to

text: the

text: inference

text: system

text: Note

text: that

text: we

text: just

text: l

text: need

text: to

text: show

text: the

text: following:

text: From

text: any

text: given

text: node

text: [U]

text: on

text: any

text: given

text: connected

text: component

text: Γ

text: of

text: the

text: Propagation

text: graph

text: G

text: there

text: is

text: an

text: unambiguous,

text: cycle-free,

text: directed

text: path

text: to

text: a

text: l

text: well-determined

text: end-node

text: on

text: Γ.

text: Now,

text: given

text: that

text: any

text: directed

text: arc

text: on

text: G

text: is

text: labeled

text: with

text: l

text: either

text: or

text: or

text: there

text: can

text: be

text: at

text: most

text: one

text: outgoing

text: arc

text: from

text: [U]:

text: otherwise

text: cons

text: bc

text: db

text: one

text: of

text: the

text: inferences

text: would

text: have

text: been

text: applicable;

text: there

text: can

text: be

text: no

text: directed

text: -cycle

text: either

text: at

text: [U],

text: otherwise

text: the

text: Occur-Check

text: violation

text: rule

text: would

text: have

text: been

text: applicable.

text: l

text: Thus,

text: the

text: proof

text: of

text: that

text: earlier

text: proposition

text: carries

text: over,

text: essentially

text: verbatim.

text: DBC

text: Proposition

text: Uniﬁcation

text: modulo

text: the

text: theory

text: is

text: NP-complete.

text: DBC

text: P

text: Proof.

text: Given

text: any

text: -uniﬁcation

text: problem

text: computing

text: a

text: standard

text: form

text: can

text: be

text: done

text: in

text: P

text: polynomial

text: time

text: (wrt

text: the

text: number

text: of

text: variables

text: of

text: the

text: same

text: holds

text: also

text: for

text: constructing

text: the

text: IN

text: propagation

text: graph

text: for

text: the

text: standard

text: form.

text: Applying

text: then

text: the

text: inference

text: rules

text: of

text: till

text: l

text: termination,

text: on

text: this

text: standard

text: form,

text: takes

text: only

text: polynomially

text: many

text: steps,

text: by

text: Proposition

text: In

text: case

text: of

text: non-failure,

text: extracting

text: the

text: set

text: of

text: element-equations

text: from

text: the

text: resulting

text: problem

text: can

text: obviously

text: be

text: done

text: in

text: polynomial

text: time.

text: P

text: To

text: show

text: that

text: solving

text: is

text: in

text: NP,

text: it

text: suﬃces

text: therefore

text: to

text: show

text: that

text: the

text: set

text: of

text: its

text: element-

text: equations

text: can

text: be

text: solved,

text: modulo

text: the

text: theory

text: deﬁned

text: by

text: the

text: single

text: equation

text: g(h(x,

text: y),

text: y)

text: x,

text: in

text: nondeterministic

text: polynomial

text: time.

text: But

text: this

text: is

text: a

text: collapsing

text: convergent

text: system,

text: and

text: the

text: uniﬁcation

text: problem

text: for

text: such

text: theories

text: is

text: known

text: to

text: be

text: decidable

text: and

text: ﬁnitary

text: In

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: 26 S. ANANTHARAMAN, C. BOUCHARD, PALIATH NARENDRANc, AND M. RUSINOWITCH Appendix-1: On the Cancellativity properties of bc, g and db Lemma A. For all terms T , T , t, we have: 1 2 ≈ ≈ bc(T , t) BC bc(T , t) if and only if T BC T . 1 2 1 2 Proof. The proof is by structural induction on the terms, based on the semi-cancellativity of h and the cancellativity of cons. If either T or T is nil, then the other has to be nil 1 2 too, and the assertion of the Lemma is trivial. So suppose that T and T are not nil. Then (cid:48) (cid:48) 1 (cid:48) (cid:48) 2 T = cons(u , T ) and T = cons(u , T ), for some terms u , u , T , T . Substituting back 1 1 1 2 2 2 1BC2 1 2 into the original equation and applying the second axiom of , we deduce that: (cid:48) ≈ (cid:48) cons( h(u , t), bc(T , h(u , t)) ) BC cons( h(u , t), bc(T , h(u , t)) ) 1 1 1 2 2 2 Since cons is cancellative, we get: ≈ (cid:48) ≈ (cid:48) h(u , t) BC h(u , t), and bc(T , h(u , t)) BC bc(T , h(u , t)). 1 2 1 1 2 2 From the semi-cancellativity of h, we then deduce that: ≈ (cid:48) ≈ (cid:48) u BC u , and bc(T , h(u , t)) BC bc(T , h(u , t)). 1 2 1 1 2 1 (cid:48) ≈ (cid:48) Therefore, by structural induction, we deduce that T BC T , and the result follows. 1 2 Lemma B. For all terms T, t , t , we have: 1 2 ≈ ≈ ≈ bc(T, t ) BC bc(T, t ) if and only if T BC nil or t BC t . 1 2 1 2 Proof. The proof is by exactly the same reasonings as for proving the previous lemma. We shall paraphrase these two lemmas together by saying that bc is “conditionally” semi-cancellative. ≈ Lemma C. For all terms u , T , u , T , u , u : If bc(cons(u , T ), u ) BC bc(cons(u , T ), u ) ≈ 1 1 2 2 3≈ 4 1 1 3 2 2 4 then h(u , u ) BC h(u , u ) and T BC T . 1 3 2 4 1 2 BC Proof. By applying the second axiom of , we get: ≈ cons( h(u , u ), bc(T , h(u , u )) ) BC cons( h(u , u ), bc(T , h(u , u )) ) 1 3 1 1 3 2 4 2 2 4 Cancellation on cons gives: ≈ ≈ h(u , u ) BC h(u , u ) and bc(T , h(u , u )) BC bc(T , h(u , u )) 1 3 2 4 1 1 3 2 2 4 ≈ By Lemma A above, this implies that T BC T . 1 2 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: S.

text: ANANTHARAMAN,

text: C.

text: BOUCHARD,

text: PALIATH

text: NARENDRANc,

text: AND

text: M.

text: RUSINOWITCH

text: On

text: the

text: Cancellativity

text: properties

text: of

text: bc,

text: g

text: and

text: db

text: Lemma

text: A.

text: For

text: all

text: terms

text: T

text: T

text: t,

text: we

text: have:

text: bc(T

text: t)

text: BC

text: bc(T

text: t)

text: if

text: and

text: only

text: if

text: T

text: BC

text: T

text: Proof.

text: The

text: proof

text: is

text: by

text: structural

text: induction

text: on

text: the

text: terms,

text: based

text: on

text: the

text: semi-cancellativity

text: of

text: h

text: and

text: the

text: cancellativity

text: of

text: cons.

text: If

text: either

text: T

text: or

text: T

text: is

text: nil,

text: then

text: the

text: other

text: has

text: to

text: be

text: too,

text: and

text: the

text: assertion

text: of

text: the

text: Lemma

text: is

text: trivial.

text: So

text: suppose

text: that

text: T

text: and

text: T

text: are

text: not

text: nil.

text: Then

text: T

text: cons(u

text: T

text: and

text: T

text: cons(u

text: T

text: for

text: some

text: terms

text: u

text: u

text: T

text: T

text: Substituting

text: back

text: into

text: the

text: original

text: equation

text: and

text: applying

text: the

text: second

text: axiom

text: of

text: we

text: deduce

text: that:

text: cons(

text: h(u

text: t),

text: bc(T

text: h(u

text: t))

text: BC

text: cons(

text: h(u

text: t),

text: bc(T

text: h(u

text: t))

text: Since

text: cons

text: is

text: cancellative,

text: we

text: get:

text: h(u

text: t)

text: BC

text: h(u

text: t),

text: and

text: bc(T

text: h(u

text: t))

text: BC

text: bc(T

text: h(u

text: t)).

text: From

text: the

text: semi-cancellativity

text: of

text: h,

text: we

text: then

text: deduce

text: that:

text: u

text: BC

text: u

text: and

text: bc(T

text: h(u

text: t))

text: BC

text: bc(T

text: h(u

text: t)).

text: Therefore,

text: by

text: structural

text: induction,

text: we

text: deduce

text: that

text: T

text: BC

text: T

text: and

text: the

text: result

text: follows.

text: Lemma

text: B.

text: For

text: all

text: terms

text: T,

text: t

text: t

text: we

text: have:

text: bc(T,

text: t

text: BC

text: bc(T,

text: t

text: if

text: and

text: only

text: if

text: T

text: BC

text: or

text: t

text: BC

text: t

text: Proof.

text: The

text: proof

text: is

text: by

text: exactly

text: the

text: same

text: reasonings

text: as

text: for

text: proving

text: the

text: previous

text: lemma.

text: We

text: shall

text: paraphrase

text: these

text: two

text: lemmas

text: together

text: by

text: saying

text: that

text: bc

text: is

text: “conditionally”

text: semi-cancellative.

text: Lemma

text: C.

text: For

text: all

text: terms

text: u

text: T

text: u

text: T

text: u

text: u

text: If

text: bc(cons(u

text: T

text: u

text: BC

text: bc(cons(u

text: T

text: u

text: 3≈

text: then

text: h(u

text: u

text: BC

text: h(u

text: u

text: and

text: T

text: BC

text: T

text: BC

text: Proof.

text: By

text: applying

text: the

text: second

text: axiom

text: of

text: we

text: get:

text: cons(

text: h(u

text: u

text: bc(T

text: h(u

text: u

text: BC

text: cons(

text: h(u

text: u

text: bc(T

text: h(u

text: u

text: Cancellation

text: on

text: cons

text: gives:

text: h(u

text: u

text: BC

text: h(u

text: u

text: and

text: bc(T

text: h(u

text: u

text: BC

text: bc(T

text: h(u

text: u

text: By

text: Lemma

text: A

text: above,

text: this

text: implies

text: that

text: T

text: BC

text: T

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: UNIFICATION MODULO A 2-SORTED EQUATIONAL THEORY FOR CBC 27 DBC DBC In what follows, by we shall mean the equational theory of Section , and the rewrite system it deﬁnes. DBC As for the analogs of the above results for the operator db of , we ﬁrst observe that the function g is not semi-cancellative – more precisely, it is not right-cancellative: (cid:54) indeed, we have g(h(g(t, u), u), u) =DBC g(t, u), although h(g(t, u), u) =DBC t, in general. But left-cancellativity holds for g.

text: UNIFICATION

text: MODULO

text: A

text: EQUATIONAL

text: THEORY

text: FOR

text: CBC

text: DBC

text: DBC

text: In

text: what

text: follows,

text: by

text: we

text: shall

text: mean

text: the

text: equational

text: theory

text: of

text: Section

text: and

text: the

text: rewrite

text: system

text: it

text: deﬁnes.

text: DBC

text: As

text: for

text: the

text: analogs

text: of

text: the

text: above

text: results

text: for

text: the

text: operator

text: db

text: of

text: we

text: ﬁrst

text: observe

text: that

text: the

text: function

text: g

text: is

text: not

text: semi-cancellative

text: more

text: precisely,

text: it

text: is

text: not

text: right-cancellative:

font: default

text: indeed,

text: we

text: have

text: g(h(g(t,

text: u),

text: u),

text: u)

text: =DBC

text: g(t,

text: u),

text: although

text: h(g(t,

text: u),

text: u)

text: =DBC

text: t,

text: in

text: general.

text: But

text: left-cancellativity

text: holds

text: for

text: g.


text: 4 SEA MSP BOS 0.6 DET Exact values 0.58 Perturbation analysis LGA ORD 0.56 DEN JFK 0.54 SFO EWR PHL 0.52 LAS BWI 0.5 !2 DFW 0.48 LAX 0.46 PHX CLT 0.44 IAH ATL 0.42 0.4 MCO -0.1 -0.05 0 0.05 0.1 SEA MSP " DET BOS FIG. 4: The validity of the theoretical prediction (13) for λ is tested LGA 2 ORD with the exact eigenvalue of the transition matrix of the dynamical DEN JFK process deﬁned on Fig. 2. When ε = 0, the process is Markovian and SFO EWR λ2 = 1/2. Increasing values of ε tend to slow down the relaxation PHL towards stationarity. LAS BWI DFW LAX PHX CLT ics ergodic [20]. Because the airport network is weighted, in IAH ATL contrast with previous example, the transition matrix of the MCO Markovian process is now given by FIG. 5: Illustration of the 19 ﬂight legs leaving Dallas (DFW) af- w ter coming from Atlanta (ATL). In a ﬁrst-order Markov model (up- TM = β , (12) per), the probability to follow a link, represented by its width, is αβ ∑ w β β proportional to the total volume of trafﬁc towards that airport, irre- spectively of the origin of the passenger. In a second-order Markov in order to provide an adequate baseline, and not uniform model (lower), however, the probability to follow link depends on where the passengers come from, with a strong bias towards their as in (3). w is the total number of passengers along ﬂight leg β origin. β, independently on where they come from. In order to in- vestigate the effect of memory, we consider a random process − driven by the tunable transition matrix T(p) = pT+(1 p)TM, that is a random walk process given by the ﬁrst-order Markov − process with probability (1 p), and by the second-order Markov process with probability p. This hybrid process mod- els the diffusion of an item, e.g. a virus or a bank note [21], 1 Exact values which travels with passengers and changes owner inside cities Exact values - Only return flights with probability p [9]. As shown in Fig 6, the perturbation 0.8 Perturbation analysis analysis provides a good approximation of λ for small val- 2 ues of p, and shows that memory signiﬁcantly slows down the 0.6 spreading process. This slowdown is driven by the high return !2 rate of the ﬂights observed in Fig. 5. To show so, we have cal- 0.4 − culated λ2 for the transition matrix pTR + (1 p)TM, where TR models a second-order process where only return ﬂights 0.2 are permitted, i.e. (cid:40) 0 0 0.2 0.4 0.6 0.8 1 p 1 for β = #j»i, Ti#R»jβ = 0 otherwise. (13) FpI=G.0,6t:he Eprfofeccetssoifsmﬁresmt-oorrydeornMλa2rkfoovratnhdewaihrepnorpt =ne1tw, iotriks.seWcohnedn- order Markov. Memory signiﬁcantly slows down diffusion, with λ 2 going from 0.77 to 0.07 from one end to the other, with a mixing As expected, this process slows down even further the ran- time going from 1.3 to 14.28, i.e. a slowndown by a factor of 11. dom walk process and ultimately leads to non-ergodic dynam- When only return ﬂights are considered for the second-order Markov ics when p = 1, as the corresponding memory network be- model, this slow-down is even more important, and the process be- comes disconnected in that case. comes non-ergodic, with λ2 = 0 when p = 1. V. CONCLUSION ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: SEA

text: MSP

text: BOS

text: DET

text: Exact

text: values

text: Perturbation

text: analysis

text: LGA

text: ORD

text: DEN

text: JFK

text: SFO

text: EWR

text: PHL

text: LAS

text: BWI

text: DFW

text: LAX

text: PHX

text: CLT

text: IAH

text: ATL

text: MCO

text: SEA

text: MSP

text: DET

text: BOS

text: FIG.

text: The

label: caption

text: validity

text: of

text: the

text: theoretical

text: prediction

text: for

text: λ

text: is

text: tested

text: LGA

text: ORD

text: with

text: the

text: exact

text: eigenvalue

text: of

text: the

text: transition

text: matrix

text: of

text: the

text: dynamical

text: DEN

text: JFK

text: process

text: deﬁned

text: on

text: Fig.

text: When

text: ε

text: the

text: process

text: is

text: Markovian

text: and

text: SFO

text: EWR

text: λ2

text: Increasing

text: values

text: of

text: ε

text: tend

text: to

text: slow

text: down

text: the

text: relaxation

text: PHL

text: towards

text: stationarity.

text: LAS

text: BWI

text: DFW

text: LAX

text: PHX

text: CLT

text: ics

text: ergodic

text: Because

text: the

text: airport

text: network

text: is

text: weighted,

text: in

text: IAH

text: ATL

text: contrast

text: with

text: previous

text: example,

text: the

text: transition

text: matrix

text: of

text: the

text: MCO

text: Markovian

text: process

text: is

text: now

text: given

text: by

text: FIG.

text: Illustration

text: of

text: the

text: ﬂight

text: legs

text: leaving

text: Dallas

text: (DFW)

text: af-

text: w

text: ter

text: coming

text: from

text: Atlanta

text: (ATL).

text: In

text: a

text: ﬁrst-order

text: Markov

text: model

text: (up-

text: TM

text: β

text: per),

text: the

text: probability

text: to

text: follow

text: a

text: link,

text: represented

text: by

text: its

text: width,

text: is

text: αβ

text: w

text: β

text: β

text: proportional

text: to

text: the

text: total

text: volume

text: of

text: trafﬁc

text: towards

text: that

text: airport,

text: irre-

text: spectively

text: of

text: the

text: origin

text: of

text: the

text: passenger.

text: In

text: a

text: second-order

text: Markov

text: in

text: order

text: to

text: provide

text: an

text: adequate

text: baseline,

text: and

text: not

text: uniform

text: model

text: (lower),

text: however,

text: the

text: probability

text: to

text: follow

text: link

text: depends

text: on

text: where

text: the

text: passengers

text: come

text: from,

text: with

text: a

text: strong

text: bias

text: towards

text: their

text: as

text: in

text: w

text: is

text: the

text: total

text: number

text: of

text: passengers

text: along

text: ﬂight

text: leg

text: β

text: origin.

text: β,

text: independently

text: on

text: where

text: they

text: come

text: from.

text: In

text: order

text: to

text: in-

text: vestigate

text: the

text: effect

text: of

text: memory,

text: we

text: consider

text: a

text: random

text: process

text: driven

text: by

text: the

text: tunable

text: transition

text: matrix

text: T(p)

text: p)TM,

text: that

text: is

text: a

text: random

text: walk

text: process

text: given

text: by

text: the

text: ﬁrst-order

text: Markov

text: process

text: with

text: probability

text: p),

text: and

text: by

text: the

text: second-order

text: Markov

text: process

text: with

text: probability

text: p.

text: This

text: hybrid

text: process

text: mod-

text: els

text: the

text: diffusion

text: of

text: an

text: item,

text: e.g.

text: a

text: virus

text: or

text: a

text: bank

text: note

text: Exact

text: values

text: which

text: travels

text: with

text: passengers

text: and

text: changes

text: owner

text: inside

text: cities

text: Exact

text: values

text: Only

text: return

text: flights

text: with

text: probability

text: p

text: As

text: shown

text: in

text: Fig

text: the

text: perturbation

text: Perturbation

text: analysis

text: analysis

text: provides

text: a

text: good

text: approximation

text: of

text: λ

text: for

text: small

text: val-

text: ues

text: of

text: p,

text: and

text: shows

text: that

text: memory

text: signiﬁcantly

text: slows

text: down

text: the

text: spreading

text: process.

text: This

text: slowdown

text: is

text: driven

text: by

text: the

text: high

text: return

text: rate

text: of

text: the

text: ﬂights

text: observed

text: in

text: Fig.

text: To

text: show

text: so,

text: we

text: have

text: cal-

text: culated

text: λ2

text: for

text: the

text: transition

text: matrix

text: pTR

text: p)TM,

text: where

text: TR

text: models

text: a

text: second-order

text: process

text: where

text: only

text: return

text: ﬂights

text: are

text: permitted,

text: i.e.

text: p

text: for

text: β

text: #j»i,

text: Ti#R»jβ

text: otherwise.

text: iotriks.seWcohnedn-

text: order

text: Markov.

text: Memory

text: signiﬁcantly

text: slows

text: down

text: diffusion,

text: with

text: λ

text: going

text: from

text: to

text: from

text: one

text: end

text: to

text: the

text: other,

text: with

text: a

text: mixing

text: As

text: expected,

text: this

text: process

text: slows

text: down

text: even

text: further

text: the

text: ran-

text: time

text: going

text: from

text: to

text: i.e.

text: a

text: slowndown

text: by

text: a

text: factor

text: of

text: dom

text: walk

text: process

text: and

text: ultimately

text: leads

text: to

text: non-ergodic

text: dynam-

text: When

text: only

text: return

text: ﬂights

text: are

text: considered

text: for

text: the

text: second-order

text: Markov

text: ics

text: when

text: p

text: as

text: the

text: corresponding

text: memory

text: network

text: be-

text: model,

text: this

text: slow-down

text: is

text: even

text: more

text: important,

text: and

text: the

text: process

text: be-

text: comes

text: disconnected

text: in

text: that

text: case.

text: comes

text: non-ergodic,

text: with

text: λ2

text: when

text: p

text: V.

text: CONCLUSION

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

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: ##LTLine##

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: ##LTLine##

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: ##LTLine##

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: ##LTLine##

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: ##LTLine##

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: ##LTLine##

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: ##LTLine##


text: 6 (2006) [37] N. Masuda, K. Klemm and V.M. Egu´ıluz, Phys. Rev. Lett. 111, [22] T. S. Evans and R. Lambiotte, Phys. Rev. E 80, 016105 (2009). 188701 (2013). [23] Y.-Y. Ahn, J. P. Bagrow, and S. Lehmann, Nature 466, 761 [38] R. Lambiotte, L. Tabourier and J.-C. Delvenne, The European (2010). Physical Journal B 86, 320 (2013) [24] P. Boldi and M. Rosa. LA-WEB, IEEE Computer Society, 48- [39] G. Miritello, E. Moro and R. Lara, Phys. Rev. E 83, 045102 56 (2012). (2011). [25] D.J. Watts and S.H. Strogatz Nature 393: 440-442 (1998). [40] L.E.C. Rocha and V.D. Blondel, Phys. Rev. E 87, 042814 [26] M. Barahona and L.M. Pecora, Phys Rev Lett. 89, 054101 (2013). (2002). [41] L. Kovanen, M. Karsai, K. Kaski, J. Kerte´sz, and J. Sarama¨ki, [27] C. Castellano and R. Pastor-Satorras, Phys. Rev. Lett. 105, J. Stat. Mech., P11005 (2011). 218701 (2010). [42] T. Hoffmann, M. Porter and R. Lambiotte, Phys. Rev. E 86, [28] D. Centola and M. Macy, Am. J. of Sociology 113, 702 (2007). 046102 (2012). [29] S.V. Buldyrev, R. Parshani, G. Paul, H.E. Stanley, and S. [43] R. Pﬁtzner, I. Scholtes, A. Garas, C.J. Tessone, and F. Havlin, Nature 464, 1025 (2010). Schweitzer, Phys. Rev. Lett. 110, 198701 (2013) [30] E. A. Leicht and R. M. Douza, arXiv:0907.0894. [44] I. Scholtes, N. Wider, R. Pﬁtzner, A. Garas, C.J. Tessone and F. [31] S. Go´mez, A. D´ıaz-Guilera, J. Go´mez-Gardenes, C. Pe´rez- Schweitzer, arXiv:1307.4030 Vicente, Y. Moreno, and A. Arenas, Phys. Rev. Lett. 110, [45] In the case of directed networks, a network of L directed links 028701 (2013). leads to a memory network of L memory nodes. [32] B. Min and K.-I. Goh, arXiv:1307.2967 [46] The detailed spectral properties of memory networks will be the [33] P. Holme and J. Sarama¨ki, Physics Reports 519, 97-125 (2012). subject of a future work. [34] L.E.C. Rocha, F. Liljeros, and P. Holme, Proc. Natl. Acad. Sci. [47] When modelling the effect of non-exponential waiting time USA 107, 5706 (2010). distributions on diffusion, the dynamics shows a different [35] M. Karsai, M. Kivela¨, R. K. Pan, K. Kaski, J. Kerte´sz, A.-L. type of non-Markovianity, and the dynamics leads to integro- Baraba´si, and J. Sarama¨ki, Phys. Rev. E 83, 025102 (2011). differential equations in time [42]. [36] F. Peruani and L. Tabourier, PLoS ONE 6, e28860 (2011).

label: reference

text: N.

text: Masuda,

text: K.

text: Klemm

text: and

text: V.M.

text: Egu´ıluz,

text: Phys.

text: Rev.

text: Lett.

text: T.

text: S.

text: Evans

text: and

text: R.

text: Lambiotte,

text: Phys.

text: Rev.

text: E

text: Y.-Y.

text: Ahn,

text: J.

text: P.

text: Bagrow,

text: and

text: S.

text: Lehmann,

text: Nature

text: R.

text: Lambiotte,

text: L.

text: Tabourier

text: and

text: J.-C.

text: Delvenne,

text: The

text: European

text: Physical

text: Journal

text: B

text: P.

text: Boldi

text: and

text: M.

text: Rosa.

text: LA-WEB,

text: IEEE

text: Computer

text: Society,

text: G.

text: Miritello,

text: E.

text: Moro

text: and

text: R.

text: Lara,

text: Phys.

text: Rev.

text: E

text: D.J.

text: Watts

text: and

text: S.H.

text: Strogatz

text: Nature

text: L.E.C.

text: Rocha

text: and

text: V.D.

text: Blondel,

text: Phys.

text: Rev.

text: E

text: M.

text: Barahona

text: and

text: L.M.

text: Pecora,

text: Phys

text: Rev

text: Lett.

text: L.

text: Kovanen,

text: M.

text: Karsai,

text: K.

text: Kaski,

text: J.

text: Kerte´sz,

text: and

text: J.

text: Sarama¨ki,

text: C.

text: Castellano

text: and

text: R.

text: Pastor-Satorras,

text: Phys.

text: Rev.

text: Lett.

text: J.

text: Stat.

text: Mech.,

text: T.

text: Hoffmann,

text: M.

text: Porter

text: and

text: R.

text: Lambiotte,

text: Phys.

text: Rev.

text: E

text: D.

text: Centola

text: and

text: M.

text: Macy,

text: Am.

text: J.

text: of

text: Sociology

text: S.V.

text: Buldyrev,

text: R.

text: Parshani,

text: G.

text: Paul,

text: H.E.

text: Stanley,

text: and

text: S.

text: R.

text: Pﬁtzner,

text: I.

text: Scholtes,

text: A.

text: Garas,

text: C.J.

text: Tessone,

text: and

text: F.

text: Havlin,

text: Nature

text: Schweitzer,

text: Phys.

text: Rev.

text: Lett.

text: E.

text: A.

text: Leicht

text: and

text: R.

text: M.

text: Douza,

text: I.

text: Scholtes,

text: N.

text: Wider,

text: R.

text: Pﬁtzner,

text: A.

text: Garas,

text: C.J.

text: Tessone

text: and

text: F.

text: S.

text: Go´mez,

text: A.

text: D´ıaz-Guilera,

text: J.

text: Go´mez-Gardenes,

text: C.

text: Pe´rez-

text: Schweitzer,

text: Vicente,

text: Y.

text: Moreno,

text: and

text: A.

text: Arenas,

text: Phys.

text: Rev.

text: Lett.

text: In

text: the

text: case

text: of

text: directed

text: networks,

text: a

text: network

text: of

text: L

text: directed

text: links

text: leads

text: to

text: a

text: memory

text: network

text: of

text: L

text: memory

text: nodes.

text: B.

text: Min

text: and

text: K.-I.

text: Goh,

text: The

text: detailed

text: spectral

text: properties

text: of

text: memory

text: networks

text: will

text: be

text: the

text: P.

text: Holme

text: and

text: J.

text: Sarama¨ki,

text: Physics

text: Reports

text: subject

text: of

text: a

text: future

text: work.

text: L.E.C.

text: Rocha,

text: F.

text: Liljeros,

text: and

text: P.

text: Holme,

text: Proc.

text: Natl.

text: Acad.

text: Sci.

text: When

text: modelling

text: the

text: effect

text: of

text: non-exponential

text: waiting

text: time

text: USA

text: distributions

text: on

text: diffusion,

text: the

text: dynamics

text: shows

text: a

text: different

text: M.

text: Karsai,

text: M.

text: Kivela¨,

text: R.

text: K.

text: Pan,

text: K.

text: Kaski,

text: J.

text: Kerte´sz,

text: A.-L.

text: type

text: of

text: non-Markovianity,

text: and

text: the

text: dynamics

text: leads

text: to

text: integro-

text: Baraba´si,

text: and

text: J.

text: Sarama¨ki,

text: Phys.

text: Rev.

text: E

text: differential

text: equations

text: in

text: time

text: F.

text: Peruani

text: and

text: L.

text: Tabourier,

text: PLoS

text: ONE


text: the speed-density relation. In the case of bottlenecks and the speed-density relation good agreement with experimental data was achieved. Calibration of the model parameters was performed using plausible assumptions on the outcome of benchmark scenarios rather than numerical tests. Recalibration for diﬀerent scenarios was unnecessary. One main goal for the model was to ﬁnd a concise formulation with as few equations as possible and, at the same time, certain smoothness properties so that existence, uniqueness and smoothness of the solution would follow directly. The GNM only needs three equations, as opposed to four in force based models, to describe motion of one pedestrian. In addi- tion, we proposed a ﬂoor ﬁeld to steer pedestrians instead of constructing paths or guiding lines. The ﬂoor ﬁeld was computed by solving the eikonal equation using Sethian’s highly eﬃcient fast marching algorithm [35]. To achieve smoothness, molliﬁcation techniques were employed. The smoothness also enabled us to use numerical schemes of high order making the GNM computationally very eﬃcient. Two of the methods we introduced can easily be carried over to other models: The plausibility arguments that allowed us to calibrate free parameters hold independently of the model. The molliﬁcation techniques that led to the smooth functions could also be used by other diﬀerential equation based models like the Social Force Model [6, 13] or the Generalized Centrifugal Force Model [7]. Some of the most recent enhancements in crowd modeling rely on a ﬂoor ﬁeld to steer pedestrians towards the target. Among them are steering around crowd clusters [4, 31] and more sophisticated navigation on the tactical and strategic level [5]. These developments can be employed in the GNM without any change to the equations of motion. Some empirical observations, such as stop-and-go traﬃc [17, 40] are not yet well under- stood, neither from the experimental nor the theoretical point of view. In a mathematical model stability issues and bifurcations often are at the root of such phenomena. The concise mathematical formulation of the GNM as an ODE systems facilitates stability analysis and the investigation of bifurcations, both tasks that we are currently working on. ACKNOWLEDGMENTS This work was partially funded by the German Ministry of Research through the project MEPKA (Grant No. 17PNT028). Support from the TopMath Graduate Center of TUM Graduate School at Technische Universita¨t Mu¨nchen, Germany, and from the TopMath 16

text: the

text: speed-density

text: relation.

text: In

text: the

text: case

text: of

text: bottlenecks

text: and

text: the

text: speed-density

text: relation

text: good

text: agreement

text: with

text: experimental

text: data

text: was

text: achieved.

text: Calibration

text: of

text: the

text: model

text: parameters

text: was

text: performed

text: using

text: plausible

text: assumptions

text: on

text: the

text: outcome

text: of

text: benchmark

text: scenarios

text: rather

text: than

text: numerical

text: tests.

text: Recalibration

text: for

text: diﬀerent

text: scenarios

text: was

text: unnecessary.

text: One

text: main

text: goal

text: for

text: the

text: model

text: was

text: to

text: ﬁnd

text: a

text: concise

text: formulation

text: with

text: as

text: few

text: equations

text: as

text: possible

text: and,

text: at

text: the

text: same

text: time,

text: certain

text: smoothness

text: properties

text: so

text: that

text: existence,

text: uniqueness

text: and

text: smoothness

text: of

text: the

text: solution

text: would

text: follow

text: directly.

text: The

text: GNM

text: only

text: needs

text: three

text: equations,

text: as

text: opposed

text: to

text: four

text: in

text: force

text: based

text: models,

text: to

text: describe

text: motion

text: of

text: one

text: pedestrian.

text: In

text: addi-

text: tion,

text: we

text: proposed

text: a

text: ﬂoor

text: ﬁeld

text: to

text: steer

text: pedestrians

text: instead

text: of

text: constructing

text: paths

text: or

text: guiding

text: lines.

text: The

text: ﬂoor

text: ﬁeld

text: was

text: computed

text: by

text: solving

text: the

text: eikonal

text: equation

text: using

text: Sethian’s

text: highly

text: eﬃcient

text: fast

text: marching

text: algorithm

text: To

text: achieve

text: smoothness,

text: molliﬁcation

text: techniques

text: were

text: employed.

text: The

text: smoothness

text: also

text: enabled

text: us

text: to

text: use

text: numerical

text: schemes

text: of

text: high

text: order

text: making

text: the

text: GNM

text: computationally

text: very

text: eﬃcient.

text: Two

text: of

text: the

text: methods

text: we

text: introduced

text: can

text: easily

text: be

text: carried

text: over

text: to

text: other

text: models:

text: The

text: plausibility

text: arguments

text: that

text: allowed

text: us

text: to

text: calibrate

text: free

text: parameters

text: hold

text: independently

text: of

text: the

text: model.

text: The

text: molliﬁcation

text: techniques

text: that

text: led

text: to

text: the

text: smooth

text: functions

text: could

text: also

text: be

text: used

text: by

text: other

text: diﬀerential

text: equation

text: based

text: models

text: like

text: the

text: Social

text: Force

text: Model

text: or

text: the

text: Generalized

text: Centrifugal

text: Force

text: Model

text: Some

text: of

text: the

text: most

text: recent

text: enhancements

text: in

text: crowd

text: modeling

text: rely

text: on

text: a

text: ﬂoor

text: ﬁeld

text: to

text: steer

text: pedestrians

text: towards

text: the

text: target.

text: Among

text: them

text: are

text: steering

text: around

text: crowd

text: clusters

text: and

text: more

text: sophisticated

text: navigation

text: on

text: the

text: tactical

text: and

text: strategic

text: level

text: These

text: developments

text: can

text: be

text: employed

text: in

text: the

text: GNM

text: without

text: any

text: change

text: to

text: the

text: equations

text: of

text: motion.

text: Some

text: empirical

text: observations,

text: such

text: as

text: stop-and-go

text: traﬃc

text: are

text: not

text: yet

text: well

text: under-

text: stood,

text: neither

text: from

text: the

text: experimental

text: nor

text: the

text: theoretical

text: point

text: of

text: view.

text: In

text: a

text: mathematical

text: model

text: stability

text: issues

text: and

text: bifurcations

text: often

text: are

text: at

text: the

text: root

text: of

text: such

text: phenomena.

text: The

text: concise

text: mathematical

text: formulation

text: of

text: the

text: GNM

text: as

text: an

text: ODE

text: systems

text: facilitates

text: stability

text: analysis

text: and

text: the

text: investigation

text: of

text: bifurcations,

text: both

text: tasks

text: that

text: we

text: are

text: currently

text: working

text: on.

text: ACKNOWLEDGMENTS

text: This

text: work

text: was

text: partially

text: funded

text: by

text: the

text: German

text: Ministry

text: of

text: Research

text: through

text: the

text: project

text: MEPKA

text: (Grant

text: No.

text: Support

text: from

text: the

text: TopMath

text: Graduate

text: Center

text: of

text: TUM

text: Graduate

text: School

text: at

text: Technische

text: Universita¨t

text: Mu¨nchen,

text: Germany,

text: and

text: from

text: the

text: TopMath


text: DUALITY THEOREMS FOR COINVARIANT SUBSPACES OF H1 R. V. BESSONOV Abstract. Let θ be an inner function satisfying the connected level set con- dition of B. Cohn, and let K1 be the shift-coinvariant subspace of the Hardy θ space H1 generated by θ. We describe the dual space to K1 in terms of a θ bounded mean oscilla∩tion wi∗th respect to the Clark measure σα of θ. Namely, we prove that (Kθ1 zH1) = BMO(σα). The result implies a tw×o-sided estimate for the operator norm of a ﬁnite Hankel matrix of size n n via BthMe Ogr(oµu2pn){-ξno∈rmC :oξf2ints=st1a}n.dard symbol, where µ2n is the Haar measure on 1. Introduction A bounded analytic function θ in the open unit disk D = {z ∈ C : |z| < 1} is called inner if |θ(z)| = 1 for almost all points z on the unit circle T in the sense of angular boundary values. With every inner function θ we associate the shift- coinvariant [19] subspace Kp of the Hardy space Hp, θ ∩ (cid:54) (cid:54) ∞ Kp = Hp z¯θHp, 1 p . (1) θ As usual, functions in Hp are identiﬁed with their angular boundary values on the unit circle T; formula (1) means that f ∈ Kp if f ∈ Hp and there is g ∈ Hp such that f(z) = z¯θ(z)g(z) for almost all points zθ∈ T. An inner function θ is said to be one-component if its sublevel set Ω = {z ∈ D : |θ(z)| < δ} is connected for a δ positive number δ < 1. This class of inner functions was introduced by B.Cohn [12] → in 1982. It is very useful in studying Carleson-type embeddings Kp (cid:44) Lp(µ) and θ Riesz bases of reproducing kernels in Kp, see [3–5, 7, 12, 13, 17, 26] for results and θ further references. In this paper we describe the dual space to the space K1 generated by a one- θ component inner function θ. Our main result is the following formula: ∩ ∗ (K1 zH1) = BMO(σ ), (2) θ α where σ denotes the Clark measure of the inner function θ. Below we state α this result formally and apply it to the boundedness problem for truncated Hankel operators. 2010 Mathematics Subject Classiﬁcation. Primary 30J05. Key words and phrases. Inner function, Clark measure, discrete Hilbert transform, bounded mean oscillation, atomic Hardy space, truncated Hankel operators. This work is partially supported by RFBR grants 12-01-31492, 14-01-00748, by ISF grant 94/11, by JSC “Gazprom Neft”, and by the Chebyshev Laboratory (Department of Mathematics and Mechanics, St. Petersburg State University) under RF Government grant 11.G34.31.0026. 1 ##LTLine## ##LTLine## ##LTLine##

text: DUALITY

text: THEOREMS

text: FOR

text: COINVARIANT

text: SUBSPACES

text: OF

text: R.

text: V.

text: BESSONOV

text: Abstract.

text: Let

label: abstract

text: θ

text: be

text: an

text: inner

text: function

text: satisfying

text: the

text: connected

text: level

text: set

text: con-

text: dition

text: of

text: B.

text: Cohn,

text: and

text: let

text: be

text: the

text: shift-coinvariant

text: subspace

text: of

text: the

text: Hardy

text: θ

text: space

text: generated

text: by

text: θ.

text: We

text: describe

text: the

text: dual

text: space

text: to

text: in

text: terms

text: of

text: a

text: θ

text: bounded

text: mean

text: oscilla∩tion

text: wi∗th

text: respect

text: to

text: the

text: Clark

text: measure

text: σα

text: of

text: θ.

text: Namely,

text: we

text: prove

text: that

text: BMO(σα).

text: The

text: result

text: implies

text: a

text: tw×o-sided

text: estimate

text: for

text: the

text: operator

text: norm

text: of

text: a

text: ﬁnite

text: Hankel

text: matrix

text: of

text: size

text: n

text: n

text: via

text: BthMe

text: symbol,

text: where

text: is

text: the

text: Haar

text: measure

text: on

text: Introduction

text: A

text: bounded

text: analytic

text: function

text: θ

text: in

text: the

text: open

text: unit

text: disk

text: D

text: {z

text: C

text: |z|

text: is

text: called

text: inner

text: if

text: |θ(z)|

text: for

text: almost

text: all

text: points

text: z

text: on

text: the

text: unit

text: circle

text: T

text: in

text: the

text: sense

text: of

text: angular

text: boundary

text: values.

text: With

text: every

text: inner

text: function

text: θ

text: we

text: associate

text: the

text: shift-

text: coinvariant

text: subspace

text: Kp

text: of

text: the

text: Hardy

text: space

text: Hp,

text: θ

text: Kp

text: Hp

text: z¯θHp,

text: p

text: θ

text: As

text: usual,

text: functions

text: in

text: Hp

text: are

text: identiﬁed

text: with

text: their

text: angular

text: boundary

text: values

text: on

text: the

text: unit

text: circle

text: T;

text: formula

text: means

text: that

text: f

text: Kp

text: if

text: f

text: Hp

text: and

text: there

text: is

text: g

text: Hp

text: such

text: that

text: f(z)

text: z¯θ(z)g(z)

text: for

text: almost

text: all

text: points

text: zθ∈

text: T.

text: An

text: inner

text: function

text: θ

text: is

text: said

text: to

text: be

text: one-component

text: if

text: its

text: sublevel

text: set

text: Ω

text: {z

text: D

text: |θ(z)|

text: δ}

text: is

text: connected

text: for

text: a

text: δ

text: positive

text: number

text: δ

text: This

text: class

text: of

text: inner

text: functions

text: was

text: introduced

text: by

text: B.Cohn

text: in

text: It

text: is

text: very

text: useful

text: in

text: studying

text: Carleson-type

text: embeddings

text: Kp

text: Lp(µ)

text: and

text: θ

text: Riesz

text: bases

text: of

text: reproducing

text: kernels

text: in

text: Kp,

text: see

text: for

text: results

text: and

text: θ

text: further

text: references.

text: In

text: this

text: paper

text: we

text: describe

text: the

text: dual

text: space

text: to

text: the

text: space

text: generated

text: by

text: a

text: one-

text: θ

text: component

text: inner

text: function

text: θ.

text: Our

text: main

text: result

text: is

text: the

text: following

text: formula:

text: BMO(σ

text: θ

text: α

text: where

text: σ

text: denotes

text: the

text: Clark

text: measure

text: of

text: the

text: inner

text: function

text: θ.

text: Below

text: we

text: state

text: α

text: this

text: result

text: formally

text: and

text: apply

text: it

text: to

text: the

text: boundedness

text: problem

text: for

text: truncated

text: Hankel

text: operators.

text: Mathematics

text: Subject

text: Classiﬁcation.

text: Primary

text: Key

text: words

text: and

text: phrases.

text: Inner

text: function,

text: Clark

text: measure,

text: discrete

text: Hilbert

text: transform,

text: bounded

text: mean

text: oscillation,

text: atomic

text: Hardy

text: space,

text: truncated

text: Hankel

text: operators.

text: This

text: work

text: is

text: partially

text: supported

text: by

text: RFBR

text: grants

text: by

text: ISF

text: grant

text: by

text: JSC

text: “Gazprom

text: Neft”,

text: and

text: by

text: the

text: Chebyshev

text: Laboratory

text: (Department

text: of

text: Mathematics

text: and

text: Mechanics,

text: St.

text: Petersburg

text: State

text: University)

text: under

text: RF

text: Government

text: grant

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##