<h3>Regular relations</h3>

<p>All of them are regular relations, assuming the rules are applied only once and assuming we don't have to deal with overlapping matches.</p>

<p>You have to be a bit careful when specifying these kinds of rules to determine what you want to happen if there are multiple places where the rule might apply.  I'm going to assume that the rule avoids ambiguity (e.g., always pick the leftmost match), and that the rule is applied only once, so that the rule can be implemented by scanning from left-to-right over the string in a single pass.</p>

<p>With that clarification, all of these are regular relations, i.e., can be implemented as a (possibly non-deterministic) <a href="https://en.wikipedia.org/wiki/Finite-state_transducer" rel="nofollow noreferrer">finite-state transducer</a>.  There are two rules whose intended meaning wasn't entirely clear to me, so let me discuss each in more detail:</p>

<ul>
<li>"if the string contains a /d/ with a /g/ anywhere later than it, map that /d/ to /t/": I can see two possible meanings, both regular:

<ul>
<li>"if the string contains a /d/ with a /g/ anywhere later than it, map the leftmost /d/ to /t/": a regular relation. or,</li>
<li>"if the string contains a /d/ with a /g/ anywhere later than it, map all /d/'s that precede the last /g/ to /t/": also a regular relation.</li>
</ul></li>
<li><p>"if the string contains a /w/ and a /y/ with anything intervening, swap around the /w/ and the /y/": This requires more care.  I can see two possible meanings:</p>

<ul>
<li>Perhaps you mean to scan for the first /w/, then for the first /y/ after it, and if found swap the /w/ and /y/ and then continue scanning the rest of the string after that.  If so, that's a regular relation.</li>
<li>However, if you meant to pair up the /w/'s and /y/'s in a nested fashion (leftmost /w/ with rightmost /y/, and so on) and swap them all (e.g., /wwwwyyyy/ becomes /yyyywwww/), then that's not a regular relation.  Or, to put it another way, if you meant that the rule should be applied repeatedly until no further changes occur, it's not a regular relation.</li>
</ul>

<p>I'll assume you meant the former.</p></li>
</ul>

<hr>

<h3>Deterministic finite-state transducers</h3>

<p>That said, the notion of regular relation might not be the notion you are looking for.  A mapping forms a regular relation if and only if it can be applied by a, <em>possibly non-deterministic</em>, finite-state transducer.  Unfortunately, non-deterministic finite-state transducers are not as convenient as deterministic finite-state transducers.  There are two problems:</p>

<ul>
<li><p><em>Ambiguous output:</em> Given a single input word and a non-deterministic finite-state transducer, there might be multiple possible outputs.  I suspect you want your rules to correspond to deterministic functions, so each input string corresponds to a single output string.  (Otherwise, there's ambiguity about what the input string should map to.)  If so, non-deterministic transducers are too powerful.  You might want to restrict attention to deterministic finite-state transducers or <a href="https://en.wikipedia.org/wiki/Unambiguous_finite_automaton" rel="nofollow noreferrer">unambiguous finite-state transducers</a>, which ensure that each input corresponds to just one possible output.</p></li>
<li><p><em>Efficient simulation:</em> Given a single input string and a deterministic finite-transducer, you can very efficiently compute the corresponding output string by just simulating the transducer.  However, the same is not true for non-deterministic finite-state transducers (not even unambiguous finite-state transducers).  Therefore, you might want to restrict attention to <em>deterministic</em> finite-state transducers.</p></li>
</ul>

<p>With that motivation, we can ask a follow-up question: which of these rules can be modelled by deterministic finite-state transducers?  The answer is that all but two of those rule can be implemented as a <em>deterministic</em> finite-state transducer.</p>

<p>The two that cannot are:</p>

<ul>
<li>"if the string contains a /d/ with a /g/ anywhere later than it, map that /d/ to /t/"</li>
<li>"if the string contains a /w/ and a /y/ with anything intervening, swap around the /w/ and the /y/"</li>
</ul>

<p>Those two cannot be implemented with a deterministic finite-state transducer, because they require unbounded memory.  After you see a /d/, you can't output anything: you have to keep scanning until you see a /g/ and meanwhile save everything you've seen.  There's no limit to how much you might need to remember, because there's no limit to how long you might have to wait until you see a /g/.  A similar reason applies for the second example above.</p>

<p>The remainder <em>can</em> be implemented as a deterministic finite-state transducer, because they only require a fixed constant amount of memory.</p>

<p>Those two rules <em>can</em> be implemented as a <em>non-deterministic</em> finite-state transducer.  For instance, when the transducer sees a /d/ it can non-deterministically guess whether or not there is any subsequent /g/, and follow both paths.  Those two rules can even be implemented with an unambiguous non-deterministic finite-state transducer.</p>

<p>If you want an overview of theoretical tools to prove that a language is/isn't regular, take a look at <a href="https://cs.stackexchange.com/q/1331/755">https://cs.stackexchange.com/q/1331/755</a> and <a href="https://cs.stackexchange.com/q/1031/755">https://cs.stackexchange.com/q/1031/755</a>.  Those relate to regular <em>languages</em>, but similar theoretical tools can be adapted to apply to regular <em>relations</em> as well.  See also <a href="https://en.wikipedia.org/wiki/Finite-state_transducer" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Finite-state_transducer</a>.</p>

<hr>

<h3>Literature</h3>

<p>There appears to be some literature on exactly your idea: modelling phonological rules as regular relations.  See, for example, the following paper:</p>

<p>Ronald M. Kaplan, Martin Kay.  <a href="http://www.anthology.aclweb.org/J/J94/J94-3001.pdf" rel="nofollow noreferrer">Regular Models of Phonological Rule Systems</a>.  Computational Linguistics 20(3), pp.331-378, 1994.</p>

<p>From a technical perspective, they model phonological rules as <em>same-length</em> regular relations, i.e., a regular relation $R \subseteq \Sigma^* \times \Gamma^*$ with the added property that for every $(s,t) \in R$ the length of $s$ is the same as the length of $t$.  Equivalently, they consider the class of non-deterministic finite-state transducers that have no $\epsilon$-transitions.  It looks like they work out the mathematics and its application to linguistics in considerable detail.</p>

CC BY-SA 3.0
2016-12-16T14:59:31.103Z
I'm not sure this is correct.  A *deterministic* transducer cannot recognize these, but certainly an unambiguous one can, hence they are rational relations alright.
Michaël Cadilhac
CC BY-SA 3.0
2016-12-16T19:05:32.517Z
@MichaëlCadilhac, you're quite right.  Thank you!  Would you take a look at the edited answer and see if it looks like I've gotten it right now?  I might be exposing gaps in my knowledge here.  Thanks again for the correction and feedback.
D.W.
CC BY-SA 3.0
2016-12-16T19:38:30.910Z
Thanks, D.W., that's extremely helpful! It seems like deterministic functions are the right thing to assume for phonology, so that would suggest that either these "anywhere intervening" rules aren't in fact within the power of phonology, or phonology needs access to a more complex sort of transducer than Kaplan and Kay (and others) have assumed.
Ollie Sayeed
CC BY-SA 3.0
2016-12-16T21:04:43.057Z
Is there a word for the types of relations that can be implemented with a deterministic transducer, specifically?
Ollie Sayeed
CC BY-SA 3.0
2016-12-16T22:08:07.403Z
@OliverSayeed, I *think* that deterministic finite-state transducers correspond to purely sequential (regular) relations.  Not sure whether that will be useful, though.
D.W.
CC BY-SA 3.0
2016-12-16T23:35:47.113Z
It seems quite OK now :-)  Note that *deterministic* is not the usual term for what you consider, *sequential* (or *input-deterministic*) is.  (Deterministic means that the automaton on the product alphabet is deterministic).  Cheers!
Michaël Cadilhac
CC BY-SA 3.0
2016-12-15T04:29:47.603Z
2016-12-16T19:00:06.650Z
2017-04-13T12:48:30.830Z
D.W.
<p>I'm a linguist (and not a computer scientist!) investigating a new sort of linguistic formalism for mapping phonological strings into other strings - and I'm wondering if it's a regular relation that could be done on a finite-state transducer.</p>

<p>I give the machine a description of a string to look for, and when it finds a string that fits its description, it maps it to another string that's a function of the input string.</p>

<p>Examples of things this machine can do:</p>

<ul>
<li>"if the string contains a /b/, map that /b/ to /p/"</li>
<li>"if the string contains a /t/, map that /t/ to /ts/"</li>
<li>"if the string contains a sequence /dw/, map that /dw/ to /p/"</li>
<li>"if the string contains a /z/, delete the /z/"</li>
<li>"if the string contains a /d/ with a /g/ anywhere later than it, map that /d/ to /t/"</li>
<li>"if the string contains a /t/ <em>or</em> it contains a /k/, add a /d/ to the end"</li>
<li>"if the string contains a sequence /ti/ <em>and</em> it contains a sequence /in/ (which may or may not be overlapping), add a /d/ to the end"</li>
<li>"if the string does <em>not</em> contain a /k/, add a /d/ to the end"</li>
<li>"if the string contains a /w/ and a /y/ with anything intervening, swap around the /w/ and the /y/"</li>
</ul>

<p>In other words, it applies to an input string if that string has some (not necessarily contiguous) substring - and then applies some simple function, like mapping the relevant substring to something else, or adding something to the end of the string. And it can have words like <em>and</em>, <em>or</em>, and <em>not</em> in the descriptions of the strings it applies to.</p>

<p>Is there anything in here (if it's possible to tell from a prose description) that a finite-state transducer wouldn't be able to do? I have an intuition that there isn't, but I'm not able to prove that.</p>

CC BY-SA 3.0
2016-12-15T17:20:16.793Z
What is the result of your machine if there are several occurrences matching your requirements. For instance, for the first item, do you want to replace each occurrence of $b$ by $p$ (or just the first one) and for the last item, what would be the output for the strings $wyw$, $ywy$ and $wywy$?
J.-E. Pin
CC BY-SA 3.0
2016-12-16T16:06:57.987Z
Good question; in other phonological models, a rule applies to every occurrence that matches its description, and it's specified for each rule whether it applies to them in turn from left to right or right to left.
Ollie Sayeed
<automata-theory>
Is this a regular relation?
Ollie Sayeed
# Is this a regular relation?

(Asked by: username_0 on 2016-12-14)

I'm a linguist (and not a computer scientist!) investigating a new sort of linguistic formalism for mapping phonological strings into other strings - and I'm wondering if it's a regular relation that could be done on a finite-state transducer.

I give the machine a description of a string to look for, and when it finds a string that fits its description, it maps it to another string that's a function of the input string.

Examples of things this machine can do:

* "if the string contains a /b/, map that /b/ to /p/"
* "if the string contains a /t/, map that /t/ to /ts/"
* "if the string contains a sequence /dw/, map that /dw/ to /p/"
* "if the string contains a /z/, delete the /z/"
* "if the string contains a /d/ with a /g/ anywhere later than it, map that /d/ to /t/"
* "if the string contains a /t/ *or* it contains a /k/, add a /d/ to the end"
* "if the string contains a sequence /ti/ *and* it contains a sequence /in/ (which may or may not be overlapping), add a /d/ to the end"
* "if the string does *not* contain a /k/, add a /d/ to the end"
* "if the string contains a /w/ and a /y/ with anything intervening, swap around the /w/ and the /y/"

In other words, it applies to an input string if that string has some (not necessarily contiguous) substring - and then applies some simple function, like mapping the relevant substring to something else, or adding something to the end of the string. And it can have words like *and*, *or*, and *not* in the descriptions of the strings it applies to.

Is there anything in here (if it's possible to tell from a prose description) that a finite-state transducer wouldn't be able to do? I have an intuition that there isn't, but I'm not able to prove that.

**Tags:** automata-theory
> **Comments:**
> **username_1**: What is the result of your machine if there are several occurrences matching your requirements. For instance, for the first item, do you want to replace each occurrence of $b$ by $p$ (or just the first one) and for the last item, what would be the output for the strings $wyw$, $ywy$ and $wywy$?  
> **username_0**: Good question; in other phonological models, a rule applies to every occurrence that matches its description, and it's specified for each rule whether it applies to them in turn from left to right or right to left.  

---

## 1 answers

### Answer by username_2 on 2016-12-15. Score: 9 | Accepted answer

### Regular relations

All of them are regular relations, assuming the rules are applied only once and assuming we don't have to deal with overlapping matches.

You have to be a bit careful when specifying these kinds of rules to determine what you want to happen if there are multiple places where the rule might apply. I'm going to assume that the rule avoids ambiguity (e.g., always pick the leftmost match), and that the rule is applied only once, so that the rule can be implemented by scanning from left-to-right over the string in a single pass.

With that clarification, all of these are regular relations, i.e., can be implemented as a (possibly non-deterministic) [finite-state transducer](https://en.wikipedia.org/wiki/Finite-state_transducer). There are two rules whose intended meaning wasn't entirely clear to me, so let me discuss each in more detail:

* "if the string contains a /d/ with a /g/ anywhere later than it, map that /d/ to /t/": I can see two possible meanings, both regular:
  + "if the string contains a /d/ with a /g/ anywhere later than it, map the leftmost /d/ to /t/": a regular relation. or,
  + "if the string contains a /d/ with a /g/ anywhere later than it, map all /d/'s that precede the last /g/ to /t/": also a regular relation.
* "if the string contains a /w/ and a /y/ with anything intervening, swap around the /w/ and the /y/": This requires more care. I can see two possible meanings:

  + Perhaps you mean to scan for the first /w/, then for the first /y/ after it, and if found swap the /w/ and /y/ and then continue scanning the rest of the string after that. If so, that's a regular relation.
  + However, if you meant to pair up the /w/'s and /y/'s in a nested fashion (leftmost /w/ with rightmost /y/, and so on) and swap them all (e.g., /wwwwyyyy/ becomes /yyyywwww/), then that's not a regular relation. Or, to put it another way, if you meant that the rule should be applied repeatedly until no further changes occur, it's not a regular relation.

  I'll assume you meant the former.

---

### Deterministic finite-state transducers

That said, the notion of regular relation might not be the notion you are looking for. A mapping forms a regular relation if and only if it can be applied by a, *possibly non-deterministic*, finite-state transducer. Unfortunately, non-deterministic finite-state transducers are not as convenient as deterministic finite-state transducers. There are two problems:

* *Ambiguous output:* Given a single input word and a non-deterministic finite-state transducer, there might be multiple possible outputs. I suspect you want your rules to correspond to deterministic functions, so each input string corresponds to a single output string. (Otherwise, there's ambiguity about what the input string should map to.) If so, non-deterministic transducers are too powerful. You might want to restrict attention to deterministic finite-state transducers or [unambiguous finite-state transducers](https://en.wikipedia.org/wiki/Unambiguous_finite_automaton), which ensure that each input corresponds to just one possible output.
* *Efficient simulation:* Given a single input string and a deterministic finite-transducer, you can very efficiently compute the corresponding output string by just simulating the transducer. However, the same is not true for non-deterministic finite-state transducers (not even unambiguous finite-state transducers). Therefore, you might want to restrict attention to *deterministic* finite-state transducers.

With that motivation, we can ask a follow-up question: which of these rules can be modelled by deterministic finite-state transducers? The answer is that all but two of those rule can be implemented as a *deterministic* finite-state transducer.

The two that cannot are:

* "if the string contains a /d/ with a /g/ anywhere later than it, map that /d/ to /t/"
* "if the string contains a /w/ and a /y/ with anything intervening, swap around the /w/ and the /y/"

Those two cannot be implemented with a deterministic finite-state transducer, because they require unbounded memory. After you see a /d/, you can't output anything: you have to keep scanning until you see a /g/ and meanwhile save everything you've seen. There's no limit to how much you might need to remember, because there's no limit to how long you might have to wait until you see a /g/. A similar reason applies for the second example above.

The remainder *can* be implemented as a deterministic finite-state transducer, because they only require a fixed constant amount of memory.

Those two rules *can* be implemented as a *non-deterministic* finite-state transducer. For instance, when the transducer sees a /d/ it can non-deterministically guess whether or not there is any subsequent /g/, and follow both paths. Those two rules can even be implemented with an unambiguous non-deterministic finite-state transducer.

If you want an overview of theoretical tools to prove that a language is/isn't regular, take a look at <https://cs.stackexchange.com/q/1331/755> and <https://cs.stackexchange.com/q/1031/755>. Those relate to regular *languages*, but similar theoretical tools can be adapted to apply to regular *relations* as well. See also <https://en.wikipedia.org/wiki/Finite-state_transducer>.

---

### Literature

There appears to be some literature on exactly your idea: modelling phonological rules as regular relations. See, for example, the following paper:

Ronald M. Kaplan, Martin Kay. [Regular Models of Phonological Rule Systems](http://www.anthology.aclweb.org/J/J94/J94-3001.pdf). Computational Linguistics 20(3), pp.331-378, 1994.

From a technical perspective, they model phonological rules as *same-length* regular relations, i.e., a regular relation $R \subseteq \Sigma^\* \times \Gamma^\*$ with the added property that for every $(s,t) \in R$ the length of $s$ is the same as the length of $t$. Equivalently, they consider the class of non-deterministic finite-state transducers that have no $\epsilon$-transitions. It looks like they work out the mathematics and its application to linguistics in considerable detail.

> **Comments:**
> **username_3**: I'm not sure this is correct.  A *deterministic* transducer cannot recognize these, but certainly an unambiguous one can, hence they are rational relations alright.  
> **username_2**: @MichaëlCadilhac, you're quite right.  Thank you!  Would you take a look at the edited answer and see if it looks like I've gotten it right now?  I might be exposing gaps in my knowledge here.  Thanks again for the correction and feedback.  
> **username_0**: Thanks, D.W., that's extremely helpful! It seems like deterministic functions are the right thing to assume for phonology, so that would suggest that either these "anywhere intervening" rules aren't in fact within the power of phonology, or phonology needs access to a more complex sort of transducer than Kaplan and Kay (and others) have assumed.  
> **username_0**: Is there a word for the types of relations that can be implemented with a deterministic transducer, specifically?  
> **username_2**: @OliverSayeed, I *think* that deterministic finite-state transducers correspond to purely sequential (regular) relations.  Not sure whether that will be useful, though.  
> **username_3**: It seems quite OK now :-)  Note that *deterministic* is not the usual term for what you consider, *sequential* (or *input-deterministic*) is.  (Deterministic means that the automaton on the product alphabet is deterministic).  Cheers!  

---

