Autosegmental Input Strictly Local Functions
Jane Chandlee
Tri-College Department of Linguistics
Haverford College
jchandlee@haverford.edu
Adam Jardine
Department of Linguistics
Rutgers University
adam.jardine@rutgers.edu
Abstract
Autosegmental representations (ARs; Goldsmith,
1976) are claimed to enable local analyses of
otherwise non-local phenomena (Odden, 1994).
Focusing on the domain of tone, we investigate
this ability of ARs using a computationally
well-defined notion of locality extended from
Chandlee (2014). The result is a more nuanced
understanding of
the way in which ARs
interact with phonological locality.
1
Introduction
Autosegmental representations (ARs; Goldsmith,
1976) have long been claimed to capture non-
local processes in a local way (Odden, 1994).
Focusing on tone, we explore this claim from
a computational perspective using a precisely
defined notion of locality. Specifically, we use
logical
quantifier-free (QF)
transductions, which have been shown (Chandlee
and Lindell, in prep.) in strings to correspond to
the input strictly local (ISL) functions (Chandlee,
2014), a phonologically relevant notion of compu-
tational locality (Chandlee and Heinz, 2018).
first-order (FO)
We extend QF transductions to ARs to de-
fine the autosegmental input strictly local (A-ISL)
functions and give a partial abstract characteriza-
tion of this class. We then examine a variety of
commonly attested tone patterns that are both ISL
and not ISL (i.e., local and non-local in terms of
strings) to see if they are A-ISL (i.e., local over
ARs). Our exploration reveals a four-way division
among tone patterns: those that are local without
ARs (i.e., both ISL and A-ISL), those that are local
only with ARs (i.e., A-ISL but not ISL), those that
are local with strings but not ARs (ISL but not
A-ISL), and those that are not local at all (neither
ISL nor A-ISL). The conclusion is that ARs do
not automatically make non-local processes local,
but that this ability is more nuanced. We also
briefly explore an alternative notion of locality
that extends A-ISL.
The remainder of the paper is structured as
follows. In §2 we review ARs, and in §3 we provide
the mathematical preliminaries. In §4 we define
the ISL functions. §5 extends that characterization
to ARs. §6 presents analyses for a selection of
tone processes, and §7 discusses the significance
of these results and open questions. §8 concludes.
2 Autosegmental Representations
In ARs (Clements, 1976; Goldsmith, 1976) pho-
nological primitives are arranged in distinct strings
or tiers, with an association relation relating
units on different tiers. Examples from Arusa
(Levergood, 1987; Odden, 1994) are shown in
Figure 1, both as strings and as ARs. Here and
throughout the paper, an acute accent [´a] indicates
a high tone; unmarked vowels bear low (L) tones.
In the underlying representation (UR) on the
left-hand side of Figure 1, the second vowel of
/ol´orika/ ‘chair’ bears a H tone, and both vowels
of /s´ıd´ay/ ‘good’ bear a H tone. The AR for /s´ıd´ay/
‘good’ shows a single H on the ‘‘autonomous’’
tonal tier that is associated to both vowels on
the vowel tier. Tones associate to tone-bearing
units (TBUs), which could be vowels, moras, or
syllables depending on the language (Yip, 2002).
ARs have been argued to provide natural
accounts of many tone and segmental processes,
particularly non-local ones. To illustrate, when
preceded by the word [ol´orika] ‘chair’ in the
phrase [ol´orika siday] ‘good chair’, /s´ıd´ay/ ‘good’
is pronounced instead [siday], with two low tones.
This is explained through a map in which the
underlying H tone is deleted following another H
tone in the AR. This is shown schematically in
Figure 1. In terms of the string, this is a non-local
process: The tone of the second vowel in /ol´orika/
affects the tone of the vowels in /s´ıd´ay/, which
are two TBUs away. But in the AR, the process is
157
Transactions of the Association for Computational Linguistics, vol. 7, pp. 157–168, 2019. https://doi.org/10.1162/tacl a 00260.
Action Editor: Eric Fosler-Lussier. Submission batch: 8/2018; Revision batch: 12/2018; Published 4/2019.
c(cid:13) 2019 Association for Computational Linguistics. Distributed under a CC-BY 4.0 license.
l
D
o
w
n
o
a
d
e
d
f
r
o
m
h
t
t
p
:
/
/
d
i
r
e
c
t
.
m
i
t
.
e
d
u
/
t
a
c
l
/
l
a
r
t
i
c
e
–
p
d
f
/
d
o
i
/
.
1
0
1
1
6
2
/
t
l
a
c
_
a
_
0
0
2
6
0
1
9
2
3
3
2
9
/
/
t
l
a
c
_
a
_
0
0
2
6
0
p
d
.
f
b
y
g
u
e
s
t
t
o
n
0
7
S
e
p
e
m
b
e
r
2
0
2
3
Figure 1: AR map from Arusa.
‘‘local’’ because the H tones are adjacent on the
tonal tier.
The computational properties of ARs have been
studied before (Kay, 1987; Wiebe, 1992; Bird
and Ellison, 1994; Kornai, 1995; Jardine, 2017).
However, tone maps, such as the one exemplified
in Figure 1, have not yet been studied under a
computational notion of locality.
3 Preliminaries
3.1 Strings
Let Σ be a finite alphabet of symbols and Σ∗ the
set of all strings over Σ. Let |w| indicate the length
of w ∈ Σ∗. For two strings w and v let wv be their
concatenation, and for a set L ⊆ Σ∗ of strings and
a string w, by wL we denote {wv|v ∈ L}.
The n-suffix of a string w is the last n symbols
of w: Suffn(w) = v such that uv = w and
|v| = n. The prefixes of a string w ∈ Σ∗,
prfs(w) def= {u | w = uv ∈ L for some v ∈
Σ∗}. The common prefixes of a set L ⊆ Σ∗,
w∈L prfs(w). The longest common
cmprfs
prefix of a set L ⊆ Σ∗, is lcp(L)def= u such that
u ∈ cmprfs(L) and ∀u(cid:48) ∈ cmprfs(L), |u| ≥ |v|.
def= (cid:84)
3.2 Models
We consider finite models (Libkin, 2004). A model
is a tuple (cid:104)D; f1, …, fn, R1, …, Rm(cid:105) where D is a
finite domain of elements, f1, …, fn are a set of
functions over the domain, and R1, …, Rm are a
set of relations over the domain. (We do not use
models with constants.) We assume functions to
be unary and relations either unary or binary.
We can talk of a set of models of
the
same signature, where signature refers to a set
S = {f1, …, fn, R1, …, Rn} of named functions
and relations. In particular, we consider models
of strings of the signature {p, s, Pσ∈Σ}, where p
and s are the predecessor and successor functions,
respectively, indicating the order of positions in
the string, and for every σ ∈ Σ there is a unary
relation Pσ indicating the labels of each position.
Figure 2: String model for abba. Upper curved arrows
depict s, lower curved arrows depict p, and the labels
on the nodes depict Pa and Pb.
Figure 2 shows the example of the string abba
represented as a model (cid:104){0, 1, 2, 3}; p, s, Pa, Pb(cid:105)
where: p(0) = 0; for i ∈ {1, 2, 3}, p(i) = i−1; for
i ∈ {0, 1, 2}, s(i) = i + 1; s(3) = 3; Pa = {0, 3};
and Pb = {1, 2}. The first position is its own
predecessor and the last is its own successor, to
encode word boundaries.
3.3 Logics and Transductions
We define transductions from models to models
using logical
interpretations (Courcelle, 1994;
Engelfriet and Hoogeboom, 2001; Filiot and
Reynier, 2016). A fixed signature induces a FO
logical language LS where each variable x is a
term, fi(x) for any function fi ∈ S is a term, and
Ri(t1, …, tk) for any Rj ∈ S and terms t1, …, tk
is an atomic formula. We also allow t1 ≈ t2,
representing equality, as an atomic formula. We
define LS in the usual way. By ϕ(x1, …, xk) we
denote a formula ϕ in LS such that x1, …, xk are
free variables in ϕ. For ϕ(x1, …, xk) and a model
M in the signature, we write M |= ϕ(d1, …, dk)
when ϕ(x1, …, xk) is true in M when x1, …, xk
are evaluated to d1, …, dk in D. For an input
signature I and an output signature O, a logical
transduction τ is a definition of each function and
relation in O in I as follows:1
• A unary predicate ϕD(x) defined in LI;
• For each function f ∈ O, a definition f (x) ≈
y def= ϕf (x, y) for some ϕf (x, y) in LI;
• For each unary relation P ∈ O, a definition
P (x) def= ϕP (x), for some ϕP (x) in LI;
• For each binary relation R ∈ O, a definition
R(x, y) def= ϕR(x, y), for some ϕR(x, y)in LI.
1These definitions are usually relativized over a copy set,
such that the output model may be larger than the input
model, but we abstract away from this.
158
l
D
o
w
n
o
a
d
e
d
f
r
o
m
h
t
t
p
:
/
/
d
i
r
e
c
t
.
m
i
t
.
e
d
u
/
t
a
c
l
/
l
a
r
t
i
c
e
–
p
d
f
/
d
o
i
/
.
1
0
1
1
6
2
/
t
l
a
c
_
a
_
0
0
2
6
0
1
9
2
3
3
2
9
/
/
t
l
a
c
_
a
_
0
0
2
6
0
p
d
.
f
b
y
g
u
e
s
t
t
o
n
0
7
S
e
p
e
m
b
e
r
2
0
2
3
For an input structure MI with domain D
over the signature I, its output τ (MI ) = MO =
(cid:104)D(cid:48); f1, …, fn, R1, …, Rm(cid:105) where
• For each d ∈ D there is a copy d(cid:48) ∈ D(cid:48) iff
MI |= ϕD(d).
• For copies d(cid:48)
1, d(cid:48)
2 ∈ D(cid:48) of some d1, d2 ∈ D
2 iff
1) = d(cid:48)
and for each function f ∈ O, f (d(cid:48)
MI |= ϕf (d1, d2).
• For copy d(cid:48) ∈ D(cid:48) of some d1 ∈ D and
for each unary relation P ∈ O, d(cid:48) ∈ P iff
MI |= ϕP (d).
1, d(cid:48)
1, d(cid:48)
• For copies d(cid:48)
2 ∈ D(cid:48) of some d1, d2 ∈ D
and for each binary relation R ∈ O,
(d(cid:48)
2) ∈ R iff MI |= ϕR(d1, d2).
For example, we can define a string transduction
that takes a string w over Σ = {a, b} and returns a
string w(cid:48) over Σ(cid:48) = {a, b, c} that is identical to w
except that every b following another b is rewrit-
ten as a c. Let S (cid:48) = {p(cid:48), s(cid:48), P (cid:48)
c} be the
signature for strings over Σ(cid:48). Then let τ be de-
fined as ϕD(x) def= True, ϕs(cid:48)(x, y) def= s(x) ≈ y
a(x) def= Pa(x),
ϕp(cid:48) (x, y) def= p (x) ≈ y, ϕP (cid:48)
c(x) def=
ϕP (cid:48)
Pb(x) ∧ Pb(p(x)), where True is any unary
predicate that is always true for models in S.
(x) def= Pb(x) ∧ ¬ Pb(p(x)), and ϕP (cid:48)
a, P (cid:48)
b, P (cid:48)
b
In this transduction, ϕP (cid:48)
(x) is only true for input
b
positions labeled b that do not follow another b;
c(x) is only true for input positions
conversely, ϕP (cid:48)
labeled b that do follow another b. Thus, for
example, the output under τ for the string model
for abba from Figure 2 is a model for abca as
shown in Figure 3.
As ϕD(x) is set to True, τ copies every input
element. Furthermore, the definitions of ϕs(cid:48)(x, y)
and ϕp(cid:48)(x, y) mean that p(cid:48) and s(cid:48) are identical to
a(x) is defined
s and p in the input. Similarly, ϕP (cid:48)
to mirror Pa. Thus, the only change is made to bs
following other bs, which are written out as cs.
In the definitions that follow, we will often omit
formulas for relations and functions whose defi-
nition is True or identical to their input formula
(as in ϕD(x), p(cid:48), and s(cid:48) in the above example).
Figure 3: Output model under τ as defined above given
the model from Figure 2, where each element i(cid:48) is a
copy of i from Figure 2.
159
4
Input Strictly Local String Transductions
We now connect logical transductions to the ISL
class. A proper subset of the regular relations,
the ISL functions determine an output string for
a given input string based only on contiguous
substrings of bounded length (Chandlee, 2014;
Chandlee et al., 2014). This means that
the
computation of the output string is based on a
very limited amount of information present in the
input, and that information is locally contained
(i.e., within a bounded window around the current
position) rather than ‘‘global’’ in nature (i.e.,
referring to some property of the entire string).
This limitation on the information available to
the function is what establishes ISL as a proper
subclass of the regular relations (i.e., not all
string-to-string relations can be computed with
such limited information). Despite its reduced
expressivity, ISL can model a significant range
of local segmental phonological maps and has
been argued to provide a well-defined notion of
phonological locality (Chandlee and Heinz, 2018).
Chandlee (2014) gives the ISL functions an
abstract characterization based on the notion of
the tails of a string x with
tails. Informally,
respect to a function f is a set of strings (y, v)
where y is a possible ‘‘input extension’’ of x and
v is the contribution to the output string that y
itself is responsible for. Formally: tailsf (x) =
{(y, v) | f (xy) = uv ∧ u = lcp(f (xΣ∗))}. The
abstract characterizations of ISL functions is given
in Definition 1.
Definition 1 (Input Strictly Local Function)
A function f is ISL iff there is a k such that for
all u1, u2 ∈ Σ∗, if Suffk−1(u1) = Suffk−1(u2)
then tailsf (u1) = tailsf (u2).
If two strings share a (k − 1)-suffix but have
different sets of tails, the function is not k-ISL, a
fact we use in some of the analyses to follow.
Chandlee and Lindell (in prep.) provide a
logical characterization of ISL functions as those
functions which can be described by quantifier-
free (QF) FO string transductions. A QF transduc-
tion τ is a FO transduction such that no quantifiers
appear in any formulas in τ (as in the example in
the previous section).
QF logical transductions can be applied not only
to strings but to models in general. We can thus
use them as a general notion of locality to compare
strings and ARs. We first view tone patterns as
l
D
o
w
n
o
a
d
e
d
f
r
o
m
h
t
t
p
:
/
/
d
i
r
e
c
t
.
m
i
t
.
e
d
u
/
t
a
c
l
/
l
a
r
t
i
c
e
–
p
d
f
/
d
o
i
/
.
1
0
1
1
6
2
/
t
l
a
c
_
a
_
0
0
2
6
0
1
9
2
3
3
2
9
/
/
t
l
a
c
_
a
_
0
0
2
6
0
p
d
.
f
b
y
g
u
e
s
t
t
o
n
0
7
S
e
p
e
m
b
e
r
2
0
2
3
ISL string functions, then use QF transductions
in §5 to define A-ISL functions over ARs and in
§6 to compare and contrast ISL with A-ISL with
respect to a variety of tone patterns.
4.1 Bounded Tone Shift is ISL
We thus first illustrate the ISL class of local
string functions by analyzing some example tone
patterns. To do this, we analyze these patterns as
functions operating over strings of TBUs.
In all of the analyses that follow, the goal is
to isolate tone processes in order to classify them
individually in terms of the notions of ISL/A-ISL.
In some cases this isolation requires certain
restrictions on the input forms, and we will note
those assumptions in each case. We will briefly
discuss in §7 how the interaction of multiple tone
processes can affect computational classification,
though a complete answer to that question will
ultimately be left for future work.
First, we contrast bounded shift and unbounded
shift. In bounded shift a tone appears some
fixed number of TBUs away from its underlying
position. In Rimi (Meyers, 1997), a tone shifts one
TBU to the right. In Example (1), /−a/, /−mu/,
and /−i¸/ have a L tone but surface with an H when
the preceding vowel is underlyingly high.
(1)
Rimi (Schadeberg, 1979; Meyers, 1997)
a.
(cid:55)→ [u-pu¸m-´a]
‘to go
/u-p´u¸m-a/
away’
/r´a-mu-ntu/ (cid:55)→ [ra-m´u-ntu]
person’
/mu-t´em-i¸/ (cid:55)→ [mu-tem-´ı¸]
‘of a
‘chief’
b.
c.
this pattern as a string
We can represent
transduction with an alphabet Σ = {∅, H}, where
∅ is an ‘‘unspecified’’ or toneless TBU (as in the
first vowel in Example (1a)) and H is a high-toned
TBU.2 Using this notation, the examples from (1)
are as below in Example (2).
(2)
a. ∅H∅ (cid:55)→ ∅∅H
b. H∅∅ (cid:55)→ ∅H∅
In general, then, the Rimi case is the function
below. Here, to isolate the shifting process we
restrict our domain to strings with one underlying
H, as in Rimi sequences of successive H tones
2This abstracts away from consonants, consistent with the
assumption that tone operates over prosodic units and usually
does not interact with segmental information (Yip, 2002).
160
are subject to other rules (see Meyers, 1997). This
also assumes a final H does not shift.
∅mH∅n (cid:55)→ ∅m+1H∅n−1 for n > 0,
∅mH (cid:55)→ ∅mH
This is easily defined with the QF transduction
below, where the predicates ∅(x) and H(x) refer
to input position labels and ∅(cid:48)(x) and H(cid:48)(x)
label the output positions. first(x) def= p(x) ≈ x
and last(x) def= s(x) ≈ x, and the successor/
predecessor functions are unchanged from the
input: s(cid:48)(x) def= s(x) and p(cid:48)(x) def= p(x).
∅(cid:48)(x)
def= ∅(p(x)) ∨ first(x)∧
H(cid:48)(x)
¬(last(x) ∧ H(x)),
def= (H(p(x)) ∧ ¬first(x))∧
∨(last(x) ∧ H(x))
For an input position x, its corresponding out-
put position is labled ∅ only if x’s predecessor is
labeled ∅ or if x was the first position (and not
the final H). Conversely, x’s corresponding output
position is labeled H if its predecessor is an H or
if x is the last position and is an H. In this way, the
‘‘shifting’’ behavior is captured by determining the
output label of each position via the predecessor
of its corresponding input position. Thus, bounded
tone shift is QF-definable and so ISL.
4.2 Unbounded Tone Shift is Not ISL
In contrast, unbounded tone shift is not ISL. In
unbounded shift, underlying tones move some
arbitrary distance to another fixed position. One
example is in Zigula.
(3)
Zigula (Kenstowicz and Kisseberth, 1990)
a.
b.
c.
d.
ku-gulus-a ‘to chase’
ku-lomb´ez-a ‘to ask’
ku-lombez-´ez-a ‘to ask for’
ku-lombez-ez-´an-a ‘to ask for e. o.’
The contrast between Example (3a) and (3b)
shows that roots must underlyingly contrast in
this tone does not appear in
tone. However,
this underlying position, but instead shifts to the
penultimate TBU, as demonstrated dramatically
by Example (3d).
Following the string representation scheme, we
can represent this as the following function. Here,
l
D
o
w
n
o
a
d
e
d
f
r
o
m
h
t
t
p
:
/
/
d
i
r
e
c
t
.
m
i
t
.
e
d
u
/
t
a
c
l
/
l
a
r
t
i
c
e
–
p
d
f
/
d
o
i
/
.
1
0
1
1
6
2
/
t
l
a
c
_
a
_
0
0
2
6
0
1
9
2
3
3
2
9
/
/
t
l
a
c
_
a
_
0
0
2
6
0
p
d
.
f
b
y
g
u
e
s
t
t
o
n
0
7
S
e
p
e
m
b
e
r
2
0
2
3
we restrict the domain to strings with at most
one H (as, like in Rimi, multiple H tones trigger
other processes; interested readers are referred to
Kenstowicz and Kisseberth, 1990).
(cid:55)→∅n
∅n
∅mH∅n(cid:55)→∅m+n−1H∅
There is no QF transduction for this map.
Lemma 1 The Zigula map is not ISL.
Proof: Let f be the Zigula map. For any k, and
for any n ≥ k, the strings H∅n and ∅n have the
same (k − 1)-suffix: ∅k−1. However, their tails
differ. First, lcp(f (H∅nΣ∗)) = ∅n−1, because
f (H∅nλ) = ∅n−1H∅ but f (H∅n∅) = ∅nH∅;
the longest prefix these outputs share is ∅n−1.
Thus (λ, H∅) ∈ tailsf (H∅n). However, clearly
(cid:3)
(λ, H∅) (cid:54)∈ tailsf (∅n).
These two examples show how the ISL property
can be used to formalize the notion of ‘‘locality’’
in tone. The shift pattern in Rimi is ISL, whereas
the shift pattern in Zigula is not ISL.
5 Autosegmental ISL Transductions
In this section we demonstrate how using an AR
model instead of a string model allows us to
capture some phenomena with QF transductions
when we wouldn’t otherwise be able to do so.
First, we define AR models.
5.1 Autosegmental Models
Autosegmental models include two strings, a
string of TBUs (e.g., vowels, syllables, moras)
and a string of tones. The positions of these strings
are related to each other by the successor and
predecessor functions, just as in string models. In
addition, the association relation relates positions
from the tone string to positions of the TBU
string. We thus have the signature in Example (4),
where D is the domain, p and s are the successor
functions, and A is the association relation.
(4)
(cid:104)D; p, s, A, PH , PV (cid:105)
An example is shown in Figure 4, with an explicit
model for the underlying Arusa phrase /ol´orika
s´ıd´ay/ ‘good chair’ from Figure 1 (for the sake of
simplicity, word boundaries have been omitted).
Figure 4 depicts a model with the domain
{0, 1, 2, 3, 4, 5, 6, 7} and the association relation
Figure 4: Example of an autosegmental model.
a = {(6, 1), (7, 3), (7, 4)} relating tones to their
TBUs. Whereas some authors define association
as symmetric (Kornai, 1995), to simplify the for-
mulas in our analyses we define it as anti-
symmetric, although this assumption has no
bearing on QF-definability. Note that association
only holds between the tiers: Elements on the same
tier cannot be associated. Also, for ease of reading
we will represent AR models in the remainder of
the paper as originally presented in Figure 1 (i.e.,
without the nodes, position numbers, successor
relation, and predecessor relation pictured).
Furthermore, we use notation following that
for strings. First, for any ARs w and v, we
denote by w · v the concatenation of w and v;
that is, the concatenation of each tier of w to its
corresponding tier in v, preserving all association
lines (see Example (5)).
(5)
This allows us to use the usual conventions from
strings: For an AR w, wn represents the AR
consisting of n repetitions of w; w0 is the empty
AR whose tiers are both λ and thus has no
association lines. Let Γ∗ refer to the set of all
ARs. We also use the abbreviations below in
Example (6),
(6)
We will classify patterns that can be analyzed with
QF FO formulas as A-ISL when the model is an
autosegmental model instead of a string model.
Definition 2 An input–output map is A-ISL if it
can be described with a QF transduction where
the model is an AR model.
161
l
D
o
w
n
o
a
d
e
d
f
r
o
m
h
t
t
p
:
/
/
d
i
r
e
c
t
.
m
i
t
.
e
d
u
/
t
a
c
l
/
l
a
r
t
i
c
e
–
p
d
f
/
d
o
i
/
.
1
0
1
1
6
2
/
t
l
a
c
_
a
_
0
0
2
6
0
1
9
2
3
3
2
9
/
/
t
l
a
c
_
a
_
0
0
2
6
0
p
d
.
f
b
y
g
u
e
s
t
t
o
n
0
7
S
e
p
e
m
b
e
r
2
0
2
3
The structure of ARs and the nature of QF
transductions gives us the following necessary
(but not sufficient) property of A-ISL maps.
Theorem 1 If a AR map is A-ISL,
individual map on each tier is an ISL function.
then the
Proof: (Sketch.) For any tier w in an AR, the
output for each position in w will depend on some
QF formula ϕ(x) with exactly one free variable.
Because ϕ(x) is QF, no other variables can be
introduced, thus for any A(t1, t2) that appears in
ϕ(x), both t1 and t2 must be of the form p(…p(x))
or s(…s(x)); that is, t1 and t2 represent members
of the same tier. Since members of the same
tier are never associated to each other, A(t1, t2)
will always evaluate to False. This essentially
reduces ϕ(x) to a QF formula over the string
(cid:3)
signature for that tier.
As every map that is A-ISL satisfies Theorem 1,
we use it below to prove some maps are not A-ISL.
However, although Theorem 1 is a necessary
condition for A-ISL maps, it is not a sufficient
condition. In §6.5 we show that an unbounded
spreading map satsifies Theorem 1 but is not
A-ISL. Briefly,
this is because defining the
associations in unbounded spreading cannot be
defined with QF formulas. Thus, A-ISL maps are
also restricted in how associations can change
from input to output. While a full abstract char-
acterization of A-ISL must also express these
constraints, for concerns of space we save this for
future work.
5.2 Bounded Tone Shift is A-ISL
Rimi bounded tone shift was already analyzed as
ISL in §4.1. It is also A-ISL. When viewed as a
function from ARs to ARs, it is as given below.
Figure 5 shows an AR model representing the
map from Example (1a).
Figure 5: AR representation of bounded shift in Rimi.
162
We can define this map with a QF transduction.
As nothing changes with respect to position label-
ing or the successor and predecessor functions for
either string, we only give the association relation.
(7)
A(cid:48)(x, y) def= (A(x, p(y)) ∧ ¬first(y))∨
(last(y) ∧ A(x, y))
Informally, the formula in (7) states that positions
x and y are associated in the output model if x
is associated to the predecessor of y in the input
model, or if x is associated to y in the input and y
is final (because, as with the string representation,
we assume that a final H cannot shift). Thus, the
bounded shift pattern in Rimi, which was ISL
given a string representation, is also A-ISL.
5.3 Unbounded Tone Shift is A-ISL
Zigula unbounded tone shift is also A-ISL. Again,
in this pattern a H tone shifts to the penultimate
position in the word. This map is shown in
Figure 6, which gives an example for the mapping
from Example (3d).
Figure 6: ARs for unbounded shift in Zigula.
This is A-ISL, as it simply requires identifying
the penultimate vowel and associating that with a
H tone. First, we define a predicate penult(x),
which is true for the second-to-last item in a string:
(8)
penult(x) def= ¬last(x) ∧ last(s(x))
The relevant formula for this map is again
A(cid:48)(x, y); we omit the other formulas. We define
this to be when y is the penultimate vowel:3
(9)
A(cid:48)(x, y) def= H(x) ∧ penult(y)
Unbounded shift provides an example of a map
that is A-ISL but not ISL. We thus have one
3In general, it is the last H tone that shifts to the end of the
word (Kenstowicz and Kisseberth, 1990). To accommodate
multiple H tones, this condition can be added to the definition
in Equation (9) with the last(x) predicate.
l
D
o
w
n
o
a
d
e
d
f
r
o
m
h
t
t
p
:
/
/
d
i
r
e
c
t
.
m
i
t
.
e
d
u
/
t
a
c
l
/
l
a
r
t
i
c
e
–
p
d
f
/
d
o
i
/
.
1
0
1
1
6
2
/
t
l
a
c
_
a
_
0
0
2
6
0
1
9
2
3
3
2
9
/
/
t
l
a
c
_
a
_
0
0
2
6
0
p
d
.
f
b
y
g
u
e
s
t
t
o
n
0
7
S
e
p
e
m
b
e
r
2
0
2
3
example where a pattern that is ‘‘non-local’’ in
terms of strings is ‘‘local’’ when viewed in terms
of ARs.
as a H tone associating to the TBU following the
TBU to which it is associated in the input:
6 Analyses
In this section we apply our definitions of ISL
and A-ISL to analyze a range of tone phenomena,
including examples that (1) are ISL and A-ISL,
(2) A-ISL but not ISL, (3) ISL but not A-ISL, and
(4) neither ISL nor A-ISL.
As before, to analyze the processes in isolation,
in some cases we assume restrictions on the
underlying forms (i.e., the domain of the maps).
We note in these cases any such assumptions.
6.1 Bounded Tone Spread
In bounded tone spread a tone on one TBU
associates to some fixed number of TBUs. In
Northern Bemba (Bickmore and Kula, 2013,
henceforth Bemba), an underlying H tone spreads
to the next vowel, but does not spread any further.4
(10)
Bemba (Bickmore and Kula, 2013)
/b´a-ka-fik-a/ (cid:55)→ [b´a-k´a-fik-a]
a.
‘they will arrive’
/b´a-ka-bil-a/ (cid:55)→ [b´a-k´a-bil-a]
‘they will sew’
b.
In terms of strings, this map is as follows (n > 0):
f (w) def=
(cid:26) w
if w = ∅mH
∅mHH∅n−1 if w = ∅mH∅n
This map is ISL, as witnessed by the trans-
duction defined by the following formulas.
(11)
H(cid:48)(x) def= H(x) ∨ H(p(x))
∅(cid:48)(x) def= ∅(x) ∧ ¬H(p(x))
The first of these formulas states that a position is
H in the output if either it was H in the input or its
predecessor was H in the input. The second states
the opposite: A position is ∅ in the output if it was
a ∅ in the input and its predecessor was not H.
This map is also A-ISL. In terms of an auto-
segmental map, this process can be represented
We can focus on the definition of the output
association relation, as nothing else changes.
(12)
A(cid:48)(x, y) def= A(x, y) ∨ A(p(x), y)
Informally, (12) says that positions x and y are
associated in the output if either (1) they are
associated in the input, or (2) the predecessor of x
is associated to y in the input.This allows a H to
spread to exactly one following TBU (if it exists).
Thus, bounded spread is both ISL and A-ISL.
6.2 Unbounded Deletion
We now turn to an example that is A-ISL but
in Arusa (Odden, 1994;
not ISL. Recall
Levergood, 1987) a phrase-final H is deleted fol-
lowing (any number of syllables after) another H:
that
(13)
Arusa (Odden, 1994)
a.
/enk´er kit´ı/ (cid:55)→ [enk´er kiti]
‘small ewe’
/ol´orika s´ıd´ay/ (cid:55)→ [ol´orika siday]
‘good chair’
b.
In this map, a stretch of Hs are converted to ∅
following some distinct stretch of H symbols—
distinct here meaning that they are separated by
some stretch of ∅s. However, a stretch of Hs is not
converted if it does not follow some other distinct
stretch of Hs.
(14)
a. HH (cid:55)→ HH
b. ∅H (cid:55)→ ∅H
c. ∅H∅H (cid:55)→ ∅H∅∅
d. ∅H∅∅HH (cid:55)→ ∅H∅∅∅∅
The map can be generalized as
f (w) def=
if w = ∅(cid:96)Hm∅n
w
v∅(cid:96)∅m∅n if w = v∅(cid:96)Hm∅n,
v ∈ Σ∗HΣ∗, (cid:96) > 0
4This is also referred to as ‘‘binary tone spread’’ or ‘‘tone
doubling’’ (Bickmore and Kula, 2013). Copperbelt Bemba
has ‘‘ternary spread,’’ which is also considered bounded.
Bounded spread in Bemba is blocked by the OCP, but we
abstract away from that here (though including this constraint
would not change the fact that the pattern is ISL and A-ISL).
Lemma 2 The Arusa map is not ISL.
Proof: Let f be the Arusa map. For any k, con-
sider the two strings H∅k−1 and ∅k−1. These
strings have the same (k − 1)-suffix, but their
163
l
D
o
w
n
o
a
d
e
d
f
r
o
m
h
t
t
p
:
/
/
d
i
r
e
c
t
.
m
i
t
.
e
d
u
/
t
a
c
l
/
l
a
r
t
i
c
e
–
p
d
f
/
d
o
i
/
.
1
0
1
1
6
2
/
t
l
a
c
_
a
_
0
0
2
6
0
1
9
2
3
3
2
9
/
/
t
l
a
c
_
a
_
0
0
2
6
0
p
d
.
f
b
y
g
u
e
s
t
t
o
n
0
7
S
e
p
e
m
b
e
r
2
0
2
3
tails clearly differ: (H, ∅) ∈ tailsf (H∅k−1),
(cid:3)
whereas (H, H) ∈ tailsf (∅k−1).
As we saw in Figure 1, given ARs the Arusa
map deletes a final H that follows another H. The
full map is thus
f (w)def= w otherwise.
As defined in §3.3, an output copy of an input
position x is present if x satisfies a unary predicate
ϕD(x) establishing the domain of the output.
Deletion is the failure of an input position to
satisfy this formula. For Arusa, then, ϕD(x) is
true only for vowels and all but the last H.
(15)
ϕD(x) def= V(x) ∨ (cid:0)H(x) ∧ (first(x) ∨
¬last(x))(cid:1)
Any final H node in the AR that is not first will
fail ϕD(x) and delete, regardless of the number
of vowels between it and the preceding H. Thus
unbounded deletion is A-ISL but not ISL.
6.3 Bounded Meussen’s Rule
Meussen’s rule is an alternation in which a H tone
adjacent to a H tone either deletes or lowers to L
(the deletion in Arusa in the previous section
can be considered a form of Meussen’s). An
example from Luganda is shown in (16). Luganda
distinguishes between H vowels ([´a]), L vowels
([`a]), and unspecified vowels ([a]).5
(16)
Luganda (Hyman and Katamba, 2010)
/b´al´aba/ → [b´al`aba] ‘they see’
a.
/b´al´ıl´aba/ → [b´al`ıl`aba], ‘they will
b.
see’
/ab´at´al´ıl´abilila/ → [ab´at`al`ıl`abilila]
‘they who will not look after’
/b´akil´aba/ → [b´akil´aba] ‘they see it’
d.
c.
because it only applies to H tones that appear on
adjacent vowels. Thus, Example (16d) surfaces
as [b´akil´aba], not *[b´akil`aba], because the two H
tones are separated by one vowel. The map is thus
as below (n > 0).
f (w) def=
(cid:26) w
if w = {∅, L}m
f (v)H Ln−1 if w = vHn, v (cid:54)∈ Σ∗H
Although this applies to a sequence of Hs of any
length, it is in fact ISL, because each H vowel only
needs to ‘‘look’’ one vowel to its left in the input.
Thus, the map can be defined with the following
QF formulas.
(17)
H(cid:48)(x) def= H(x) ∧ ¬H(p(x))
L(cid:48)(x) def= H(x) ∧ H(p(x))
∅(cid:48)(x) def= ∅(x)
Bounded Meussen’s is therefore ISL, but
interestingly, it is not A-ISL, at least given the
representations of Hyman and Katamba (2010). If
each vowel in a sequence of H tones is associated
to its own H tone (as opposed to a single, spreading
H tone), the AR map for Luganda is as follows.
l
D
o
w
n
o
a
d
e
d
f
r
o
m
h
t
t
p
:
/
/
d
i
r
e
c
t
.
m
i
t
.
e
d
u
/
t
a
c
l
/
l
a
r
t
i
c
e
–
p
d
f
/
d
o
i
/
.
1
0
1
1
6
2
/
t
l
a
c
_
a
_
0
0
2
6
0
1
9
2
3
3
2
9
/
/
t
l
a
c
_
a
_
0
0
2
6
0
p
d
.
f (w)def= w otherwise.
Recall that there is a distinction between a
sequence of H tones that are associated to adjacent
TBUs and H tones that are not associated to
adjacent TBUs—the latter do not change to L.
(18)
f
b
y
g
u
e
s
t
t
o
n
0
7
S
e
p
e
m
b
e
r
2
0
2
3
As seen clearly in Example (16), a series of
H vowels of length n will surface as a HLn−1
sequence. We call this bounded Meussen’s rule
5Following Hyman and Katamba (2010), these output
forms are intermediate and subject to other processes.
The map is thus not A-ISL.
164
Lemma 3 The Bounded Meussen’s rule map is
not A-ISL.
simplify, in lieu of boundaries we will just assume
one tone per morpheme, as follows:
Proof: As is clear from the above example, the
string map on the tonal tier is not a function:
HH may be mapped to either HH or HL. Thus,
it is not ISL, and so the map is not A-ISL by
(cid:3)
Theorem 1.
Intuitively, this distinction cannot be made only
by referring to the predecessor function on the
tonal tier: in each of (18), (18b), and (18c), the
first H is the predecessor of the second. Thus,
we cannot use predicates as in (17). Instead,
the distinction is based on associations to TBUs.
In order to refer to these, we must refer to the
associations to TBUs. However, as A is a relation,
this requires introducing new variables, which is
impossible to do without introducing quantifiers.
6.4 Alternating Meussen’s Rule
We now turn to a case in Shona, in which repeated
application of Meussen’s rule leads to surface
strings of alternating H and L tones.
(19)
Shona (Odden, 1986)
a.
b.
/n´e-h´ov´e/ (cid:55)→ [n´e-h`ov`e] ‘with-fish’
/n´e-´e-h´ov´e/ (cid:55)→ [n´e-`e-h´ov´e]
‘with-of-fish’
/n´e-´e-´e-h´ov´e/ (cid:55)→ [n´e-`e-´e-h`ov`e]
‘like-with-of-fish’
c.
The examples in (19) present an interesting
challenge in how to view this pattern in terms of
strings. Under the assumption that each morpheme
gets a single tone, an input like HHH is actually
ambiguous without the morpheme boundaries. If
HHH corresponds to H+HH, as in Example (19a),
then the output is LHH. But if HHH corresponds to
HH+H the output is HHL. So without morpheme
boundaries the map isn’t even a function and
therefore is trivially not ISL.
With morpheme boundaries we see the alter-
nating H/L pattern across the boundary. The
tone sequences for the examples in (19) are as
follows:
(20)
a. H+HH (cid:55)→ H+LL
b. H+H+HH (cid:55)→ H+L+HH
c. H+H+H+HH (cid:55)→ H+L+H+LL
Even with the boundaries represented, however,
we can show that the map is still not ISL. To
(21)
a. HH (cid:55)→ HL
b. HHH (cid:55)→ HLH
c. HHHH (cid:55)→ HLHL
In contrast to the bounded Meussen’s rule case we
saw in Luganda in §6.3, in which any H following
another H in the input surfaces as L, here an H only
surfaces as L if its predecessor was an H in the
input that also surfaces as L in the output. Thus,
whereas in Luganda a HHHH sequence surfaces
as HLLL, in Shona it surfaces as HLHL.
Abstracting away from unspecified TBUs, this
function is as follows.
f (w)def=
f (v) L
f (v)(H L)n
f (v)(H L)nH if w = v(HH)nH,
if w = v L
if w = v(HH)n, v (cid:54)∈ Σ∗H
v (cid:54)∈ Σ∗H
Lemma 4 The Shona map is not ISL.
Proof: Let f be the Shona map. For any even
k, (H, L) ∈ tailsf (HHk−1), but (H, H) ∈
tailsf (Hk−1), even though the two strings share
the (k − 1)-suffix Hk−1. Thus, f is not ISL
for any even k. The case in which k is odd is
(cid:3)
similar.
Intuitively, an H surfaces as L if it is an even-
numbered position in a string of Hs. Determining
odd and even positions in a string is not even
FO-definable (McNaughton and Papert, 1971).
Adopting ARs does not change this fact, as we
still need to determine even-numbered H tones on
the tonal tier, as in the following example.
(22)
Lemma 5 The Shona map is not A-ISL.
Proof: The map on the tonal tier is identical
to the above string map, which is not ISL. By
(cid:3)
Theorem 1, then, the AR map is not A-ISL.
This is thus an important illustration of the core
concept of this paper: From an intuitive sense
of ‘‘local’’ one might assume that this pattern is
A-ISL, but given our rigorous definition it is not.
165
l
D
o
w
n
o
a
d
e
d
f
r
o
m
h
t
t
p
:
/
/
d
i
r
e
c
t
.
m
i
t
.
e
d
u
/
t
a
c
l
/
l
a
r
t
i
c
e
–
p
d
f
/
d
o
i
/
.
1
0
1
1
6
2
/
t
l
a
c
_
a
_
0
0
2
6
0
1
9
2
3
3
2
9
/
/
t
l
a
c
_
a
_
0
0
2
6
0
p
d
.
f
b
y
g
u
e
s
t
t
o
n
0
7
S
e
p
e
m
b
e
r
2
0
2
3
Pattern
Bounded shift (§4.1, 5.2)
Bounded spread (§6.1)
Bounded Meussen’s Rule (§6.3)
Unbounded shift (§4.2,5.3)
Unbounded deletion (§6.2)
Alternating Meussen’s Rule (§6.4)
Unbounded spread (§6.5)
Language
ISL A-ISL
(cid:33)
Rimi
(cid:33)
Bemba
Luganda (cid:33)
(cid:55)
Zigula
(cid:55)
Arusa
(cid:55)
Shona
(cid:55)
Ndebele
(cid:33)
(cid:33)
(cid:55)
(cid:33)
(cid:33)
(cid:55)
(cid:55)
Table 1: Summary of analyses.
6.5 Unbounded Tone Spread
Lemma 7 The Ndebele map is not A-ISL.
Next, we examine unbounded tone spread, in
which a tone spreads any number of TBUs until
reaching a particular position in the word. For
example,
in Ndebele (Sibanda, 2004; Hyman,
2011), a high tone spreads up to the antepenult.
(23)
Ndebele (Sibanda, 2004; Hyman, 2011)
/´u-ku-hlek-a/ (cid:55)→ [´u-k´u-hlek-a]
a.
‘to laugh’
/´u-ku-hlek-is-a/ (cid:55)→ [´u-k´u-hl´ek-is-a]
‘to amuse (make laugh)’
/´u-ku-hlek-is-an-a/ (cid:55)→ [´u-k´u-hl´ek-´ıs-
‘to amuse each other’
an-a]
b.
c.
Assuming inputs with at most a single H, this
function changes any number of ∅s (minus the
final two) to H following an input H.
f (w)def=
(cid:40)∅mHHn−2∅2 if w = ∅mH∅n, n > 1;
w
otherwise.
Lemma 6 The Ndebele map is not ISL.
Proof: Let f be the Ndebele map. For any k, the
strings H∅k−1 and ∅k−1 have the same (k − 1)-
suffix, but (H, ∅) ∈ tailsf (H∅k−1), whereas
(cid:3)
(H, H) ∈ tailsf (∅k−1).
Interestingly, the use of ARs instead of strings
makes no difference. In an AR map, we have a
single underlying H tone associating to all TBUs
to its right, with the exception of the final two
TBUs. The following is an AR for Example (23c),
with the general map below.
f (w) def= w otherwise.
166
Proof: In the case that w is an AR with m Vs,
followed by a single V associated to a H, followed
then by n > 1 Vs, the map must associate the
first n − 2 of this latter set of Vs to the H. This
requires determining the set of Vs that are pre-
ceded (≤) by the originally associated V. As it is
well known that precedence cannot be defined in
FO logic from successor (see, e.g., Libkin 2004),
(cid:3)
this predicate cannot be QF-definable.
Interestingly, the Ndebele map is not A-ISL not
because its composite tier maps are not ISL—no
changes are made to the strings on either tier.
Rather, it is not A-ISL strictly due to the output
association relation not being QF-definable.
6.6 Summary
This section has presented analyses of a range
of tone patterns, including ones that are ISL and
A-ISL, patterns that are ISL but not A-ISL, pat-
terns that are A-ISL but not ISL, and patterns that
are neither. These results are summarized in Table 1.
7 Discussion
The goal of this paper has been to apply a rigorous,
independently motivated notion of locality to
investigate the notion that ARs ‘‘make non-local
patterns local.’’ The fact that in Table 1 common
tone patterns fill out the logical possibilities of
ISL and A-ISL shows that this statement is not
automatically true. In fact, we found some patterns
that look intuitively ‘local’ with ARs but, under
a rigorous definition, are not. This opens up a
rich line of investigation into what definitions of
locality allow ARs to ‘‘make non-local patterns
local,’’ and under what conditions these definitions
hold.
For example, we have taken the approach of
analyzing tone processes in isolation, but it is also
l
D
o
w
n
o
a
d
e
d
f
r
o
m
h
t
t
p
:
/
/
d
i
r
e
c
t
.
m
i
t
.
e
d
u
/
t
a
c
l
/
l
a
r
t
i
c
e
–
p
d
f
/
d
o
i
/
.
1
0
1
1
6
2
/
t
l
a
c
_
a
_
0
0
2
6
0
1
9
2
3
3
2
9
/
/
t
l
a
c
_
a
_
0
0
2
6
0
p
d
.
f
b
y
g
u
e
s
t
t
o
n
0
7
S
e
p
e
m
b
e
r
2
0
2
3
worth considering what happens to complexity
when multiple processes are combined and interact
in some way. Mathematically, this involves in-
vestigating whether or not the A-ISL class is
closed under composition.
Another important question is what notion of
locality might include the non-A-ISL patterns in
Shona and Ndebele in §§6.4 and 6.5. One potential
solution is the use of implicit definitions (Rogers,
1997). Briefly,
implicit definitions allow the
recursive definition of a predicate. For example,
for unbounded spreading, as in Ndebele, we could
define the output association relation as follows.
A(cid:48)(x, y) def= A(x, y) ∨ A(cid:48)(p(x), y)
This is a recursive definition in that any pair
x, y that are associated is the base case (A(x, y)),
and in the recursive case the predecessor of x
is associated in the output to y (A(cid:48)(p(x), y)).
This predicate thus iteratively adds associations
following an initial input association, much in
the way that phonologists have characterized
unbounded spread as the iterative application of
local spread. A full study of such definitions, and
whether or not they are decidable for ARs, is left
for future work.
Finally, a full exploration of the A-ISL class
should situate it in the sub-regular (i.e., describable
with finite-state transducers) hierarchy of com-
putational complexity as has been done in pre-
vious work on phonological complexity (e.g.,
Gainor et al., 2012; Heinz and Lai, 2013; Jardine,
2016, among others). We conjecture that A-ISL
falls between the regular and ISL functions.
As some tone patterns were neither ISL or
A-ISL, this raises the question of whether or
not QF transductions are appropriate as a com-
putational notion of locality. Clearly, on their
own, QF transductions with a successor do not
capture all phonological patterns, even over ARs.
However,
they do implement a fundamental
notion of locality, which is that computations
can only occur within some fixed window. We
thus believe that a final computational theory of
phonological processes will somehow incorporate
QF definitions—one example is the implicit
definitions mentioned above.
8 Conclusion
We have introduced the A-ISL class of maps,
which are defined through QF transductions
over ARs, and compared them with ISL string
functions with respect to common tone processes.
Our results point to a further division among
‘‘unbounded’’ or ‘‘non-local’’ phenomena into
those that are A-ISL and those that cannot be
modeled locally even with the use of ARs. This
adds to our understanding of the computational
nature of tonal processes and how they are
represented.
References
Lee S. Bickmore and Nancy C. Kula. 2013.
Ternary spreading and the OCP in Copperbelt
Bemba. Studies in African Linguistics, 42.
Steven Bird and T. Mark Ellison. 1994. One-level
phonology: Autosegmental representations and
rules as finite automata. Computational Ling-
uistics, 20.
Jane Chandlee. 2014. Strictly Local Phonological
Processes. Ph.D. thesis, University of Delaware.
Jane Chandlee, R´emi Eyraud, and Jeffrey Heinz.
2014. Learning Strictly Local subsequential
functions. Transactions of the Association for
Computational Linguistics, 2:491–503.
Jane Chandlee and Jeffrey Heinz. 2018. Strictly
locality and phonological maps. LI, 49:23–60.
Jane Chandlee and Steven Lindell. in prep. A
logical characterization of strictly local func-
tions. In Jeffrey Heinz, editor, Doing Computa-
tional Phonology. OUP.
G. N. Clements. 1976. Vowel Harmony in Non-
linear Generative Phonology: An Autosegmental
Model. Bloomington: Indiana University Lin-
guistics Club Publications.
Bruno Courcelle. 1994. Monadic second-order
definable graph transductions: a survey. Theo-
retical Computer Science, 126:53–75.
Joost Engelfriet and Hendrik Jan Hoogeboom.
2001. MSO definable string transductions and
two-way finite-state transducers. ACM Transa-
tions on Computational Logic, 2:216–254.
Emmanuel Filiot and Pierre-Alain Reynier. 2016.
Transducers, logic, and algebra for functions of
finite words. ACM SIGLOG News, 3(3):4–19.
167
l
D
o
w
n
o
a
d
e
d
f
r
o
m
h
t
t
p
:
/
/
d
i
r
e
c
t
.
m
i
t
.
e
d
u
/
t
a
c
l
/
l
a
r
t
i
c
e
–
p
d
f
/
d
o
i
/
.
1
0
1
1
6
2
/
t
l
a
c
_
a
_
0
0
2
6
0
1
9
2
3
3
2
9
/
/
t
l
a
c
_
a
_
0
0
2
6
0
p
d
.
f
b
y
g
u
e
s
t
t
o
n
0
7
S
e
p
e
m
b
e
r
2
0
2
3
Brian Gainor, Regine Lai, and Jeffrey Heinz.
2012. Computational characterizations of vowel
In The
harmony patterns and pathologies.
Proceedings of the 29th West Coast Conference
on Formal Linguistics, pages 63–71.
John Goldsmith. 1976. Autosegmental Phonol-
ogy. Ph.D. thesis, Massachussets Institute of
Technology.
Jeffrey Heinz and Regine Lai. 2013. Vowel
harmony and subsequentiality. In Proceedings
of the 13th Meeting on Mathematics of Lan-
guage. Sofia, Bulgaria.
Larry Hyman. 2011. Tone: Is it different? In
John A. Goldsmith, Jason Riggle, and Alan
C. L. Yu, editors, The Blackwell Handbook of
Phonological Theory, pages 197–238. Wiley-
Blackwell.
Larry Hyman and Francis X. Katamba. 2010.
Tone, syntax and prosodic domains in Luganda.
In Laura Downing, Annie Rialland, Jean-
Marc Beltzung, Sophie Manus, C´edric Patin,
and Kristina Riedel, editors, Papers from
the Workshop on Bantu Relative Clauses,
volume 53 of ZAS Papers in Linguistics,
pages 69–98. ZAS Berlin.
Adam Jardine. 2016. Computationally, tone is
different. Phonology, 33:247–283.
Adam Jardine. 2017. On the logical complexity of
autosegmental representations. In Proceedings
of the 15th Meeting on the Mathematics of
Language, pages 22–35. London, UK. Asso-
ciation for Computational Linguistics.
Martin Kay. 1987. Nonconcatenative finite-state
morphology. In Proceedings, Third Meeting of
the European Chapter of the Association for
Computational Linguistics, pages 2–10.
Michael Kenstowicz and Charles Kisseberth.
1990. Chizigula tonology: the word and beyond.
In Sharon Inkelas and Draga Zec, editors, The
Phonology–Syntax Connection, pages 163–194.
Chicago: the University of Chicago Press.
Andr´as Kornai. 1995. Formal Phonology. Garland
Publication.
Barbara Levergood. 1987. Topics
phonology and morphology. Ph.D.
University of Texas.
in Arusa
thesis,
l
D
o
w
n
o
a
d
e
d
f
r
o
m
h
t
t
p
:
/
/
d
i
r
e
c
t
.
m
i
t
.
e
d
u
/
t
a
c
l
/
l
a
r
t
i
c
e
–
p
d
f
/
d
o
i
/
.
1
0
1
1
6
2
/
t
l
a
c
_
a
_
0
0
2
6
0
1
9
2
3
3
2
9
/
/
t
l
a
c
_
a
_
0
0
2
6
0
p
d
.
f
b
y
g
u
e
s
t
t
o
n
0
7
S
e
p
e
m
b
e
r
2
0
2
3
Leonid Libkin. 2004. Elements of Finite Model
Theory. Berlin: Springer-Verlag.
Robert McNaughton and Seymour Papert. 1971.
Counter-Free Automata. MIT Press.
Scott Meyers. 1997. OCP effects in Optimality
Theory. NLLT, 15(4):847–892.
David Odden. 1986. On the role of the Obligatory
theory.
Contour Principle in phonological
Language, 62(2):353–383.
David Odden. 1994. Adjacency parameters in
phonology. Language, 70(2):289–330.
James Rogers. 1997. Strict
lt2 : Regular
::
: Recognizable. In Christian Retor´e,
Local
editor, Logical Aspects of Computational
International Conference,
Linguistics: First
LACL ’96 Nancy, France, September 23–25,
1996 Selected Papers, pages 366–385. Springer
Berlin Heidelberg, Berlin, Heidelberg.
Thilo Schadeberg. 1979.
¨Uber die t¨one der
verbalen formen im rimi. Afrika und ¨Ubersee,
57:288–313.
Galen Sibanda. 2004. Verbal phonology and
thesis, UC
morphology of Ndebele. Ph.D.
Berkeley.
Bruce Wiebe. 1992. Modelling autosegmental pho-
nology with multi-tape finite state transducers.
Master’s thesis, Simon Fraser University.
Moira Yip. 2002. Tone, Cambridge University
Press.
168