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 endif the string contains a sequence /ti/ and it contains a sequence /in/ (which may or may not be overlapping), add a /d/ to the endif the string does not contain a /k/, add a /d/ to the endif 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.
Is this a regular relation?
automata theory
Regular relationsAll 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.  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 transducersThat 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, 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.LiteratureThere 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.  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.