Computational Perspectives on Phonological Constituency and Recursion


  • Kristine M. Yu University of Massachusetts Amherst


Whether or not phonology has recursion is often conflated with whether or not phonology has strings or trees as data structures. Taking a computational perspective from formal language theory and focusing on how phonological strings and trees are built, we disentangle these issues. We show that even considering the boundedness of words and utterances in physical realization and the lack of observable examples of potential recursive embedding of phonological constituents beyond a few layers, recursion is a natural consequence of expressing generalization in phonological grammars for strings and trees. While prosodically-conditioned phonological patterns can be represented using grammars for strings, e.g., with bracketed string representations, we show how grammars for trees provide a natural way to express these patterns and provide insight into the kinds of analyses that phonologists have proposed for them.


prosody, tree transducers, computational phonology, recursion


Abelson, Harold, Gerald Jay Sussman & Julie Sussman. 1996. Structure and interpretation of computer programs, 2nd edn. Cambridge, MA: MIT Press.

Alberta, Jürgen, Dora Giammarresi & Derick Wood. 2001. Normal form algorithms for extended context-free grammars. Theoretical Computer Science 267: 35-47.

Baker, Brenda. 1978. Tree transducers and tree languages. Information and control 37: 241-266.

Bennett, Ryan. 2018. Recursive prosodic words in Kaqchikel (Mayan). Glossa 3(1): 67-133.

Chomsky, Noam. 1956. Three descriptions of language. IRE Transactions in Information Theory 2(3): 113-124.

Chomsky, Noam. 1963. Formal properties of grammars. In R. Duncan Luce, Robert B. Bush & Eugene Galanter (eds.). Handbook of mathematical psychology, Vol. 2, 323-418. New York and London: John Wiley & Sons, Inc. Chap. 12.

Chomsky, Noam & Morris Halle. 1968. The sound pattern of English. Cambridge: The MIT Press.

Chomsky, Noam & George A. Miller. 1963. Introduction to the formal analysis of natural languages. In R. Duncan Luce, Robert B. Bush & Eugene Galanter (eds.). Handbook of mathematical psychology, Vol. 2, 269-321. New York and London: John Wiley & Sons, Inc. Chap. 11.

Clark, Alexander. 2014. An introduction to multiple context-free grammars for linguists. Retrieved from

Comon, H., M. Dauchet, R. Gilleron, C. Löding, F. Jacquemard, D. Lugiez, S. Tison & M. Tommasi. 2007. Tree Automata Techniques and Applications. Retrieved from Release October, 12th 2007.

Dolatian, Hossep, Aniello De Santo & Thomas Graf. 2021. Recursive prosody is not finite-state. In Proceedings of SIGMORPHON 2021.

Engelfriet, Joost, Eric Lilin & Andreas Maletti. 2009. Extended multi bottom-up tree transducers: Composition and decomposition. Acta Informatica 46(8): 561-590.

Gärtner, Hans-Martin. 2002. Generalized transformations and beyond. Berlin: Akademie Verlag.

Gussenhoven, Carlos. 2005. Procliticized phonological phrases in English: Evidence from rhythm. Studia Linguistica 59: 174-193.

Gussenhoven, Carlos. 2018. Prosodic typology meets phonological representations. In Larry M. Hyman and Frans Plank (eds.). Phonological typology, 389-418. Berlin/Boston: Walter de Gruyter GmbH.

Hartmanis, Juris. 1980. On the succinctness of different representations of languages. SIAM Journal on Computing 9: 114-120.

Heinz, Jeffrey. 2009. On the role of locality in learning stress patterns. Phonology 26(02): 303-351.

Heinz, Jeffrey. 2011. Computational phonology – part I: Foundations. Language and Linguistics Compass 5(4): 140-152.

Heinz, Jeffrey. 2018. The computational nature of phonological generalizations. In Larry M. Hyman and Frans Plank (eds.). Phonological typology, 126-195. Berlin/Boston: De Gruyter Mouton.

Heinz, Jeffrey, Colin de la Higuera & Menno van Zaanen. 2016. Grammatical inference for computational linguistics. California: Morgan and Claypool Publishers.

Idsardi, William J. 2018. Why is phonology different? No recursion. In Ángel J. Gallego & Roger Martin (eds.). Language, Syntax, and the Natural Sciences, 212-223. Cambridge: Cambridge University Press.

Ito, Junko & Armin Mester. 1992. Weak layering and word binarity. Manuscript. University of California Santa Cruz.

Ito, Junko & Armin Mester. 2003. Weak layering and word binarity. In Takeru Honma, Masao Okazaki, Toshiyuki Tabata & Shin’ichi Tanaka (eds.). A new century of phonology and phonological theory: a festschrift for Professor Shosuke Haraguchi on the occasion of his sixtieth birthday, Vol. Revised version of Report LRC-92-09, Linguistic Research Center, University of California, Santa Cruz (1992), 26-65. Tokyo, Japan: Kaitakusha.

Ito, Junko & Armin Mester. 2007. Prosodic adjunction in Japanese compounds. Formal Approaches to Japanese Linguistics: Proceedings of FAJL 4 55: 97-111.

Ladd, D. Robert. 1986. Intonational phrasing: The case for recursive prosodic structure. Phonology Yearbook 3: 311-340.

Lilin, Eric. 1978. Une generalisation des transducteurs d’etats finis d’arbres: les S-transducteurs. Thése 3éme cycle, Université de Lille.

McCarthy, John J. 1988. Feature geometry and dependency: a review. Phonetica 43: 84-108.

Meyer, A. R. & M. J. Fischer. 1971. Economy of description by automata, grammars, and formal systems. In 12th Annual IEEE Symposium on Switching and Automata Theory, 188-191.

Neeleman, Ad & J. van de Koot. 2006. On syntactic and phonological representations. Lingua 116: 1524-1552.

Nespor, Marina & Irene Vogel. 1986. Prosodic phonology. Dordrecht, The Netherlands: Foris Publications.

Nowak, Martin A., Natalia L. Komarova & Partha Niyogi. 2002. Computational and evolutionary aspects of language. Nature 417(6889): 611-617.

Parker, Anna R. 2006. Evolution as a constraint on theories of syntax: the case against Minimalism. PhD diss, University of Edinburgh, Edinburgh, Scotland.

Peperkamp, Sharon Andrea. 1997. Prosodic words. PhD diss, Universiteit van Amsterdam, Amsterdam.

Pierrehumbert, Janet & Mary Beckman. 1988. Japanese tone structure. Cambridge: The MIT Press.

Pinker, Steven & Ray Jackendoff. 2005. The faculty of language: what’s special about it? Cognition 95: 201-236.

Rounds, William C. 1970. Mappings and grammars on trees. Mathematical Systems Theory 4(3): 257-287.

Savitch, Walter J. 1993. Why it might pay to assume that languages are infinite. Annals of Mathematics and Artificial Intelligence 8: 17-25.

Scheer, Tobias. 2004. A lateral theory of phonology. Berlin/New York: Mouton de Gruyter.

Scheer, Tobias. 2013. Why phonology is flat: the role of concatenation and linearity. Language Sciences 39: 54-74.

Schreuder, Maartje, Dicky Gilbers & Hugo Quené. 2009. Recursion in phonology. Lingua 119: 1243-1252.

Selkirk, Elisabeth. 1980. Prosodic domains in phonology: Sanskrit revisited. In M. Aronoff and M. L. Keans (eds.). Juncture. Saratoga, California: Anma Libri.

Selkirk, Elisabeth. 1996. The prosodic structure of function words. In James Morgan & Katherine Demuth (eds.). Signal to syntax: Bootstrapping from speech to grammar in early acquisition, 187-213. Mahwah: Lawrence Erlbaum Associates.

Selkirk, Elisabeth. 2011. The syntax-phonology interface. In John Goldsmith, Jason Riggle & Alan C. L. Yu (eds.). The handbook of phonological theory, 435-484. Malden: Wiley-Blackwell.

Selkirk, Elisabeth O. 1984. Phonology and syntax: the relationship between sound and structure. Cambridge, MA: MIT Press.

Sipser, Michael. 2013. Introduction to the theory of computation, 3rd edn. Boston, MA: Cengage Learning.

Stabler, Edward P. 2014. Recursion in grammar and performance. In Tom Roeper & Margaret Speas (eds.). Recursion: complexity in cognition, 159-177. Cham: Springer.

Stabler, Edward P. 2019. Three mathematical foundations for syntax. Annual Review of Linguistics 5(1): 243-260.

Tomalin, Marcus. 2007. Reconsidering recursion in syntactic theory. Lingua 117: 1784-1800.

van der Hulst, Harry. 2010. A note on recursion in phonology. In Harry van der Hulst (ed.). Recursion and human language, 301-341. Berlin/New York: De Gruyter Mouton. Chap. 17.

Vance, Timothy J. 1987. An introduction to Japanese phonology. Albany, NY: State University of New York Press.

Vogel, Irene. 2009. Universals of prosodic structure. In Sergio Scalise, Elisabetta Magni & Antonietta Bisetto (eds.). Universals of language today, 59-82. Cham: Springer.

Yu, Kristine M. 2019. Parsing with Minimalist Grammars and prosodic trees. In Robert C. Berwick & Edward P. Stabler (eds.). Minimalist parsing, 69-109. Oxford, UK: Oxford University Press.




Download data is not yet available.