text: Kuba [13] considered non-monic polynomials and proved the following theorem, which we have rephrased in terms of a ratio of probabilities to show its connection with Heuristic 1.1. − · · · Theorem 3.2 (Kuba [13]). Let h (x) = a xd + a − xd 1 + + a be a polynomial with degree K,d d d 1 0 − d > 2, where the a are chosen uniformly and independently from integers in the interval [ K, K], i and a is nonzero. Then, d Pr(h (x) is reducible) ≤ ≥ K,d C , for every K 1, 1 d 2K+1 where C is a constant depending only on d. (Note that the left-hand side of the inequality above is d always at least 1.) Our computer data indicates that the probability that h (x) is reducible divided by 1 K,d 2K+1 decreases to 1 as d goes to inﬁnity; see Figure 7. Data with higher degree (we also tested d = 80, 90, 100, 200) further suggests that this ratio goes to 1. (cid:0) (cid:1) One natural, non-uniform way to choose coeﬃcients in the interval [0, K] is to use a binomial ≤ ≤ distribution, Bin(K, p), where K is a positive integer and 0 p 1, so that the value (cid:96) is taken − − with probability K p(cid:96)(1 p)K (cid:96). Heuristic 1.1 is easiest to understand when the probability of (cid:96) a linear factor is dominated by the probability that the constant coeﬃcient is zero, and thus we − let p = 1/K, in which case the constant coeﬃcient is zero with probability (1 1/K)K, which − is close to e 1 especially as K increases. Interestingly, this binomial model has features similar to 0,1 polynomials, in that each coeﬃcient takes the value zero with roughly constant probability as K increases, while still having the support of the coeﬃcients tend to inﬁnity as K increases (the binomial distribution approximates a Poisson distribution as K increases). Data in Figure 8 suggests that Heuristic 1.1 still holds, and we make the following conjecture. − · · · Conjecture 3.3. For a random monic polynomial h (x) = xd + a − xd 1 + + a x + a Bin,K,d d 1 1 0 with coeﬃcients a , . . . , a − chosen from the interval [0, K] using a Bin(K, 1/K) distribution, the 0 d 1 probability that the polynomial is reducible divided by the probability that the constant coeﬃcient is zero goes to 1 as K goes to inﬁnity. ± 4. Characteristic polynomial of a random 1 matrix. We consider the probability of reducibility for χ(x), the characteristic polynomial of a d by d matrix with integer entries. This case is diﬀerent than the previous two sections because both the degree of the characteristic polynomial and the support of the coeﬃcients grow as d increases. We − study the case where the d by d matrix has entries that are +1 or 1 independently with probability 1. Some results are known for other models of random matrices. In [20], Rivin studies random 2 Z integer matrices formed as products of random elements in the special linear group SL(n, ), where Z the random elements are chosen in two ways: either uniformly over all matrices in SL(n, ) with coeﬃcients uniformly bounded by a constant, or in terms of word length based on a ﬁxed generating Z set for SL(n, ). Rivin [20] shows that the probability that the characteristic polynomial is reducible Z tends to 0 in both cases as n increases, and also studies Sp(n, ) (see further extensions in [7]). − In the case where the d by d matrix has entries that are +1 or 1 independently with probability 1, Figure 9 indicates that the probability of reducibility decreases as d increases, and the probability 2 9 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: Kuba

text: considered

text: non-monic

text: polynomials

text: and

text: proved

text: the

text: following

text: theorem,

text: which

text: we

text: have

text: rephrased

text: in

text: terms

text: of

text: a

text: ratio

text: of

text: probabilities

text: to

text: show

text: its

text: connection

text: with

text: Heuristic

text: Theorem

text: (Kuba

text: Let

text: h

text: (x)

text: a

text: xd

text: a

text: xd

text: a

text: be

text: a

text: polynomial

text: with

text: degree

text: K,d

text: d

text: d

text: d

text: where

text: the

text: a

text: are

text: chosen

text: uniformly

text: and

text: independently

text: from

text: integers

text: in

text: the

text: interval

text: K,

text: K],

text: i

text: and

text: a

text: is

text: nonzero.

text: Then,

text: d

text: Pr(h

text: (x)

text: is

text: reducible)

text: K,d

text: C

text: for

text: every

text: K

text: d

text: where

text: C

text: is

text: a

text: constant

text: depending

text: only

text: on

text: d.

text: (Note

text: that

text: the

text: left-hand

text: side

text: of

text: the

text: inequality

text: above

text: is

text: d

text: always

text: at

text: least

text: Our

text: computer

text: data

text: indicates

text: that

text: the

text: probability

text: that

text: h

text: (x)

text: is

text: reducible

text: divided

text: by

text: K,d

text: decreases

text: to

text: as

text: d

text: goes

text: to

text: inﬁnity;

text: see

text: Figure

text: Data

text: with

text: higher

text: degree

text: (we

text: also

text: tested

text: d

text: further

text: suggests

text: that

text: this

text: ratio

text: goes

text: to

text: One

text: natural,

text: non-uniform

text: way

text: to

text: choose

text: coeﬃcients

text: in

text: the

text: interval

text: K]

text: is

text: to

text: use

text: a

text: binomial

text: distribution,

text: Bin(K,

text: p),

text: where

text: K

text: is

text: a

text: positive

text: integer

text: and

text: p

text: so

text: that

text: the

text: value

text: is

text: taken

text: with

text: probability

text: K

text: p)K

text: Heuristic

text: is

text: easiest

text: to

text: understand

text: when

text: the

text: probability

text: of

text: a

text: linear

text: factor

text: is

text: dominated

text: by

text: the

text: probability

text: that

text: the

text: constant

text: coeﬃcient

text: is

text: zero,

text: and

text: thus

text: we

text: let

text: p

text: in

text: which

text: case

text: the

text: constant

text: coeﬃcient

text: is

text: zero

text: with

text: probability

text: which

text: is

text: close

text: to

text: e

text: especially

text: as

text: K

text: increases.

text: Interestingly,

text: this

text: binomial

text: model

text: has

text: features

text: similar

text: to

text: polynomials,

text: in

text: that

text: each

text: coeﬃcient

text: takes

text: the

text: value

text: zero

text: with

text: roughly

text: constant

text: probability

text: as

text: K

text: increases,

text: while

text: still

text: having

text: the

text: support

text: of

text: the

text: coeﬃcients

text: tend

text: to

text: inﬁnity

text: as

text: K

text: increases

text: (the

text: binomial

text: distribution

text: approximates

text: a

text: Poisson

text: distribution

text: as

text: K

text: increases).

text: Data

text: in

text: Figure

text: suggests

text: that

text: Heuristic

text: still

text: holds,

text: and

text: we

text: make

text: the

text: following

text: conjecture.

text: Conjecture

text: For

text: a

text: random

text: monic

text: polynomial

text: h

text: (x)

text: xd

text: a

text: xd

text: a

text: x

text: a

text: Bin,K,d

text: d

text: with

text: coeﬃcients

text: a

text: a

text: chosen

text: from

text: the

text: interval

text: K]

text: using

text: a

text: Bin(K,

text: distribution,

text: the

text: d

text: probability

text: that

text: the

text: polynomial

text: is

text: reducible

text: divided

text: by

text: the

text: probability

text: that

text: the

text: constant

text: coeﬃcient

text: is

text: zero

text: goes

text: to

text: as

text: K

text: goes

text: to

text: inﬁnity.

text: Characteristic

text: polynomial

text: of

text: a

text: random

text: matrix.

text: We

text: consider

text: the

text: probability

text: of

text: reducibility

text: for

text: χ(x),

text: the

text: characteristic

text: polynomial

text: of

text: a

text: d

text: by

text: d

text: matrix

text: with

text: integer

text: entries.

text: This

text: case

text: is

text: diﬀerent

text: than

text: the

text: previous

text: two

text: sections

text: because

text: both

text: the

text: degree

text: of

text: the

text: characteristic

text: polynomial

text: and

text: the

text: support

text: of

text: the

text: coeﬃcients

text: grow

text: as

text: d

text: increases.

text: We

text: study

text: the

text: case

text: where

text: the

text: d

text: by

text: d

text: matrix

text: has

text: entries

text: that

text: are

text: or

text: independently

text: with

text: probability

text: Some

text: results

text: are

text: known

text: for

text: other

text: models

text: of

text: random

text: matrices.

text: In

text: Rivin

text: studies

text: random

text: Z

text: integer

text: matrices

text: formed

text: as

text: products

text: of

text: random

text: elements

text: in

text: the

text: special

text: linear

text: group

text: SL(n,

text: where

text: Z

text: the

text: random

text: elements

text: are

text: chosen

text: in

text: two

text: ways:

text: either

text: uniformly

text: over

text: all

text: matrices

text: in

text: SL(n,

text: with

text: coeﬃcients

text: uniformly

text: bounded

text: by

text: a

text: constant,

text: or

text: in

text: terms

text: of

text: word

text: length

text: based

text: on

text: a

text: ﬁxed

text: generating

text: Z

text: set

text: for

text: SL(n,

text: Rivin

text: shows

text: that

text: the

text: probability

text: that

text: the

text: characteristic

text: polynomial

text: is

text: reducible

text: Z

text: tends

text: to

text: in

text: both

text: cases

text: as

text: n

text: increases,

text: and

text: also

text: studies

text: Sp(n,

text: (see

text: further

text: extensions

text: in

text: In

text: the

text: case

text: where

text: the

text: d

text: by

text: d

text: matrix

text: has

text: entries

text: that

text: are

text: or

text: independently

text: with

text: probability

text: Figure

text: indicates

text: that

text: the

text: probability

text: of

text: reducibility

text: decreases

text: as

text: d

text: increases,

text: and

text: the

text: probability

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: Figure 8. Let h (x) be a monic random polynomial with all other coeﬃcients Bin,K,d { } chosen independently from 0, 1, . . . , K using a Bin(K, 1/K) distribution. The plot shows the probability that h (x) is reducible divided by the probability that the Bin,K constant coeﬃcient is zero for degrees d = 3 to d = 15 and K equal to 10, 30, and 50. Note that the ratio appears to tend to 1 as the degree increases, supporting Heuristic 1.1 (see Conjecture 3.3). For the data points for K = 10, 30, and 50, the ± ± ± 99.9999% conﬁdence intervals are 0.0017, 0.0006 and 0.0004, respectively. of reducibility appears to become close to a lower bound derived from the probability that the matrix has a pair or rows or columns that are dependent (this implies that the constant coeﬃcient, which is the determinant of the matrix, is zero). It has long been conjectured (see, for example, ± [9, 8, 22, 23, 3, 1]) that the probabi(cid:18)lity(cid:19)t(cid:18)hat(cid:19)a uni(cid:18)form rand(cid:19)om d by d matrix with 1 entries has determinant zero is asymptotically d 1 d 1 d (cid:0) (cid:1) (cid:0) (cid:1) (2) 4 = + o(1) , 2 2 2 where o(1) is a small quantity tending to zero as d tends to inﬁnity. The term 4 d 1 d is an 2 2 asymptotic lower bound coming from the probability that there is a pair of rows or columns that are dependent. Figure 9 uses a diﬀerent asymptotic lower bound (see Proposition 5.4) that is similar but more accurate for small d. Based on our data we make the following conjecture, which implies the bound in (2) and also supports Heuristic 1.1. Conjecture 4.1. If χ(x) is the characteristic polynomial of a d by d random matrix, where each − entry is +1 or 1 independently with probabil(cid:0)ity(cid:1) (cid:0)1/(cid:1)2, then Pr(χ(x) is reducible) lim = 1. d→∞ 4 d 1 d 2 2 5. Propositions and proofs In this section we collect lower bounds on the probability of a linear factor in given polynomial models using combinatorics. We use the notation o(1) to signify a small function which tends to 0 as d tends to inﬁnity. 10 ##LTFigure## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: Figure

label: paragraph

text: Let

label: caption

text: h

text: (x)

text: be

text: a

text: monic

text: random

text: polynomial

text: with

text: all

text: other

text: coeﬃcients

text: Bin,K,d

text: chosen

text: independently

text: from

text: K

text: using

text: a

text: Bin(K,

text: distribution.

text: The

text: plot

text: shows

text: the

text: probability

text: that

text: h

text: (x)

text: is

text: reducible

text: divided

text: by

text: the

text: probability

text: that

text: the

text: Bin,K

text: constant

text: coeﬃcient

text: is

text: zero

text: for

text: degrees

text: d

text: to

text: d

text: and

text: K

text: equal

text: to

text: and

text: Note

text: that

text: the

text: ratio

text: appears

text: to

text: tend

text: to

text: as

text: the

text: degree

text: increases,

text: supporting

text: Heuristic

text: (see

text: Conjecture

text: For

text: the

text: data

text: points

text: for

text: K

text: and

text: the

text: conﬁdence

text: intervals

text: are

text: and

text: respectively.

text: of

text: reducibility

text: appears

text: to

text: become

text: close

text: to

text: a

text: lower

text: bound

text: derived

text: from

text: the

text: probability

text: that

text: the

text: matrix

text: has

text: a

text: pair

text: or

text: rows

text: or

text: columns

text: that

text: are

text: dependent

text: (this

text: implies

text: that

text: the

text: constant

text: coeﬃcient,

text: which

text: is

text: the

text: determinant

text: of

text: the

text: matrix,

text: is

text: zero).

text: It

text: has

text: long

text: been

text: conjectured

text: (see,

text: for

text: example,

text: that

text: the

text: d

text: by

text: d

text: matrix

text: with

text: entries

text: has

text: determinant

text: zero

text: is

text: asymptotically

text: d

text: d

text: d

text: where

text: is

text: a

text: small

text: quantity

text: tending

text: to

text: zero

text: as

text: d

text: tends

text: to

text: inﬁnity.

text: The

text: term

text: d

text: d

text: is

text: an

text: asymptotic

text: lower

text: bound

text: coming

text: from

text: the

text: probability

text: that

text: there

text: is

text: a

text: pair

text: of

text: rows

text: or

text: columns

text: that

text: are

text: dependent.

text: Figure

text: uses

text: a

text: diﬀerent

text: asymptotic

text: lower

text: bound

text: (see

text: Proposition

text: that

text: is

text: similar

text: but

text: more

text: accurate

text: for

text: small

text: d.

text: Based

text: on

text: our

text: data

text: we

text: make

text: the

text: following

text: conjecture,

text: which

text: implies

text: the

text: bound

text: in

text: and

text: also

text: supports

text: Heuristic

text: Conjecture

text: If

text: χ(x)

text: is

text: the

text: characteristic

text: polynomial

text: of

text: a

text: d

text: by

text: d

text: random

text: matrix,

text: where

text: each

text: entry

text: is

text: or

text: independently

text: with

text: then

text: Pr(χ(x)

text: is

text: reducible)

text: lim

text: d→∞

text: d

text: d

text: Propositions

text: and

text: proofs

text: In

text: this

text: section

text: we

text: collect

text: lower

text: bounds

text: on

text: the

text: probability

text: of

text: a

text: linear

text: factor

text: in

text: given

text: polynomial

text: models

text: using

text: combinatorics.

text: We

text: use

text: the

text: notation

text: to

text: signify

text: a

text: small

text: function

text: which

text: tends

text: to

text: as

text: d

text: tends

text: to

text: inﬁnity.

text: ##LTFigure##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: 12 KANG LI1 AND HU(cid:91)NG-CHANG LIAO2 Deﬁne ∞ Y := Y n n=0 and → ∈ f : X Y, f(x) := f (x) (x X ). n n By condition (1) the map f is well-deﬁned. Since each f is a bijection, so is f. It is easy n to check, using condition (3) and the fact that X (and Y ) have asymptotic dimension zero, (cid:3) that f is a coarse equivalence. (cid:32) (cid:33) { }∞ Proposition 4.5. Let Γ be a countable locally ﬁnite group and let (Γ, Γ , d) be as in (cid:89) | | n n=0 Lemma 3.5. For each n = 0, 1, 2, ..., deﬁne k = Γ and r = k /k . Then n n n n+1 n ∞ ∼ ∗ C C (Γ) = l−i→m M ( ), ϕ , u kn n i=1 where ϕ (T , T , ...) = (diag(T , ..., T ), diag(T , ..., T ), ...) . n 1 2 1 rn rn+1 2rn Proof. We saw in Theorem 3.6 that locally ﬁni(cid:76)te groups have asymptotic dimension zero. (cid:3) Now the result follows from P(cid:76)roposition 4.4 and Proposition 4.2. Z Z Esuxbagmropuples 4{.Γ6.}Wtoe cboenΓside=r thencasZe/w2Zhe.nTΓh=en(cid:32) k N =/|2Γ .| W=e2c(cid:33)nanantdakre th=e ksque/nkce o=f ﬁ2nfioter n n (cid:77)i=1 (cid:89)n n n n+1 n n = 0, 1, 2, .... Then according to the previous proposition, ∞ ∼ ∗ Z Z C Cu( /2 ) = (cid:18)l−i→m(cid:18) M(cid:19)2n(cid:18)( ), ϕn (cid:19), (cid:19) N i=1 where T 0 T 0 ϕ (T , T , T , T , ...) = 1 , 3 , ... . n 1 2 3 4 0 T 0 T 2 4 ∗ From Propositionss 4.5 and Proposition 4.1 we see that the ordered K -group of C (Γ) is ∞ N Z 0 u a (sequential) inductive limit of (cid:96) ( , ). It is not hard to see that each connecting map ϕ n (n = 0, 1, 2, ...) induces the following map at the level of K -groups: 0 ∞ N Z → ∞ N Z α : (cid:96) ( , ) (cid:96) ( , ), n · · · · · · α ((m , m , ...)) = (m + + m , m + + m , ...). n 1 2 1 rn rn+1 2rn By continuity of the K functor, we have 0 ∼ ∗ ∗ ∞ N Z ∞ N Z (K (C (Γ)), K (C (Γ))+) = l−i→m((cid:96) ( , ), (cid:96) ( , )+, α ).  0 u 0 u n  (cid:88)  To describe the inductive limit more explicitly, deﬁne   ∈ ∞ N Z (j+1)kn H(n) := (m , m , ...) (cid:96) ( , ) : m = 0 for all j = 0, 1, 2, ... Γ 1 2 i i=jkn+1

text: KANG

text: AND

text: Deﬁne

text: Y

text: Y

text: n

text: and

text: f

text: X

text: Y,

text: f(x)

text: f

text: (x)

text: (x

text: X

text: n

text: n

text: By

text: condition

text: the

text: map

text: f

text: is

text: well-deﬁned.

text: Since

text: each

text: f

text: is

text: a

text: bijection,

text: so

text: is

text: f.

text: It

text: is

text: easy

text: n

text: to

text: check,

text: using

text: condition

text: and

text: the

text: fact

text: that

text: X

text: (and

text: Y

text: have

text: asymptotic

text: dimension

text: zero,

text: that

text: f

text: is

text: a

text: coarse

text: equivalence.

text: Proposition

text: Let

text: Γ

text: be

text: a

text: countable

text: locally

text: ﬁnite

text: group

text: and

text: let

text: (Γ,

text: Γ

text: d)

text: be

text: as

text: in

text: n

text: Lemma

text: For

text: each

text: n

text: deﬁne

text: k

text: Γ

text: and

text: r

text: k

text: /k

text: Then

text: n

text: n

text: n

text: n

text: C

text: C

text: (Γ)

text: l−i→m

text: M

text: ϕ

text: u

text: kn

text: n

text: where

text: ϕ

text: (T

text: T

text: (diag(T

text: T

text: diag(T

text: T

text: n

text: rn

text: Proof.

text: We

text: saw

text: in

text: Theorem

text: that

text: locally

text: groups

text: have

text: asymptotic

text: dimension

text: zero.

text: Now

text: the

text: result

text: follows

text: from

text: and

text: Proposition

text: Z

text: Z

text: Esuxbagmropuples

text: cboenΓside=r

text: k

text: N

text: th=e

text: ksque/nkce

text: o=f

text: n

text: n

text: n

text: n

text: n

text: n

text: Then

text: according

text: to

text: the

text: previous

text: proposition,

text: Z

text: Z

text: C

text: Cu(

text: ϕn

text: N

text: where

text: T

text: T

text: ϕ

text: (T

text: T

text: T

text: T

text: n

text: T

text: T

text: From

text: Propositionss

text: and

text: Proposition

text: we

text: see

text: that

text: the

text: ordered

text: K

text: -group

text: of

text: C

text: (Γ)

text: is

text: N

text: Z

text: u

text: a

text: (sequential)

text: inductive

text: limit

text: of

text: It

text: is

text: not

text: hard

text: to

text: see

text: that

text: each

text: connecting

text: map

text: ϕ

text: n

text: (n

text: induces

text: the

text: following

text: map

text: at

text: the

text: level

text: of

text: K

text: -groups:

text: N

text: Z

text: N

text: Z

text: α

text: n

text: α

text: ((m

text: m

text: (m

text: m

text: m

text: m

text: n

text: rn

text: By

text: continuity

text: of

text: the

text: K

text: functor,

text: we

text: have

text: N

text: Z

text: N

text: Z

text: (K

text: (C

text: (Γ)),

text: K

text: (C

text: (Γ))+)

text: α

text: u

text: u

text: n

text: To

text: describe

text: the

text: inductive

text: limit

text: more

text: explicitly,

text: deﬁne

text: N

text: Z

text: H(n)

text: (m

text: m

text: m

text: for

text: all

text: j

text: Γ

text: i


text: 16 KANG LI1 AND HUNG-CHANG LIAO2 Remark 4.12. It is shown in [16, Corollary 2.21] that two countable discrete groups are ˇ bijectively coarsely equivalent if and only if their canonical actions on Stone-Cech compact- iﬁcations are continuously orbit equivalent. Since the proof of [20, Proposition 4.13] goes through without any change for ´etale Hausdorﬀ locally compact topologically principal σ- compact groupoids, it follows from [15, Theorem 1.2] that (1) and (2) are equivalent for all countable discrete groups. Remark 4.13. We would like to thank Rufus Willett for letting us know the following fact, which can be deduced from (the proof) of [28, Theorem 1.1]: if X and Y are uniformly dis- crete, bounded geometry non-amenable metric spaces, then any coarse equivalence between X and Y is close to a bijective coarse equivalence. Using this result, one deduces from the ⇒ main theorem of [26] that (3) = (1) holds for the class of non-amenable exact countable groups (cf. [26, Corollary 6.2]). Our main theorem provides a small class of amenable groups ⇒ for which (3) = (1) holds. (cid:76) (cid:76) Remark 4.14. It is known from [2, Corollary 8] that all countably inﬁnite locally ﬁnite groups are coarsely equivalent. Thus, there are many coarsely equivalent locally ﬁnite groups ∗ Z (cid:29) ∗ Z with non-isomorphic uniform Roe algebras. For instance, Cu( N 2) Cu( N 3) (see Theorem 3.10). In fact, two countable direct sums of ﬁnite prime cyclic groups are bijectively coarsely equivalent if and only if they are isomorphic as groups (see [5, Corollary 5.6]). We refer the reader to [17, Section 6] for relevant discussions. Remark 4.15. It is shown by Rufus Willett and the ﬁrst named author in [14, Corollary 1.7] ∗ that K (C (Γ)) = 0 for every non-amenable countable group Γ with asymptotic dimension 0 u one. Hence, we cannot expect Theorem 4.11 to hold for general countable groups with asymptotic dimension one. For instance, let us consider the free group F on n generators Z (cid:111) n and the wreath product group F , which is also ﬁnitely generated. Since they are 2 n non-amenable countable groups with asymptotic dimension one, their uniform Roe algebras have trivial K groups. However, they are not coarsely equivalent (or equivalently, they 0 are not quasi-isometric) as being ﬁnitely presented is invariant under quasi-isometries [9, Z (cid:111) Proposition V.4] and F is not ﬁnitely presented (see [3, Theorem 1]). 2 n Question 4.16. Does Theorem 4.11 hold for all bounded geometry metric spaces with as- ymptotic dimension zero? It follows from [2, Section 11] that Theorem 4.11 holds for all bounded geometry iso- metrically homogeneous metric spaces with asymptotic dimension zero. Recall that a metric ∈ space X is called isometrically homogeneous if for any two points x, y X there is a bijective → isometry f : X X such that f(x) = y. As a side note, it follows from [5, Corollary 6.4] and Proposition 4.4 that there are un- Z countably many coarsely inequivalent asymptotically 0-dimensional subspaces of ≥ . On 0 the other hand, there are only two coarsely equivalent classes of countable locally ﬁnite groups (cf. Remark 3.11).

text: KANG

text: AND

text: HUNG-CHANG

text: Remark

text: It

text: is

text: shown

text: in

text: Corollary

text: that

text: two

text: countable

text: discrete

text: groups

text: are

text: ˇ

text: bijectively

text: coarsely

text: equivalent

text: if

text: and

text: only

text: if

text: their

text: canonical

text: actions

text: on

text: Stone-Cech

text: compact-

text: iﬁcations

text: are

text: continuously

text: orbit

text: equivalent.

text: Since

text: the

text: proof

text: of

text: Proposition

text: goes

text: through

text: without

text: any

text: change

text: for

text: ´etale

text: Hausdorﬀ

text: locally

text: compact

text: topologically

text: principal

text: σ-

text: compact

text: groupoids,

text: it

text: follows

text: from

text: Theorem

text: that

text: and

text: are

text: equivalent

text: for

text: all

text: countable

text: discrete

text: groups.

text: Remark

text: We

text: would

text: like

text: to

text: thank

text: Rufus

text: Willett

text: for

text: letting

text: us

text: know

text: the

text: following

text: fact,

text: which

text: can

text: be

text: deduced

text: from

text: (the

text: proof)

text: of

text: Theorem

text: if

text: X

text: and

text: Y

text: are

text: uniformly

text: dis-

text: crete,

text: bounded

text: geometry

text: non-amenable

text: metric

text: spaces,

text: then

text: any

text: coarse

text: equivalence

text: between

text: X

text: and

text: Y

text: is

text: close

text: to

text: a

text: bijective

text: coarse

text: equivalence.

text: Using

text: this

text: result,

text: one

text: deduces

text: from

text: the

text: main

text: theorem

text: of

text: that

text: holds

text: for

text: the

text: class

text: of

text: non-amenable

text: exact

text: countable

text: groups

text: (cf.

text: Corollary

text: Our

text: main

text: theorem

text: provides

text: a

text: small

text: class

text: of

text: amenable

text: groups

text: for

text: which

text: holds.

text: Remark

text: It

text: is

text: known

text: from

text: Corollary

text: that

text: all

text: countably

text: inﬁnite

text: locally

text: ﬁnite

text: groups

text: are

text: coarsely

text: equivalent.

text: Thus,

text: there

text: are

text: many

text: coarsely

text: equivalent

text: locally

text: ﬁnite

text: groups

text: Z

text: Z

text: with

text: non-isomorphic

text: uniform

text: Roe

text: algebras.

text: For

text: instance,

text: Cu(

text: N

text: Cu(

text: N

text: (see

text: Theorem

text: In

text: fact,

text: two

text: countable

text: direct

text: sums

text: of

text: ﬁnite

text: prime

text: cyclic

text: groups

text: are

text: bijectively

text: coarsely

text: equivalent

text: if

text: and

text: only

text: if

text: they

text: are

text: isomorphic

text: as

text: groups

text: (see

text: Corollary

text: We

text: refer

text: the

text: reader

text: to

text: Section

text: for

text: relevant

text: discussions.

text: Remark

text: It

text: is

text: shown

text: by

text: Rufus

text: Willett

text: and

text: the

text: ﬁrst

text: named

text: author

text: in

text: Corollary

text: that

text: K

text: (C

text: (Γ))

text: for

text: every

text: non-amenable

text: countable

text: group

text: Γ

text: with

text: asymptotic

text: dimension

text: u

text: one.

text: Hence,

text: we

text: cannot

text: expect

text: Theorem

text: to

text: hold

text: for

text: general

text: countable

text: groups

text: with

text: asymptotic

text: dimension

text: one.

text: For

text: instance,

text: let

text: us

text: consider

text: the

text: free

text: group

text: F

text: on

text: n

text: generators

text: Z

text: n

text: and

text: the

text: wreath

text: product

text: group

text: F

text: which

text: is

text: also

text: ﬁnitely

text: generated.

text: Since

text: they

text: are

text: n

text: non-amenable

text: countable

text: groups

text: with

text: asymptotic

text: dimension

text: one,

text: their

text: uniform

text: Roe

text: algebras

text: have

text: trivial

text: K

text: groups.

text: However,

text: they

text: are

text: not

text: coarsely

text: equivalent

text: (or

text: equivalently,

text: they

text: are

text: not

text: quasi-isometric)

text: as

text: being

text: ﬁnitely

text: presented

text: is

text: invariant

text: under

text: quasi-isometries

text: Z

text: Proposition

text: and

text: F

text: is

text: not

text: ﬁnitely

text: presented

text: (see

text: Theorem

text: n

text: Question

text: Does

text: Theorem

text: hold

text: for

text: all

text: bounded

text: geometry

text: metric

text: spaces

text: with

text: as-

text: ymptotic

text: dimension

text: zero?

text: It

text: follows

text: from

text: Section

text: that

text: Theorem

text: holds

text: for

text: all

text: bounded

text: geometry

text: iso-

text: metrically

text: homogeneous

text: metric

text: spaces

text: with

text: asymptotic

text: dimension

text: zero.

text: Recall

text: that

text: a

text: metric

text: space

text: X

text: is

text: called

text: isometrically

text: homogeneous

text: if

text: for

text: any

text: two

text: points

text: x,

text: y

text: X

text: there

text: is

text: a

text: bijective

text: isometry

text: f

text: X

text: X

text: such

text: that

text: f(x)

text: y.

text: As

text: a

text: side

text: note,

text: it

text: follows

text: from

text: Corollary

text: and

text: Proposition

text: that

text: there

text: are

text: un-

text: Z

text: countably

text: many

text: coarsely

text: inequivalent

text: asymptotically

text: subspaces

text: of

text: On

text: the

text: other

text: hand,

text: there

text: are

text: only

text: two

text: coarsely

text: equivalent

text: classes

text: of

text: countable

text: locally

text: ﬁnite

text: groups

text: (cf.

text: Remark


text: 2 SUSANNA TERRACINI, GIORGIO TORTONE, AND STEFANO VITA ∫ Here we deﬁne (see § for the details) ( ) − ( ) (− ) ( ) ( ) u x u η ∆ su x = C n, s P.V. | − | dη , Rn x η n+2s where u is a suﬃciently smooth function and ( ) ( ) 22ssΓ n + s (1.2) C n, s = π∫n/2Γ(12 − s) > 0, where ∞ ( ) − − Γ x = tx 1e tdt. 0 The principal value is taken at η = x: hence, though u needs not to decay at inﬁnity, it has to keep an algebraic growth with a power strictly smaller than 2s in o(cid:18)rde(cid:19)r to make the above expression meaningful. By Theorem 3.2 in [4], it is known that there exists a homogeneous, nonnegative and nontrivial solution to (1.1) of the form ( ) | | x u x = x γsu | | , s s x ( ) where γ := γ C is a deﬁnite homogeneity degree (characteristic exponent), which depends on the cone. s s Moreover, such a solution is continuous in Rn and unique, up to multiplicative constants. We can normalize (cid:107) (cid:107) it in such a way that us L∞(Sn−1) = 1. We consider the case when s approaches 1, wondering whether solutions of the problem do converge to a harmonic function in the same cone and, in case, which are the suitable spaces for convergence. Such conic s-harmonic functions appear as limiting blow-up proﬁles and play a major role in many free boundary problems with fractional diﬀusions and in the study of the geometry of nodal sets, also in the case of partition problems (see, e.g. [1, 5, 9, 20, 22]). Moreover, as we shall see later, they are strongly involved with the possible extensions of the Alt-Caﬀarelli-Friedman monotonicity formula to the case of fractional diﬀusion. The study of their properties and, ultimately, their classiﬁcation is therefore a major achievement in this setting. The problem of homogeneous s-harmonic functions on cones has been deeply studied in (cid:37) [4, 6, 7, 23]. The present paper mainly focuses on the limiting behaviour as s 1. Our problem (1.1) can be linked to a speciﬁc spectral problem of local nature in the upper half sphere; indeed let us look at the extension technique popularized by Caﬀarelli and Silvestre (see [11]), characterizing the fractional Laplacian in Rn a(cid:40)s the Dirichlet-to-Neumann map for a variable v depending on one more space dimension and satisfying: ( − ∇ ) L v = div y1 2s v = 0 in Rn+1, (1.3) (s ) ( ) + ∫ v x,0 = u x on Rn . ∫ Such an extension exists unique for a suitable class of functions u (see (2.1)) and it is given by the formula: ( ) v(x, y) = γ(n, s) (| − y|2su η ) / dη where γ(n, s)−1 := (| | 1 ) / dη . Rn x η 2 + y2 n 2+s Rn η 2 + 1 n 2+s ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

font: MFPZLZ+TeXGyreTermes-Regular

text: SUSANNA

text: TERRACINI,

text: GIORGIO

text: TORTONE,

text: AND

text: STEFANO

text: VITA

font: KUTBYC+txexs

text: Here

text: we

text: deﬁne

text: (see

text: for

text: the

text: details)

font: DTJOWG+txsys

text: u

text: x

text: u

text: η

font: ZOGNYE+rtxmi

font: VKXFRE+txmia

text: su

text: x

font: NPRKBQ+rtxr

text: C

text: n,

text: s

text: P.V.

text: dη

text: Rn

font: JESRHI+txsyb

text: x

text: η

text: where

text: u

text: is

text: a

text: suﬃciently

text: smooth

text: function

text: and

text: n

text: s

text: C

text: n,

text: s

text: s)

text: where

text: Γ

text: x

text: tx

text: tdt.

text: The

text: principal

text: value

text: is

text: taken

text: at

text: η

text: x:

text: hence,

text: though

text: u

text: needs

text: not

text: to

text: decay

text: at

text: inﬁnity,

text: it

text: has

text: to

text: keep

text: an

text: algebraic

text: growth

text: with

text: a

text: power

text: strictly

text: smaller

text: than

text: in

text: to

text: make

text: the

text: above

text: expression

text: meaningful.

text: By

text: Theorem

text: in

text: it

text: is

text: known

text: that

text: there

text: exists

text: a

text: homogeneous,

text: nonnegative

text: and

text: nontrivial

text: solution

text: to

text: of

text: the

text: form

text: x

text: u

text: x

text: x

text: γsu

text: s

text: s

text: x

text: where

text: γ

text: γ

text: C

text: is

text: a

text: deﬁnite

text: homogeneity

text: degree

text: (characteristic

text: exponent),

text: which

text: depends

text: on

text: the

text: cone.

text: s

text: s

text: Moreover,

text: such

text: a

text: solution

text: is

text: continuous

text: in

text: Rn

text: and

text: unique,

text: up

text: to

text: multiplicative

text: constants.

text: We

text: can

text: normalize

text: it

text: in

text: such

text: a

text: way

text: that

text: us

text: We

text: consider

text: the

text: case

text: when

text: s

text: approaches

text: wondering

text: whether

text: solutions

text: of

text: the

text: problem

text: do

text: converge

text: to

text: a

text: harmonic

text: function

text: in

text: the

text: same

text: cone

text: and,

text: in

text: case,

text: which

text: are

text: the

text: suitable

text: spaces

text: for

text: convergence.

text: Such

text: conic

text: s-harmonic

text: functions

text: appear

text: as

text: limiting

text: blow-up

text: proﬁles

text: and

text: play

text: a

text: major

text: role

text: in

text: many

text: free

text: boundary

text: problems

text: with

text: fractional

text: diﬀusions

text: and

text: in

text: the

text: study

text: of

text: the

text: geometry

text: of

text: nodal

text: sets,

text: also

text: in

text: the

text: case

text: of

text: partition

text: problems

text: (see,

text: e.g.

text: Moreover,

text: as

text: we

text: shall

text: see

text: later,

text: they

text: are

text: strongly

text: involved

text: with

text: the

text: possible

text: extensions

text: of

text: the

text: Alt-Caﬀarelli-Friedman

text: monotonicity

text: formula

text: to

text: the

text: case

text: of

text: fractional

text: diﬀusion.

text: The

text: study

text: of

text: their

text: properties

text: and,

text: ultimately,

text: their

text: classiﬁcation

text: is

text: therefore

text: a

text: major

text: achievement

text: in

text: this

text: setting.

text: The

text: problem

text: of

text: homogeneous

text: s-harmonic

text: functions

text: on

text: cones

text: has

text: been

text: deeply

text: studied

text: in

text: The

text: present

text: paper

text: mainly

text: focuses

text: on

text: the

text: limiting

text: behaviour

text: as

text: s

text: Our

text: problem

text: can

text: be

text: linked

text: to

text: a

text: speciﬁc

text: spectral

text: problem

text: of

text: local

text: nature

text: in

text: the

text: upper

text: half

text: sphere;

text: indeed

text: let

text: us

text: look

text: at

text: the

text: extension

text: technique

text: popularized

text: by

text: Caﬀarelli

text: and

text: Silvestre

text: (see

text: characterizing

text: the

text: fractional

text: Laplacian

text: in

text: Rn

text: the

text: Dirichlet-to-Neumann

text: map

text: for

text: a

text: variable

text: v

text: depending

text: on

text: one

text: more

text: space

text: dimension

text: and

text: satisfying:

text: L

text: v

text: div

text: v

text: in

text: (s

text: v

text: u

text: x

text: on

text: Rn

text: Such

text: an

text: extension

text: exists

text: unique

text: for

text: a

text: suitable

text: class

text: of

text: functions

text: u

text: (see

text: and

text: it

text: is

text: given

text: by

text: the

text: formula:

text: v(x,

text: y)

text: γ(n,

text: s)

text: η

text: dη

text: where

text: γ(n,

text: dη

text: Rn

text: x

text: η

text: n

text: Rn

text: η

text: n

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: ON s-HARMONIC FUNCTIONS ON CONES 29 ∫ where we can use that ˜ solves v − ∫ ∆v˜ = 2nv˜ + µ0 (cid:20)∫vdσ − ∩ Sn−1 in the enlarged cap Sn 1 C . Finally, θ+ε (| | − | | )( ( ) − ( )) ∫ ( − | | )( ( ) − ( (cid:21))) ( ) x γ y γ v x v y ( ) 1 y γ v x v y C n, s | − | dy =C n, s | − | dy+ Rn x y n+2s (|y|<−1| | )( (x ) −y n(+2)s) 1 y γ v x v y ∫ ∫ ∫ + |y|>1 ∫ |x − y|n+2s dy ( ) where the ﬁrst term is o 1 since 1 (1 − ργ)ρn−1 |v(−x) − v| (y) dσdρ = ∫1 (1 − ργ)ρn−1 ∫ (v(x) − v(y))(1 + o(ρ))dσdρ 0 Sn−1 x ρy n+2s 0 Sn−1 R ( − ) − ( ( ) − ( ))( ) (cid:104) (cid:105) ∫ + ∫ 1 ργ ρn 1 v x v y n + 2s ρ x, y dσdρ. 0 Sn−1 Hence, we obtain (| | − | | )( ( ) − ( )) (∫ − | | )( ( ) − ( )) ( ) x γ y γ v x v y ( ) 1 y γ v x v y ( ) C n, s | − | dy =C n, s | − | dy + o 1 Rn x y n+2s |y|>1 ∫ x| | y( n∫(+2)s− ( )) ( ) − ( ) y γ v x v y ( ) =o 1 C n, s | − | dy + o 1 ∫|y∞|>1 x ∫y n+2s( ) − ( ) =o(1) − C(n, s) ργρn−1 |v −x v| y dσdρ ∫ 1 ∞ ∫ Sn−1 x ρy n+2s ( ) − ( ) − − ( ( ) − ( ))( ( − )) =o 1 C n, s ρ 1+γ 2s v x v y 1 + o ρ 1 dσdρ+ ∞ 1 Sn−1 ∫ − ( ) − − ( ( ) − ( ))( )(cid:104) (cid:105) − C n, s ρ 1+γ 2s v x v y n + 2s y, x ρ 1dσdρ ( 1 ) Sn−(1 ) (cid:18) =o(1) − C(cid:19)2n∫,ss−ωγn−1 v(x) + C2sn−, sγ Sn−1 v(y)dσ. ∗( ) ∈ − ∩ Hence, recalling that γ = γ θ , for x Sn 1 C we have (cid:18) (s ) (cid:19) ∫ ( )θ ( ) (−∆)svs(x) ≤ µ0(θ)C4nn(,1s (−ωns−))1 − 2sC−nγ,s∗s(θ) Sn−1 vsdσ + C4nn(,1s −ωns−)1 (n + γs∗(θ))(2 − γs∗(θ))vs ≤ ( ) − C n, s ( ) ( ) µ0 θ 2s − γs∗(θ) ∗(Sn)−1 vsdσ→+ o 1 where o 1 is uniform with respect to γ θ as s 1. In order to obtain a negative right hand side, it is ∗( ) s − ∗( ) suﬃcient to choose γ θ < 2s in such a way to make the denominator 2s γ θ small enough and the ( ) s s quotient C−n∗,s( ) still bounded. (cid:3) 2s γs θ The previous result suggestes the following choice of the homogeneity exponent ( ) ∗( ) − C n, s γ θ := 2s s ( ) . s µ0 θ We can ﬁnally prove the main result of this section. ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: ON

text: s-HARMONIC

text: FUNCTIONS

text: ON

text: CONES

text: where

text: we

text: can

text: use

text: that

text: solves

text: v

font: RFSLDM+rntxmi

text: ∆v˜

text: µ0

text: in

text: the

text: enlarged

text: cap

text: Sn

text: C

text: Finally,

text: θ+ε

text: x

text: γ

text: y

text: γ

text: v

text: x

text: v

text: y

text: y

text: γ

text: v

text: x

text: v

text: y

text: C

text: n,

text: s

text: dy

text: =C

text: n,

text: s

text: dy+

text: Rn

text: x

text: y

text: (x

text: −y

text: y

text: γ

text: v

text: x

text: v

text: y

text: |x

text: dy

text: where

text: the

text: ﬁrst

text: term

text: is

text: o

text: since

text: ργ)ρn−1

text: |v(−x)

text: v|

text: (y)

text: dσdρ

text: ∫1

text: ργ)ρn−1

text: (v(x)

text: o(ρ))dσdρ

text: x

text: ρy

text: R

text: ργ

text: ρn

text: v

text: x

text: v

text: y

text: n

text: ρ

text: x,

text: y

text: dσdρ.

text: Hence,

text: we

text: obtain

text: x

text: γ

text: y

text: γ

text: v

text: x

text: v

text: y

text: y

text: γ

text: v

text: x

text: v

text: y

text: C

text: n,

text: s

text: dy

text: =C

text: n,

text: s

text: dy

text: o

text: Rn

text: x

text: y

text: x|

text: y(

text: y

text: γ

text: v

text: x

text: v

text: y

text: =o

text: C

text: n,

text: s

text: dy

text: o

text: x

text: ∫y

text: C(n,

text: s)

text: ργρn−1

text: |v

text: −x

text: v|

text: y

text: dσdρ

text: x

text: ρy

text: =o

text: C

text: n,

text: s

text: ρ

text: v

text: x

text: v

text: y

text: o

text: ρ

text: dσdρ+

text: C

text: n,

text: s

text: ρ

text: v

text: x

text: v

text: y

text: n

text: y,

text: x

text: ρ

text: v(x)

text: sγ

text: v(y)dσ.

text: Hence,

text: recalling

text: that

text: γ

text: γ

text: θ

text: for

text: x

text: Sn

text: C

text: we

text: have

text: (s

text: )θ

text: (−∆)svs(x)

text: vsdσ

text: (n

text: γs∗(θ))vs

text: C

text: n,

text: s

text: µ0

text: θ

text: γs∗(θ)

text: vsdσ→+

text: o

text: where

text: o

text: is

text: uniform

text: with

text: respect

text: to

text: γ

text: θ

text: as

text: s

text: In

text: order

text: to

text: obtain

text: a

text: negative

text: right

text: hand

text: side,

text: it

text: is

text: s

text: suﬃcient

text: to

text: choose

text: γ

text: θ

text: in

text: such

text: a

text: way

text: to

text: make

text: the

text: denominator

text: γ

text: θ

text: small

text: enough

text: and

text: the

text: s

text: s

text: quotient

text: C−n∗,s(

text: still

text: bounded.

text: γs

text: θ

text: The

text: previous

text: result

text: suggestes

text: the

text: following

text: choice

text: of

text: the

text: homogeneity

text: exponent

text: C

text: n,

text: s

text: γ

text: θ

text: s

text: s

text: µ0

text: θ

text: We

text: can

text: ﬁnally

text: prove

text: the

text: main

text: result

text: of

text: this

text: section.

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: ON s-HARMONIC FUNCTIONS ON CONES 31 (cid:3) (cid:37) 4. The limit for s 1 In this section we prove the main result, Theorem 1.3, emphasizing the diﬀerence between wide and narrow cones. Then we improve the asymptotic analysis proving uniqueness of the limit under assumptions on the geometry and the regularity of C. ∫ Let C ⊂ Rn be an open cone and consider the minimization problem  ∫ (4.1) λ1(C) = inf  Sn−1 |∇Sn−1u|2dσ : u ∈ H1(Sn−1) \ {0} and u = 0 in Sn−1 \ C , u2dσ Sn−1 ( ) ( )( ( ) − ) Mowrehoivcehr,isifstγr(icCtl)y>re2la,tee∫qdutiovatlheenthlyomifoλg1e(nCe)ity>o2fnt,htehesoplruotibolnemof (3.12) by λ1 C = γ C γ C +n 2 . (cid:18)∫ (cid:19) (4.2) µ0(C) := inf  Sn−1 |∇Sn−1u|2 − 2n2u2dσ : u ∈ H1(Sn−1) \ {0} and u = 0 in Sn−1 \ C | | u dσ Sn−1 ( ) is well deﬁned and the number µ0 C is strictly positive. By a standard argument due to the variational characterization of the previous quantities, we already ∈ ( − ∩ ) \ { } know the existence of a nonnegative eigenfunction ϕ H1 Sn 1 C 0 associated to the minimization ∈ ( − ∩0 ) \ { } problem (4.1) and a nonnegative function ψ H1 Sn 1 C 0 that achieves the minimum (4.2), since 0 the numerator in (4.2) is a coercive quadratic form equivalent to the one in (4.1). Since the cone C may be disconnected, it is well kn∫own that ϕ is not necessarily unique. Instead, the function ψ is unique up to amultiplicative constant, since it solves  − ( ) − ∩ (4.3) ∆Sn−1ψ = 2nψ + µ0 C Sn−1ψdσ in Sn−1 \ C, ψ = 0 in Sn 1 C. In fact, due to the integral term in the equation, the solution must be strictly positive in every con- ψ nected component of C and localizing the equation in a generic component we can easily get uniqueness by maximum principle. → A fundamental toll in order to reach as s 1 the space H1 , is the following result loc ##LTLine## ##LTLine##

text: ON

text: s-HARMONIC

text: FUNCTIONS

text: ON

text: CONES

font: PDHOGK+txsya

label: section

text: The

text: limit

text: for

text: s

text: In

text: this

text: section

text: we

text: prove

text: the

text: main

text: result,

text: Theorem

text: emphasizing

text: the

text: diﬀerence

text: between

text: wide

text: and

text: narrow

text: cones.

text: Then

text: we

text: improve

text: the

text: asymptotic

text: analysis

text: proving

text: uniqueness

text: of

text: the

text: limit

text: under

text: assumptions

text: on

text: the

text: geometry

text: and

text: the

text: regularity

text: of

text: C.

text: Let

text: C

text: Rn

text: be

text: an

text: open

text: cone

text: and

text: consider

text: the

text: minimization

text: problem

text: inf

text: u

text: and

text: u

text: in

text: C

text: by

text: λ1

text: C

text: γ

text: C

text: γ

text: C

text: +n

text: inf

text: u

text: and

text: u

text: in

text: C

text: u

text: dσ

text: is

text: well

text: deﬁned

text: and

text: the

text: number

text: µ0

text: C

text: is

text: strictly

text: positive.

text: By

text: a

text: standard

text: argument

text: due

text: to

text: the

text: variational

text: characterization

text: of

text: the

text: previous

text: quantities,

text: we

text: already

text: know

text: the

text: existence

text: of

text: a

text: nonnegative

text: eigenfunction

text: ϕ

text: Sn

text: C

text: associated

text: to

text: the

text: minimization

text: ∩0

text: problem

text: and

text: a

text: nonnegative

text: function

text: ψ

text: Sn

text: C

text: that

text: achieves

text: the

text: minimum

text: since

text: the

text: numerator

text: in

text: is

text: a

text: coercive

text: quadratic

text: form

text: equivalent

text: to

text: the

text: one

text: in

text: Since

text: the

text: cone

text: C

text: may

text: be

text: disconnected,

text: it

text: is

text: well

text: kn∫own

text: that

text: ϕ

text: is

text: not

text: necessarily

text: unique.

text: Instead,

text: the

text: function

text: ψ

text: is

text: unique

text: up

text: to

text: amultiplicative

text: constant,

text: since

text: it

text: solves

text: ∆Sn−1ψ

text: µ0

text: C

text: in

text: C,

text: ψ

text: in

text: Sn

text: C.

text: In

text: fact,

text: due

text: to

text: the

text: integral

text: term

text: in

text: the

text: equation,

text: the

text: solution

text: must

text: be

text: strictly

text: positive

text: in

text: every

text: con-

text: ψ

text: nected

text: component

text: of

text: C

text: and

text: localizing

text: the

text: equation

text: in

text: a

text: generic

text: component

text: we

text: can

text: easily

text: get

text: uniqueness

text: by

text: maximum

text: principle.

text: A

text: fundamental

text: toll

text: in

text: order

text: to

text: reach

text: as

text: s

text: the

text: space

text: is

text: the

text: following

text: result

text: loc

text: ##LTLine##

text: ##LTLine##


text: ON s-HARMONIC FUNCTIONS ON CONES 35 (4.2) always admits a unique solution. Ultimately, the main obstacle in this analysis is the disconnection of ( ) ≤ the cone C when γ C 2: in this case we cannot always ensure the uniqueness of the solution of the limit problem and even the positivity of the limit function u on every connected components of C. The following example shows uniqueness of the limit function u due to the nonlocal nature of the fractional Laplacian under a symmetry assumption on the cone C. ∪ · · · ∪ Proposition 4.3. Let C = C1 C∈m be( a) union of disconnected cones such that C1 is connected(and) there are or(tho)gon(al )maps Φ2,. . .,Φm O n( ()e.g. reﬂections about hyperplanes) such that Ci = Φi C1 and and Φ C = C for i = 2,. . .,m. Let u be the family of nonnegative solutions to (1.1) such that (cid:107) (cid:107) i s (cid:37) ( ) us L∞(Sn−1) = 1. Then there exists the limit of us as s 1 in Ll2oc Rn and uniformly on compact subsets of C. ∫ → Proof. We remark that, for any element of the orthogonal group Φ: Rn Rn, ( ( )) − ( ) (− ) ( ◦ ) ( ) ( ) u Φ x u y (− ) ( ( )) ∆ s u Φ x = C n, s P.V. | ( ) − | dy = ∆ su Φ x . Rn Φ x y n+2s ≡ ◦ By the uniqueness result [4, Theorem 3.2 ] of s-harmonic functions on cones, we infer that u u Φ , (cid:107) (cid:107) s s i fsoorluetvioernyoif= 2,. . .,m. Therefore, there holds con∫vergence to u, where satisﬁes u L∞(Sn−1) = 1, and it is a −∆u = µ(C) udσ in C, (4.8)  ≥ Sn−1 u 0 in C, \ u = 0 in Rn C , ≡ ◦ such that u u Φi for every i = 2,. . .,m. Finally, connectedness of C1 yields uniqueness of such solution also for narrow cones. (cid:3) Corollary 1.6 is an easy application of our main Theorem 1.3, since it is a consequence of the Dini’s Theorem for a monotone sequence of continuous functions which converges pointwisely to a continuous function on ∈ ( ) (cid:40) (cid:55)→ ( ) [ ) ( ) a compact set. In fact, ﬁxed s 0,1 , the function θ γ θ is continuous in 0,π with γ 0 = 2s and ( ) s [ ] s γ π = 0. Moreover this function is also monotone decreasing in 0,π and since there exists the limit s − θl→imπ− γs(θ) = γ2ss2(π1 ) = 0 iofthne=rw2isaen, d s > 12, (cid:55)→ ( ) (cid:40) [ ] ( ) we can extend θ γ θ to a continuous function in 0,π (see [23]). Nevertheless, the limit γ θ = ( ) { (s ) } [ ] lims→1 γs θ = min γ θ ,2 is continuous on 0,π with γ(π) = 12 if n = 2, 0 otherwise . ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: ON

text: s-HARMONIC

text: FUNCTIONS

text: ON

text: CONES

text: always

text: admits

text: a

text: unique

text: solution.

text: Ultimately,

text: the

text: main

text: obstacle

text: in

text: this

text: analysis

text: is

text: the

text: disconnection

text: of

text: the

text: cone

text: C

text: when

text: γ

text: C

text: in

text: this

text: case

text: we

text: cannot

text: always

text: ensure

text: the

text: uniqueness

text: of

text: the

text: solution

text: of

text: the

text: limit

text: problem

text: and

text: even

text: the

text: positivity

text: of

text: the

text: limit

text: function

text: u

text: on

text: every

text: connected

text: components

text: of

text: C.

text: The

text: following

text: example

text: shows

text: uniqueness

text: of

text: the

text: limit

text: function

text: u

text: due

text: to

text: the

text: nonlocal

text: nature

text: of

text: the

text: fractional

text: Laplacian

text: under

text: a

text: symmetry

text: assumption

text: on

text: the

text: cone

text: C.

text: Proposition

text: Let

text: C

text: C∈m

text: be(

text: a)

text: union

text: of

text: disconnected

text: cones

text: such

text: that

text: is

text: connected(and)

text: there

text: are

text: or(tho)gon(al

text: )maps

text: .,Φm

text: O

text: n(

text: ()e.g.

text: reﬂections

text: about

text: hyperplanes)

text: such

text: that

text: Ci

text: Φi

text: and

text: and

text: Φ

text: C

text: C

text: for

text: i

text: .,m.

text: Let

text: u

text: be

text: the

text: family

text: of

text: nonnegative

text: solutions

text: to

text: such

text: that

text: i

text: s

text: us

text: Then

text: there

text: exists

text: the

text: limit

text: of

text: us

text: as

text: s

text: in

text: Rn

text: and

text: uniformly

text: on

text: compact

text: subsets

text: of

text: C.

text: Proof.

text: We

text: remark

text: that,

text: for

text: any

text: element

text: of

text: the

text: orthogonal

text: group

text: Φ:

text: Rn

text: Rn,

text: u

text: Φ

text: x

text: u

text: y

text: s

text: u

text: Φ

text: x

text: C

text: n,

text: s

text: P.V.

text: dy

text: su

text: Φ

text: x

text: Rn

text: Φ

text: x

text: y

text: By

text: the

text: uniqueness

text: result

text: Theorem

text: of

text: s-harmonic

text: functions

text: on

text: cones,

text: we

text: infer

text: that

text: u

text: u

text: Φ

text: s

text: s

text: i

text: fsoorluetvioernyoif=

text: .,m.

text: Therefore,

text: there

text: holds

text: con∫vergence

text: to

text: u,

text: where

text: satisﬁes

text: u

text: and

text: it

text: is

text: a

text: −∆u

text: µ(C)

text: udσ

text: in

text: C,

text: u

text: in

text: C,

text: u

text: in

text: Rn

text: C

text: such

text: that

text: u

text: u

text: Φi

text: for

text: every

text: i

text: .,m.

text: Finally,

text: connectedness

text: of

text: yields

text: uniqueness

text: of

text: such

text: solution

text: also

text: for

text: narrow

text: cones.

text: Corollary

text: is

text: an

text: easy

text: application

text: of

text: our

text: main

text: Theorem

text: since

text: it

text: is

text: a

text: consequence

text: of

text: the

text: Dini’s

text: Theorem

text: for

text: a

text: monotone

text: sequence

text: of

text: continuous

text: functions

text: which

text: converges

text: pointwisely

text: to

text: a

text: continuous

text: function

text: on

text: a

text: compact

text: set.

text: In

text: fact,

text: ﬁxed

text: s

text: the

text: function

text: θ

text: γ

text: θ

text: is

text: continuous

text: in

text: with

text: γ

text: and

text: s

text: s

text: γ

text: π

text: Moreover

text: this

text: function

text: is

text: also

text: monotone

text: decreasing

text: in

text: and

text: since

text: there

text: exists

text: the

text: limit

text: s

text: θl→imπ−

text: γs(θ)

text: d

text: s

text: we

text: can

text: extend

text: θ

text: γ

text: θ

text: to

text: a

text: continuous

text: function

text: in

text: (see

text: Nevertheless,

text: the

text: limit

text: γ

text: θ

text: (s

text: γs

text: θ

text: min

text: γ

text: θ

text: is

text: continuous

text: on

text: with

text: γ(π)

text: if

text: n

text: otherwise

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: 36 SUSANNA TERRACINI, GIORGIO TORTONE, AND STEFANO VITA y ( ) ( ) y = Γ θ y = Γ θ ( ) 1 y = Γs θ s / / / θ 0 π 4 π 2 3π 4 π ( ) ( ) ( ) Figure 3. Values of the limit Γ θ = lims→1 Γs θ and Γ θ , for n = 2. ∈ [ ] (cid:55)→ ( ) ( ) Eventually, for any ﬁxed θ 0,π , the function s γ θ is monotone nondecreasing in 0,1 . By the [ ] s Dini’s Theorem the convergence is uniform on 0 . This fact obviously implies the uniform convergence ,π ( ) ( − ) ( ) ( − ) ( ) γ θ + γ π θ −→ ( ) γ θ + γ π θ Γs θ = s s Γ θ = 2 2 [ ] in 0 , and hence ,π ( ) −→ ( ) νsACF = θm∈[0i,nπ] Γs θ θm∈[0i,nπ] Γ θ = νACF. (cid:3) 5. Uniform in s estimates in C0,α on annuli ⊂ − We have already remarked in Section 2 that, if you take a cone C = C with ω Sn 1 a ﬁnite union of ∪ ∅ ω connected C1,1 domain ω , such that ω ω = for i (cid:44) j, by [23, Lemma 3.3] we have (2.2). i ( i− ) j ∈ ( ) ∈ ( ) Hence solutions u to (1.1) are C0,s Sn 1 and for any ﬁxed α 0,1 , any solution u with s α,1 is ( − ) s s C0,α Sn 1 ; that is, there exists L > 0 such that s | ( ) − ( )| u x u y sup s | − |s = L . x,y∈Sn−1 x y α s \ ∞ Let us consider an annulus A = Ar1,r2 = Br2 Br1 with 0 < r1 < r2 < + . We have the following result. ∈ ( ) ∈ ( { / } ) Lemma 5.1. Let α 0,1 , s0 max 1 2,α ,1 and ∈A[an an) nulus centered at zero. Then there exists a constant c > 0 such that any solution us to (1.1) with s s0,1 satisﬁes | ( ) − ( )| u x u y ≤ sup s | − |s cL . ∈ x y α s x,y A ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: SUSANNA

text: TERRACINI,

text: GIORGIO

text: TORTONE,

text: AND

text: STEFANO

text: VITA

text: y

text: y

text: Γ

text: θ

text: y

text: Γ

text: θ

text: y

text: Γs

text: θ

text: s

text: θ

text: π

text: π

text: 3π

text: π

text: Figure

text: Values

text: of

text: the

text: limit

text: Γ

text: θ

text: Γs

text: θ

text: and

text: Γ

text: θ

text: for

text: n

text: Eventually,

text: for

text: any

text: ﬁxed

text: θ

text: the

text: function

text: s

text: γ

text: θ

text: is

text: monotone

text: nondecreasing

text: in

text: By

text: the

text: s

text: Dini’s

text: Theorem

text: the

text: convergence

text: is

text: uniform

text: on

text: This

text: fact

text: obviously

text: implies

text: the

text: uniform

text: convergence

text: ,π

text: γ

text: θ

text: γ

text: π

text: θ

text: γ

text: θ

text: γ

text: π

text: θ

text: Γs

text: θ

text: s

text: s

text: Γ

text: θ

text: in

text: and

text: hence

text: ,π

text: νsACF

text: Γs

text: θ

text: Γ

text: θ

text: νACF.

text: Uniform

text: in

text: s

text: estimates

text: in

text: on

text: annuli

text: We

text: have

text: already

text: remarked

text: in

text: Section

text: that,

text: if

text: you

text: take

text: a

text: cone

text: C

text: C

text: with

text: ω

text: Sn

text: a

text: ﬁnite

text: union

text: of

text: ω

text: connected

text: domain

text: ω

text: such

text: that

text: ω

text: ω

text: for

text: i

text: j,

text: by

text: Lemma

text: we

text: have

text: i

text: i−

text: j

text: Hence

text: solutions

text: u

text: to

text: are

text: Sn

text: and

text: for

text: any

text: ﬁxed

text: α

text: any

text: solution

text: u

text: with

text: s

text: is

text: s

text: s

text: Sn

text: that

text: is,

text: there

text: exists

text: L

text: such

text: that

text: s

text: u

text: x

text: u

text: y

text: sup

text: s

text: |s

text: L

text: x

text: y

text: α

text: s

text: Let

text: us

text: consider

text: an

text: annulus

text: A

text: with

text: We

text: have

text: the

text: following

text: result.

text: Lemma

text: Let

text: α

text: max

text: and

text: ∈A[an

text: an)

text: nulus

text: centered

text: at

text: zero.

text: Then

text: there

text: exists

text: a

text: constant

text: c

text: such

text: that

text: any

text: solution

text: us

text: to

text: with

text: s

text: satisﬁes

text: u

text: x

text: u

text: y

text: sup

text: s

text: |s

text: cL

text: x

text: y

text: α

text: s

text: x,y

text: A

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: RATIONAL TRANSDUCTIONS 13 (cid:48) (cid:48) From (γ), by multiplying by Y on the right k times we have: v (Y )k = ((X )sx w)kv . (cid:48) i,j j j i,j Moreover, since (Y )k corresponds to a sequence of length a multiple of k, we also have: (cid:48) v (Y )k = (X )ks+1v . Hence (X )ks+1 = ((X )sx w)k. And by combining the two we i,j j i,j j j j obtain (X )ks+1 = (X )ks(x w)k, hence: j j j X = (x w)k j j This yields: (X )sw = w(X )s j+1 j = w(x w)ks j = (wx )ksw j Hence, X = (wx )k. j+1 j (cid:48) Let q be another looping state state such that q −u−→t A q . Again, since A is aperiodic, l (cid:48) (cid:48) l l by taking t large enough we can assume, t = t . If v < v then v = w v . However, l,j l,j+1 l,j+1 l l,j it also implies that (x w)k = (x w )k, hence w = w. On the other hand, let us assume j j l (cid:48) l v > v with w v = v . Let Y and Y correspond this time to sequences associated l,j l,j+1 l l,j+1 l,j l l with q −u→t A q and q −u−t−−→1 A q , respectively. l l l l w v Y = (X )sw v l l,j+1 l j l l,j+1 v Y = (X )sv l,j+1 l(cid:48) j+1 l,j+1· · · v Y = (X )sx x − w v l,j+1 l j+1 j+1 j 1 l l,j+1 As above, the ﬁrst two equations give: (X )sw = w (X )s j l l j+1 From the third equation we have: · · · − ((X )sx x − w )k = (X )ks+k 1 j+1 j+1 j 1 l j+1 Let us remark that: · · · · · · (X )sx x − = x x − (X )s j+1 j+1 j 1 j+1 j 1 j Hence: · · · · · · (X )sx x − w = x x − w (X )s j+1 j+1 j 1 l j+1 j 1 l j+1 · · · − From this we obtain (x x − w )k = (X )k 1. j+1 j 1 l j+1 Now from above we can write: · · · − (x x − w )k = ((wx )k)k 1 j+1 · · ·j 1 l j − x x − w = (wx )k 1 j+1 · · · j 1 l j wx x x − w = (wx )k j j+1 j 1 l j wX w = X j l j+1 Hence by length, we obtain w = w = ε. l Let q be a state reachable from q (any state is reachable from some such looping state). l i Then it can be reached by a sequence of length t and there is a corresponding sequence of outputs denoted by Z such that: l v Z = (X )sv i,j l j l,j wv Z = (X )sv i,j l j+1 i,j+1 Hence wv = v . l,j l,j+1 (cid:48) ∈ { · · · } Finally, w is a common preﬁx to all v (cid:48) (j ﬁxed and i 1, , m ) and must by i ,j+1 deﬁnition be empty. The reasoning is the same if we assume v > v . Hence v (cid:48) = v (cid:48) A(cid:48) i,j i,j+1 i ,j i ,j+1 and therefore k = 1, which means that is counter-free and thus is aperiodic. We have

text: RATIONAL

text: TRANSDUCTIONS

text: From

text: (γ),

text: by

text: multiplying

text: by

text: Y

text: on

text: the

text: right

text: k

text: times

text: we

text: have:

text: v

text: (Y

text: )k

text: ((X

text: )sx

text: w)kv

text: i,j

text: j

text: j

text: i,j

text: Moreover,

text: since

text: (Y

text: )k

text: corresponds

text: to

text: a

text: sequence

text: of

text: length

text: a

text: multiple

text: of

text: k,

text: we

text: also

text: have:

text: v

text: (Y

text: )k

text: (X

text: Hence

text: (X

text: ((X

text: )sx

text: w)k.

text: And

text: by

text: combining

text: the

text: two

text: we

text: i,j

text: j

text: i,j

text: j

text: j

text: j

text: obtain

text: (X

text: (X

text: )ks(x

text: w)k,

text: hence:

text: j

text: j

text: j

text: X

text: (x

text: w)k

text: j

text: j

text: This

text: yields:

text: (X

text: )sw

text: w(X

text: )s

text: j

text: w(x

text: w)ks

text: j

text: (wx

text: )ksw

text: j

text: Hence,

text: X

text: (wx

text: )k.

text: j

text: Let

text: q

text: be

text: another

text: looping

text: state

text: state

text: such

text: that

text: q

text: −u−→t

text: A

text: q

text: Again,

text: since

text: A

text: is

text: aperiodic,

text: l

text: l

text: l

text: by

text: taking

text: t

text: large

text: enough

text: we

text: can

text: assume,

text: t

text: t

text: If

text: v

text: v

text: then

text: v

text: w

text: v

text: However,

text: l,j

text: l

text: l,j

text: it

text: also

text: implies

text: that

text: (x

text: w)k

text: (x

text: w

text: )k,

text: hence

text: w

text: w.

text: On

text: the

text: other

text: hand,

text: let

text: us

text: assume

text: j

text: j

text: l

text: l

text: v

text: v

text: with

text: w

text: v

text: v

text: Let

text: Y

text: and

text: Y

text: correspond

text: this

text: time

text: to

text: sequences

text: associated

text: l,j

text: l

text: l,j

text: l

text: l

text: with

text: q

text: −u→t

text: A

text: q

text: and

text: q

text: −u−t−−→1

text: A

text: q

text: respectively.

text: l

text: l

text: l

text: l

text: w

text: v

text: Y

text: (X

text: )sw

text: v

text: l

text: l

text: j

text: l

text: v

text: Y

text: (X

text: )sv

text: v

text: Y

text: (X

text: )sx

text: x

text: w

text: v

text: l

text: j

text: l

text: As

text: above,

text: the

text: ﬁrst

text: two

text: equations

text: give:

text: (X

text: )sw

text: w

text: (X

text: )s

text: j

text: l

text: l

text: From

text: the

text: third

text: equation

text: we

text: have:

text: ((X

text: )sx

text: x

text: w

text: )k

text: (X

text: )ks+k

text: j

text: l

text: Let

text: us

text: remark

text: that:

text: (X

text: )sx

text: x

text: x

text: x

text: (X

text: )s

text: j

text: j

text: j

text: Hence:

text: (X

text: )sx

text: x

text: w

text: x

text: x

text: w

text: (X

text: )s

text: j

text: l

text: j

text: l

text: From

text: this

text: we

text: obtain

text: (x

text: x

text: w

text: )k

text: (X

text: )k

text: j

text: l

text: Now

text: from

text: above

text: we

text: can

text: write:

text: (x

text: x

text: w

text: )k

text: ((wx

text: )k)k

text: ·j

text: l

text: j

text: x

text: x

text: w

text: (wx

text: )k

text: j

text: l

text: j

text: wx

text: x

text: x

text: w

text: (wx

text: )k

text: j

text: j

text: l

text: j

text: wX

text: w

text: X

text: j

text: l

text: Hence

text: by

text: length,

text: we

text: obtain

text: w

text: w

text: ε.

text: l

text: Let

text: q

text: be

text: a

text: state

text: reachable

text: from

text: q

text: (any

text: state

text: is

text: reachable

text: from

text: some

text: such

text: looping

text: state).

text: l

text: i

text: Then

text: it

text: can

text: be

text: reached

text: by

text: a

text: sequence

text: of

text: length

text: t

text: and

text: there

text: is

text: a

text: corresponding

text: sequence

text: of

text: outputs

text: denoted

text: by

text: Z

text: such

text: that:

text: l

text: v

text: Z

text: (X

text: )sv

text: i,j

text: l

text: j

text: l,j

text: wv

text: Z

text: (X

text: )sv

text: i,j

text: l

text: Hence

text: wv

text: v

text: l,j

text: Finally,

text: w

text: is

text: a

text: common

text: preﬁx

text: to

text: all

text: v

text: (j

text: ﬁxed

text: and

text: i

text: m

text: and

text: must

text: by

text: i

text: deﬁnition

text: be

text: empty.

text: The

text: reasoning

text: is

text: the

text: same

text: if

text: we

text: assume

text: v

text: v

text: Hence

text: v

text: v

text: i,j

text: i

text: ,j

text: i

text: and

text: therefore

text: k

text: which

text: means

text: that

text: is

text: counter-free

text: and

text: thus

text: is

text: aperiodic.

text: We

text: have


text: RATIONAL TRANSDUCTIONS 5 2. Algebraic characterization of sequential transductions 8 3. Bimachines 13 4. Algebraic characterization of rational transductions 22 5. Characterization of aperiodic transductions 28 6. Logical transducers 33 Conclusion 42 Acknowledgement 42 References 42 1. Rational languages and rational transductions An alphabet Σ is a ﬁnite set of symbols called letters, a word over Σ is an element of ∗ the free monoid Σ , whose neutral element, the empty word, is denoted by (cid:15). The length of ∈ ∗ | | | | a word w Σ is denoted by w with (cid:15) = 0. For a non-empty word w and two positions ≤ ≤ ≤ | | 1 i j w we denote by w[i] the ith letter of w and by w[i : j] the factor of w beginning (cid:22) with the ith letter and ending with the jth letter of w. For two words u, v, we write u v if − (cid:48) (cid:48) u is a preﬁx of v and in this case we denote by u 1v the unique word v such that uv = v. (cid:86) ∧ The longest common preﬁx of two words u, v is denoted by u v and the preﬁx distance (cid:86) (cid:107) (cid:107) | | | | − | ∧ | between u and v is deﬁned as u, v = u + v 2 u v . A language L is a set of words and L denotes the longest common preﬁx of all the words in L with the convention that ∅ = (cid:15). A A ﬁnite automaton (or simply automaton) over an alphabet Σ is a tuple = (Q, ∆, I, F ) ⊆ × × ⊆ where Q is a ﬁnite set of states, ∆ Q Σ Q is the transition relation, and I, F Q A denote the set of initial states and the set of ﬁnal states, respectively. A run of over a word ∈ ∈ { | | − } w is a word r = q . . . q| | over Q such that (q , w[i + 1], q ) ∆ for all i 0, . . . , w 1 . 0 w ∈ ∈ i i+1 A The run r is accepting if q I and q| | F . A word w is accepted by if there exists (cid:74) 0(cid:75) w A an accepting run over it, and the language recognized by is the set of words accepted A A −→ −→ by and is denoted by . We will use the notation p w A q (or just p w q when it is A clear from context) to denote that there exists a run r of over w such that r[1] = p and | | A r[ r ] = q. An automaton is called deterministic if its set of initial states is a singleton ∈ and for any two transitions (p, σ, q ), (p, σ, q ) ∆ it holds that q = q . An automaton 1 2 1 2 is unambiguous if any word has at most one accepting run over it. We call an automaton ∈ ∈ ∈ ∈ complete if for any p Q, σ Σ there exists q Q such that (p, σ, q) ∆. A state q of an A automaton is said to be accessible if there exists a word w and an initial state q , such −→ A 0 that q w A q. We say by extension that the automaton is accessible if all its states are 0 accessible. Finally, a language is called rational if it is recognized by an automaton.

text: RATIONAL

text: TRANSDUCTIONS

text: Algebraic

text: characterization

text: of

text: sequential

text: transductions

text: Bimachines

text: Algebraic

text: characterization

text: of

text: rational

text: transductions

text: Characterization

text: of

text: aperiodic

text: transductions

text: Logical

text: transducers

text: Conclusion

text: Acknowledgement

text: References

text: Rational

text: languages

text: and

text: rational

text: transductions

text: An

text: alphabet

text: Σ

text: is

text: a

text: ﬁnite

text: set

text: of

text: symbols

text: called

text: letters,

text: a

text: word

text: over

text: Σ

text: is

text: an

text: element

text: of

text: the

text: free

text: monoid

text: Σ

text: whose

text: neutral

text: element,

text: the

text: empty

text: word,

text: is

text: denoted

text: by

text: The

text: length

text: of

text: a

text: word

text: w

text: Σ

text: is

text: denoted

text: by

text: w

text: with

text: For

text: a

text: non-empty

text: word

text: w

text: and

text: two

text: positions

text: i

text: j

text: w

text: we

text: denote

text: by

text: w[i]

text: the

text: ith

text: letter

text: of

text: w

text: and

text: by

text: w[i

text: j]

text: the

text: factor

text: of

text: w

text: beginning

text: with

text: the

text: ith

text: letter

text: and

text: ending

text: with

text: the

text: jth

text: letter

text: of

text: w.

text: For

text: two

text: words

text: u,

text: v,

text: we

text: write

text: u

text: v

text: if

text: u

text: is

text: a

text: preﬁx

text: of

text: v

text: and

text: in

text: this

text: case

text: we

text: denote

text: by

text: u

text: the

text: unique

text: word

text: v

text: such

text: that

text: uv

text: v.

text: The

text: longest

text: common

text: preﬁx

text: of

text: two

text: words

text: u,

text: v

text: is

text: denoted

text: by

text: u

text: v

text: and

text: the

text: preﬁx

text: distance

text: between

text: u

text: and

text: v

text: is

text: deﬁned

text: as

text: u,

text: v

text: u

text: v

text: u

text: v

text: A

text: language

text: L

text: is

text: a

text: set

text: of

text: words

text: and

text: L

text: denotes

text: the

text: longest

text: common

text: preﬁx

text: of

text: all

text: the

text: words

text: in

text: L

text: with

text: the

text: convention

text: that

text: A

text: A

text: ﬁnite

text: automaton

text: (or

text: simply

text: automaton)

text: over

text: an

text: alphabet

text: Σ

text: is

text: a

text: tuple

text: (Q,

text: I,

text: F

text: where

text: Q

text: is

text: a

text: ﬁnite

text: set

text: of

text: states,

text: Q

text: Σ

text: Q

text: is

text: the

text: transition

text: relation,

text: and

text: I,

text: F

text: Q

text: A

text: denote

text: the

text: set

text: of

text: initial

text: states

text: and

text: the

text: set

text: of

text: ﬁnal

text: states,

text: respectively.

text: A

text: run

text: of

text: over

text: a

text: word

text: w

text: is

text: a

text: word

text: r

text: q

text: q|

text: over

text: Q

text: such

text: that

text: (q

text: w[i

text: q

text: for

text: all

text: i

text: w

text: w

text: i

text: A

text: The

text: run

text: r

text: is

text: accepting

text: if

text: q

text: I

text: and

text: q|

text: F

text: A

text: word

text: w

text: is

text: accepted

text: by

text: if

text: there

text: exists

text: w

text: A

text: an

text: accepting

text: run

text: over

text: it,

text: and

text: the

text: language

text: recognized

text: by

text: is

text: the

text: set

text: of

text: words

text: accepted

text: A

text: A

text: by

text: and

text: is

text: denoted

text: by

text: We

text: will

text: use

text: the

text: notation

text: p

text: w

text: A

text: q

text: (or

text: just

text: p

text: w

text: q

text: when

text: it

text: is

text: A

text: clear

text: from

text: context)

text: to

text: denote

text: that

text: there

text: exists

text: a

text: run

text: r

text: of

text: over

text: w

text: such

text: that

text: p

text: and

text: A

text: r[

text: r

text: q.

text: An

text: automaton

text: is

text: called

text: deterministic

text: if

text: its

text: set

text: of

text: initial

text: states

text: is

text: a

text: singleton

text: and

text: for

text: any

text: two

text: transitions

text: (p,

text: σ,

text: q

text: (p,

text: σ,

text: q

text: it

text: holds

text: that

text: q

text: q

text: An

text: automaton

text: is

text: unambiguous

text: if

text: any

text: word

text: has

text: at

text: most

text: one

text: accepting

text: run

text: over

text: it.

text: We

text: call

text: an

text: automaton

text: complete

text: if

text: for

text: any

text: p

text: Q,

text: σ

text: Σ

text: there

text: exists

text: q

text: Q

text: such

text: that

text: (p,

text: σ,

text: q)

text: A

text: state

text: q

text: of

text: an

text: A

text: automaton

text: is

text: said

text: to

text: be

text: accessible

text: if

text: there

text: exists

text: a

text: word

text: w

text: and

text: an

text: initial

text: state

text: q

text: such

text: A

text: that

text: q

text: w

text: A

text: q.

text: We

text: say

text: by

text: extension

text: that

text: the

text: automaton

text: is

text: accessible

text: if

text: all

text: its

text: states

text: are

text: accessible.

text: Finally,

text: a

text: language

text: is

text: called

text: rational

text: if

text: it

text: is

text: recognized

text: by

text: an

text: automaton.


text: 6 E. FILIOT, O. GAUWIN, AND N. LHOTE It is well known that rational languages are equivalently recognized by congruences ∼ ∗ of ﬁnite index. Let us deﬁne these notions. Let be an equivalence relation on Σ . The equivalence class of a word w is denoted by [w]∼ (or just [w] when it is clear from context). ∼ ∗ { | ∈ ∗} ∼ ∼ We say that has ﬁnite index if the quotient Σ /∼ = [w]∼ w Σ is ﬁnite. Let , ∼ ∼ ∼ 1 2 be two equivalence relations, we say that is ﬁner than (or that is coarser than ∼ ∼ 1 2 ∼ 2 ) if any equivalence class of is a union of equivalence classes of , or equivalently 1 ∼ 2 ∼ ∼ (cid:118) ∼ 1 ∼ for any two words u, v, if u v then u v. We write to denote that is ﬁner ∼ 1 2 1 2 1 than . 2 ∼ ∗ An equivalence relation over Σ is a right congruence (resp. a left congruence) if for ∈ ∗ ∈ ∼ ⇒ ∼ any words u, v Σ and letter σ Σ we have u v uσ vσ. A congruence is deﬁned as ∼ ∗ both a left and a right congruence. When is a congruence, the quotient Σ /∼ is naturally · endowed with a monoid structure, with multiplication [u]∼ [v]∼ = [uv]∼ and identity [(cid:15)]∼. ∼ We say that a congruence recognizes a language L if L is a union of equivalence classes of ∼ ∼ ∼ . Let us note that the intersection of two right (resp. left) congruences , over the ∼ (cid:117)1 ∼2 same alphabet is also a right (resp. left) congruence which we denote by . 1 2 Example 1.1. Important examples of congruences which we use throughout the article ≡ ≈ are: the syntactic congruence of a language L and the transition congruence A of an A L A automaton with set of states Q. When is deterministic with initial state q , we also ∼ A 0 deﬁne A, the right transition congruence of . These relations are deﬁned as follows, with u, v ranging over all words: ≡ ⇔ ∀ ∈ ∗ ∈ ⇔ ∈ u v ( x, y Σ , xuy L xvy L) ≈L ⇔ ∀ ∈ −→ ⇔ −→ u A v ( p, q Q, p u A q p v A q) ∼ ⇔ ∀ ∈ −→ ⇔ −→ u A v ( q Q, q u A q q v A q) A 0 ≈ 0 If recognizes a language L, then its transition congruence A recognizes the same language. ≡ The relation recognizes the language L and is the coarsest among congruences which do L so. From the two previous remarks, this well-known fact follows: a language is rational if and only if its syntactic congruence has ﬁnite index. A Let be a complete and deAterministic automaton, then an equivalence class [w]∼A can be identiﬁed with the state of reached by reading the word w. In the following we will A often make this identiﬁcation, implicitly assuming that is complete (an automaton can be made complete in PTime), and will write [Aw]AArather than [∼w]∼A(cid:118)to∼simplify notations. Furthermore, for two deterministic automata , such that A A , we will say by A A A (cid:118)1 A2 1 2 extension that is ﬁner than and write . For example the minimal automaton 1 2 1 2 of a language L is the coarsest deterministic automaton recognizing L (up to isomorphism). A congruence class (class for short) C associates to any ﬁnite alphabet Σ, a set C(Σ) of congruences of ﬁnite index over Σ, such that C(Σ) is 1) closed under intersection and 2) closed under taking coarser congruences. Note that we will often abuse the notation and write C instead of C(Σ). An automaton is called a C-automaton if its transition congruence is in C. A language is a C-language if it is recognized by a C-automaton. Note that since a class is stable by

text: E.

text: FILIOT,

text: O.

text: GAUWIN,

text: AND

text: N.

text: LHOTE

text: It

text: is

text: well

text: known

text: that

text: rational

text: languages

text: are

text: equivalently

text: recognized

text: by

text: congruences

text: of

text: ﬁnite

text: index.

text: Let

text: us

text: deﬁne

text: these

text: notions.

text: Let

text: be

text: an

text: equivalence

text: relation

text: on

text: Σ

text: The

text: equivalence

text: class

text: of

text: a

text: word

text: w

text: is

text: denoted

text: by

text: [w]∼

text: (or

text: just

text: [w]

text: when

text: it

text: is

text: clear

text: from

text: context).

text: We

text: say

text: that

text: has

text: ﬁnite

text: index

text: if

text: the

text: quotient

text: Σ

text: [w]∼

text: w

text: Σ

text: is

text: ﬁnite.

text: Let

text: be

text: two

text: equivalence

text: relations,

text: we

text: say

text: that

text: is

text: ﬁner

text: than

text: (or

text: that

text: is

text: coarser

text: than

text: if

text: any

text: equivalence

text: class

text: of

text: is

text: a

text: union

text: of

text: equivalence

text: classes

text: of

text: or

text: equivalently

text: for

text: any

text: two

text: words

text: u,

text: v,

text: if

text: u

text: v

text: then

text: u

text: v.

text: We

text: write

text: to

text: denote

text: that

text: is

text: ﬁner

text: than

text: An

text: equivalence

text: relation

text: over

text: Σ

text: is

text: a

text: right

text: congruence

text: (resp.

text: a

text: left

text: congruence)

text: if

text: for

text: any

text: words

text: u,

text: v

text: Σ

text: and

text: letter

text: σ

text: Σ

text: we

text: have

text: u

text: v

text: uσ

text: vσ.

text: A

text: congruence

text: is

text: deﬁned

text: as

text: both

text: a

text: left

text: and

text: a

text: right

text: congruence.

text: When

text: is

text: a

text: congruence,

text: the

text: quotient

text: Σ

text: is

text: naturally

text: endowed

text: with

text: a

text: monoid

text: structure,

text: with

text: multiplication

text: [u]∼

text: [v]∼

text: [uv]∼

text: and

text: identity

text: We

text: say

text: that

text: a

text: congruence

text: recognizes

text: a

text: language

text: L

text: if

text: L

text: is

text: a

text: union

text: of

text: equivalence

text: classes

text: of

text: Let

text: us

text: note

text: that

text: the

text: intersection

text: of

text: two

text: right

text: (resp.

text: left)

text: congruences

text: over

text: the

text: ∼2

text: same

text: alphabet

text: is

text: also

text: a

text: right

text: (resp.

text: left)

text: congruence

text: which

text: we

text: denote

text: by

text: Example

text: Important

text: examples

text: of

text: congruences

text: which

text: we

text: use

text: throughout

text: the

text: article

text: are:

text: the

text: syntactic

text: congruence

text: of

text: a

text: language

text: L

text: and

text: the

text: transition

text: congruence

text: A

text: of

text: an

text: A

text: L

text: A

text: automaton

text: with

text: set

text: of

text: states

text: Q.

text: When

text: is

text: deterministic

text: with

text: initial

text: state

text: q

text: we

text: also

text: A

text: deﬁne

text: A,

text: the

text: right

text: transition

text: congruence

text: of

text: These

text: relations

text: are

text: deﬁned

text: as

text: follows,

text: with

text: u,

text: v

text: ranging

text: over

text: all

text: words:

text: u

text: v

text: x,

text: y

text: Σ

text: xuy

text: L

text: xvy

text: L)

text: ≈L

text: u

text: A

text: v

text: p,

text: q

text: Q,

text: p

text: u

text: A

text: q

text: p

text: v

text: A

text: q)

text: u

text: A

text: v

text: q

text: Q,

text: q

text: u

text: A

text: q

text: q

text: v

text: A

text: q)

text: A

text: If

text: recognizes

text: a

text: language

text: L,

text: then

text: its

text: transition

text: congruence

text: A

text: recognizes

text: the

text: same

text: language.

text: The

text: relation

text: recognizes

text: the

text: language

text: L

text: and

text: is

text: the

text: coarsest

text: among

text: congruences

text: which

text: do

text: L

text: so.

text: From

text: the

text: two

text: previous

text: remarks,

text: this

text: well-known

text: fact

text: follows:

text: a

text: language

text: is

text: rational

text: if

text: and

text: only

text: if

text: its

text: syntactic

text: congruence

text: has

text: ﬁnite

text: index.

text: A

text: Let

text: be

text: a

text: complete

text: and

text: deAterministic

text: automaton,

text: then

text: an

text: equivalence

text: class

text: [w]∼A

text: can

text: be

text: identiﬁed

text: with

text: the

text: state

text: of

text: reached

text: by

text: reading

text: the

text: word

text: w.

text: In

text: the

text: following

text: we

text: will

text: A

text: often

text: make

text: this

text: identiﬁcation,

text: implicitly

text: assuming

text: that

text: is

text: complete

text: (an

text: automaton

text: can

text: be

text: made

text: complete

text: in

text: PTime),

text: and

text: will

text: write

text: [Aw]AArather

text: than

text: notations.

text: Furthermore,

text: for

text: two

text: deterministic

text: automata

text: such

text: that

text: A

text: A

text: we

text: will

text: say

text: by

text: A

text: A

text: A

text: extension

text: that

text: is

text: ﬁner

text: than

text: and

text: write

text: For

text: example

text: the

text: minimal

text: automaton

text: of

text: a

text: language

text: L

text: is

text: the

text: coarsest

text: deterministic

text: automaton

text: recognizing

text: L

text: (up

text: to

text: isomorphism).

text: A

text: congruence

text: class

text: (class

text: for

text: short)

text: C

text: associates

text: to

text: any

text: ﬁnite

text: alphabet

text: Σ,

text: a

text: set

text: C(Σ)

text: of

text: congruences

text: of

text: ﬁnite

text: index

text: over

text: Σ,

text: such

text: that

text: C(Σ)

text: is

text: closed

text: under

text: intersection

text: and

text: closed

text: under

text: taking

text: coarser

text: congruences.

text: Note

text: that

text: we

text: will

text: often

text: abuse

text: the

text: notation

text: and

text: write

text: C

text: instead

text: of

text: C(Σ).

text: An

text: automaton

text: is

text: called

text: a

text: C-automaton

text: if

text: its

text: transition

text: congruence

text: is

text: in

text: C.

text: A

text: language

text: is

text: a

text: C-language

text: if

text: it

text: is

text: recognized

text: by

text: a

text: C-automaton.

text: Note

text: that

text: since

text: a

text: class

text: is

text: stable

text: by


text: 8 E. FILIOT, O. GAUWIN, AND N. LHOTE ∗ → ∗ A transduction over an alphabet Σ is a partial function2 f : Σ Σ , and its domain is denoted by dom(f). T A A A ﬁnite transducer3 (or simply transducer) over Σ is a tuple = ( , o, i, t) where = T → ∗ → ∗ (Q, ∆, I, F ) is the underlying automaton of , o : ∆ Σ is the output function, i : I Σ → ∗ is the initial output function and t : F Σ is the ﬁnal output function. Let u be a word A · · · | | on which there exists a run q . . . q| | of , and let v = o(q , u[1], q ) o(q| |− , u[ u ], q| |), 0 u 0 1 u 1 u −u−→|v ∈ ∈(cid:74) (cid:75) then we write q T q| | to denote the existence of such a run. If q I and q| | F , let 0 u T 0 u T w = i(q )vt(q| |), then we say that the pair (u, w) is realized by . We denote by the 0 u T set of pairs realized by . (cid:74) (cid:75) A transducer is called functional if it realizes a transduction (i.e. a partial function), (cid:74) (cid:75) ∈ T this property is decidable in PTime (see e.g. [BB79]) and in this case we denote (u, v) T T by (u) = v. A transducer is called unambiguous (resp. sequential) if its underlying T automaton is unambiguous (resp. deterministic) and in both cases is functional. It is known that any functional transducer is equivalent to some unambiguous transducer (see e.g. [BB79]). Finally, a transduction is called rational (resp. sequential) if it is realized by a functional (resp. sequential) transducer. Let C be a congruence class. A C-transducer is a transducer whose underlying automaton is a C-automaton. A transduction is called C-rational (resp. C-sequential) if it is realized by a functional (resp. sequential) C-transducer. Note that a C-rational transduction is sometimes called a C-transduction for short. 2. Algebraic characterization of sequential transductions Sequential transductions can be characterized, as it was shown in [Cho03], by a syntactic congruence which, like for automata, yields a unique minimal underlying machine. Given a congruence class C we thus prove that a sequential transduction is C-sequential if and only if its minimal transducer is a C-transducer, which provides a decision procedure for C-sequentiality in the case of a decidable congruence class. The second result of this section is that a sequential A-transduction is also A-sequential, as determinization preserves aperiodicity. These results are depicted in Figure 1. We describe the minimal sequential transducer given in [Cho03] and refer the reader to the original paper for a proof that the obtained transducer realizes the same transduction. We then show that the underlying automaton of the minimal transducer is minimal in the strong algebraic sense that it is the coarsest among all automata of sequential transducers realizing the same transduction. We will thus obtain a decision procedure for C-sequentiality of sequential transductions: 2In this paper transductions are functions although this term may refer to any relation in the literature. 3This type of transducer is sometimes called real-time [Sak09] since in general a transition of a transducer may be labelled by any word. ##LTLine##

text: E.

text: FILIOT,

text: O.

text: GAUWIN,

text: AND

text: N.

text: LHOTE

text: A

text: transduction

text: over

text: an

text: alphabet

text: Σ

text: is

text: a

text: partial

text: f

text: Σ

text: Σ

text: and

text: its

text: domain

text: is

text: denoted

text: by

text: dom(f).

text: T

text: A

text: A

text: A

text: ﬁnite

text: (or

text: simply

text: transducer)

text: over

text: Σ

text: is

text: a

text: tuple

text: o,

font: YSODGV+URWChanceryL-MediItal

text: i,

text: t)

text: where

text: T

text: (Q,

text: I,

text: F

text: is

text: the

text: underlying

text: automaton

text: of

text: o

text: Σ

text: is

text: the

text: output

text: function,

text: i

text: I

text: Σ

text: is

text: the

text: initial

text: output

text: function

text: and

text: t

text: F

text: Σ

text: is

text: the

text: ﬁnal

text: output

text: function.

text: Let

text: u

text: be

text: a

text: word

text: A

text: on

text: which

text: there

text: exists

text: a

text: run

text: q

text: q|

text: of

text: and

text: let

text: v

text: o(q

text: q

text: o(q|

text: u[

text: u

text: q|

text: u

text: u

text: u

text: −u−→|v

text: then

text: we

text: write

text: q

text: T

text: q|

text: to

text: denote

text: the

text: existence

text: of

text: such

text: a

text: run.

text: If

text: q

text: I

text: and

text: q|

text: F

text: let

text: u

text: T

text: u

text: T

text: w

text: i(q

text: )vt(q|

text: then

text: we

text: say

text: that

text: the

text: pair

text: (u,

text: w)

text: is

text: realized

text: by

text: We

text: denote

text: by

text: the

text: u

text: T

text: set

text: of

text: pairs

text: realized

text: by

text: A

text: transducer

text: is

text: called

text: functional

text: if

text: it

text: realizes

text: a

text: transduction

text: (i.e.

text: a

text: partial

text: function),

text: T

text: this

text: property

text: is

text: decidable

text: in

text: PTime

text: (see

text: e.g.

text: and

text: in

text: this

text: case

text: we

text: denote

text: (u,

text: v)

text: T

text: T

text: by

text: (u)

text: v.

text: A

text: transducer

text: is

text: called

text: unambiguous

text: (resp.

text: sequential)

text: if

text: its

text: underlying

text: T

text: automaton

text: is

text: unambiguous

text: (resp.

text: deterministic)

text: and

text: in

text: both

text: cases

text: is

text: functional.

text: It

text: is

text: known

text: that

text: any

text: functional

text: transducer

text: is

text: equivalent

text: to

text: some

text: unambiguous

text: transducer

text: (see

text: e.g.

text: Finally,

text: a

text: transduction

text: is

text: called

text: rational

text: (resp.

text: sequential)

text: if

text: it

text: is

text: realized

text: by

text: a

text: functional

text: (resp.

text: sequential)

text: transducer.

text: Let

text: C

text: be

text: a

text: congruence

text: class.

text: A

text: C-transducer

text: is

text: a

text: transducer

text: whose

text: underlying

text: automaton

text: is

text: a

text: C-automaton.

text: A

text: transduction

text: is

text: called

text: C-rational

text: (resp.

text: C-sequential)

text: if

text: it

text: is

text: realized

text: by

text: a

text: functional

text: (resp.

text: sequential)

text: C-transducer.

text: Note

text: that

text: a

text: C-rational

text: transduction

text: is

text: sometimes

text: called

text: a

text: C-transduction

text: for

text: short.

text: Algebraic

text: characterization

text: of

text: sequential

text: transductions

text: Sequential

text: transductions

text: can

text: be

text: characterized,

text: as

text: it

text: was

text: shown

text: in

text: by

text: a

text: syntactic

text: congruence

text: which,

text: like

text: for

text: automata,

text: yields

text: a

text: unique

text: minimal

text: underlying

text: machine.

text: Given

text: a

text: congruence

text: class

text: C

text: we

text: thus

text: prove

text: that

text: a

text: sequential

text: transduction

text: is

text: C-sequential

text: if

text: and

text: only

text: if

text: its

text: minimal

text: transducer

text: is

text: a

text: C-transducer,

text: which

text: provides

text: a

text: decision

text: procedure

text: for

text: C-sequentiality

text: in

text: the

text: case

text: of

text: a

text: decidable

text: congruence

text: class.

text: The

text: second

text: result

text: of

text: this

text: section

text: is

text: that

text: a

text: sequential

text: A-transduction

text: is

text: also

text: A-sequential,

text: as

text: determinization

text: preserves

text: aperiodicity.

text: These

text: results

text: are

text: depicted

text: in

text: Figure

text: We

text: describe

text: the

text: minimal

text: sequential

text: transducer

text: given

text: in

text: and

text: refer

text: the

text: reader

text: to

text: the

text: original

text: paper

text: for

text: a

text: proof

text: that

text: the

text: obtained

text: transducer

text: realizes

text: the

text: same

text: transduction.

text: We

text: then

text: show

text: that

text: the

text: underlying

text: automaton

text: of

text: the

text: minimal

text: transducer

text: is

text: minimal

text: in

text: the

text: strong

text: algebraic

text: sense

text: that

text: it

text: is

text: the

text: coarsest

text: among

text: all

text: automata

text: of

text: sequential

text: transducers

text: realizing

text: the

text: same

text: transduction.

text: We

text: will

text: thus

text: obtain

text: a

text: decision

text: procedure

text: for

text: C-sequentiality

text: of

text: sequential

text: transductions:

text: this

text: paper

text: transductions

text: are

text: functions

text: although

text: this

text: term

text: may

text: refer

text: to

text: any

text: relation

text: in

text: the

text: literature.

text: type

text: of

text: transducer

text: is

text: sometimes

text: called

text: real-time

text: since

text: in

text: general

text: a

text: transition

text: of

text: a

text: transducer

text: may

text: be

text: labelled

text: by

text: any

text: word.

text: ##LTLine##