1

We give a tensor algebra characterization for regular transformations via origin graphs

A novel method for sampling a class of subsequential string transductions encoding homomorphisms allows rigorous testing of learning models’ capacity for compositionality.

We formalize various iterative prosodic processes including stress, syllabification and epenthesis using logical graph transductions, showing that the necessary use of fixed point operators without quantification restricts them to a structured subclass of subsequential functions.

We analyze divergences in strong generative capacity between morphological processes that are equivalent in weak generative capacity.

We analyze the expressivity of a variety of recurrent encoder-decoder networks, showing they are limited to learning subsequential functions, and connecting RNNs with attention mechanisms to a class of deterministic 2-way transducers.

We provide an automata-theoretic characterization of templatic morphology, extending strict locality to consider n-ary functions.

We provide an automata-theoretic characterization of tonal phonology, extending strict locality to consider n-ary functions.

I provide a vector space characterization of the Star-Free and Locally Threshold testable classes of formal languages, over arbitrary data structures.

We describe a partial order on the space of model-theoretic constraints and a learning algorithm for constraint inference.

We describe the finite-state nature of root-and-pattern morphology using Semitic as a case study, and discuss issues of finiteness vs. infinity, and template emergence.