Elamur Research⌕
☰
home / papers / 2026 / Phonological Processes as Modal Transductions

Phonological Processes as Modal Transductions

Summary

The paper offers a modal-logic view of phonology, grounded in the Rational Hypothesis: phonological maps in natural language belong to the rational functions, which one-way finite-state transducers compute. The authors examine Boolean Monadic Recursive Schemes (BMRS), a recursive if-then-else formalism already used to model phonological processes. They prove that total BMRS programs define exactly the same unary properties over words as the modal µ-calculus, which is modal logic extended with a fixed-point operator.

The proof works in two directions:

  • µ-calculus to BMRS: formulas are normalized into a directional, negation-free fragment, then translated compositionally into total BMRS programs.
  • BMRS to µ-calculus: BMRS is encoded in MSO, and a known result that MSO and the µ-calculus are equivalent over strings closes the loop.

As a corollary, the authors give a fresh demonstration that BMRS interpretations which preserve order characterize precisely the rational functions. Phonological maps can therefore be written as "modal transductions" without variables. The link matters because the automata-theoretic and learning results already known for the µ-calculus may carry over to phonological modeling.

Key points

  • Main theorem: total BMRS and the modal µ-calculus are expressively equivalent on words. Each BMRS output predicate has a µ-calculus formula that holds at exactly the same indices.
  • Corollary: a new proof that order-preserving BMRS transductions characterize the rational functions. This result was originally due to Bhaskar et al. (2020, 2023).
  • Worked examples:
    • A local vowel nasalization rule, shown as an FST, as BMRS, and as the modal formula N′ = (V ∧ ♢N) ∨ N.
    • Iterative nasal spreading in Warao (Osborn, 1966), used to show how recursion is evaluated as a least fixed point.
  • Construction: a translation tr maps formulas of the fragment dir-µML_f+ into BMRS rules, with ♢ and ♦ becoming successor and predecessor calls. Totality is proved by induction over strongly connected components.
  • Context: the work extends Graf (2010), who used modal logic for surface well-formedness constraints, and connects to learning work such as Yolyan (2025a) and ten Cate and Koudijs (2024).

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

Fields: Linguistics & languages

Cite

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.18653/v1/2026.scil-main.51

@inproceedings{yolyan2026phonological,
  title = {{Phonological Processes as Modal Transductions}},
  author = {Yolyan, Tatevik and Comer, Jesse},
  booktitle = {Proceedings of the Society for Computation in Linguistics 2026},
  year = {2026},
  doi = {10.18653/v1/2026.scil-main.51},
  url = {https://doi.org/10.18653/v1/2026.scil-main.51}
}

References

32 references, 0 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Marcelo Arenas, Pablo Barceló, and Leonid Libkin. 2011. Regular languages of nested words: fixed points, automata, and synchronization. Theory of Computing Systems, 49(3):639–670. find
  2. Hans Bekić. 1984. Definable operations in general algebras, and the theory of automata and flowcharts. In C. B. Jones, editor, Programming Languages and Their Definition: H. Bekič (1936–1982), pages 30– 55. Springer Berlin Heidelberg, Berlin, Heidelberg. find
  3. Jean Berstel. 2007. Transductions and Context-Free Languages. Vieweg+Teubner Verlag Wiesbaden. find
  4. Siddharth Bhaskar, Jane Chandlee, and Adam Jardine. 2023. Rational functions via recursive schemes. Preprint, arXiv:2302.03074. — [arXiv:2302.03074](https://arxiv.org/abs/2302.03074) find
  5. Siddharth Bhaskar, Jane Chandlee, Adam Jardine, and Christopher Oakden. 2020. Boolean monadic recursive schemes as a logical characterization of the subsequential functions. In International conference on language and automata theory and applications, pages 157–169. Springer. find
  6. Patrick Blackburn, Maarten de Rijke, and Yde Venema. 2001. Modal Logic. Cambridge Tracts in Theoretical Computer Science. Cambridge University Press. find
  7. Julian Bradfield and Colin Stirling. 2006. Modal Mu-Calculi, chapter 12. Elsevier. find
  8. J. Richard Büchi. 1960. Weak second-order arithmetic and finite automata. Mathematical Logic Quarterly, 6(1-6):66–92. find
  9. Jane Chandlee. 2014. Strictly Local Phonological Processes. Ph.D. thesis, University of Delaware. find
  10. Jane Chandlee and Adam Jardine. 2019. Quantifier-free least fixed point functions for phonology. In Proceedings of the 16th Meeting on the Mathematics of Language (MOL), pages 50–62. Association for Computational Linguistics. find
  11. Emmanuel Filiot. 2015. Logic-automata connections for transformations. In Indian conference on logic and its applications, pages 30–57. Springer. find
  12. Emmanuel Filiot, Olivier Gauwin, and Nathan Lhote. 2019. Logical and algebraic characterizations of rational transductions. Logical Methods in Computer Science, Volume 15, Issue 4:16. find
  13. Thomas Graf. 2010. Logics of phonological reasoning. Master’s thesis, University of California, Los Angeles. find
  14. Jeffrey Heinz. 2018. The computational nature of phonological generalizations. In Larry M. Hyman and Frans Plank, editors, Phonological Typology, volume 23 of Phonology and Phonetics, pages 126– 195. De Gruyter Mouton, Berlin, Boston. find
  15. Adam Jardine, Jane Chandlee, Rémi Eyraud, and Jeffrey Heinz. 2014. Very efficient learning of structured classes of subsequential functions from positive data. In The 12th International Conference on Grammatical Inference, volume 34, pages 94–108. find
  16. Douglas Johnson. 1972. Formal aspects of phonological description. De Gruyter. find
  17. Ronald M Kaplan and Martin Kay. 1994. Regular models of phonological rule systems. Computational Linguistics, 20(3):331–378. find
  18. Bronisław Knaster. 1928. Un théorème sur les fonctions d’ensembles. Annales de la Société Polonaise de Mathématique, 6:133–134. find
  19. Raoul Koudijs. 2022. Learning modal formulas via dualities. Master’s thesis, Universiteit van Amsterdam. find
  20. Dexter Kozen. 1983. Results on the propositional µ-calculus. Theoretical Computer Science, 27(3):333– 354. Special Issue Ninth International Colloquium on Automata, Languages and Programming (ICALP) Aarhus, Summer 1982. find
  21. Jane Chandlee and Adam Jardine. 2021. Computational universals in linguistic theory: Using recursive programs for phonological analysis. Language, 97(3):485–519. find
  22. José Oncina, Pedro García, and Enrique Vidal. 1993. Learning subsequential transducers for pattern recognition interpretation tasks. IEEE Transactions on Pattern Analysis and Machine Intelligence, 15:448–458. find
  23. Bruno Courcelle. 1994. Monadic second-order definable graph transductions: a survey. Theoretical Computer Science, 126(1):53–75. find
  24. Henry A. Osborn. 1966. Warao i: Phonology and morphophonemics. International Journal of American Linguistics, 32(2). find
  25. Bruno Courcelle and Joost Engelfriet. 2012. Monadic second-order transductions. In Graph Structure and Monadic Second-Order Logic: A Language-Theoretic Approach, chapter 7, pages 505–577. Cambridge University Press. find
  26. Alfred Tarski. 1955. A lattice-theoretical fixpoint theorem and its applications. Pacific Journal of Mathematics, 5(2):285–309. find
  27. E. A. Emerson and C. S. Jutla. 1991. Tree automata, mu-calculus and determinacy. In Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, SFCS ’91, page 368–377, USA. IEEE Computer Society. find
  28. Balder ten Cate and Raoul Koudijs. 2024. Characterising modal formulas with examples. ACM Transactions on Computational Logic, 25(2). find
  29. Thomas Wilke. 2001. Alternating tree automata, parity games, and modal µ-calculus. Bulletin of The Belgian Mathematical Society, 8:359–391. find
  30. Tatevik Yolyan. 2025a. A framework for learning phonological maps as logical transductions. In Proceedings of the 18th Meeting on the Mathematics of Language, page 44–58. Association for Computational Linguistics. find
  31. Tatevik Yolyan. 2025b. A logical characterization of weak determinism as simultaneous application. Journal of Logic, Language and Information. find
  32. Tatevik Yolyan. 2025c. Phonological Expressivity and Learning via Boolean Monadic Recursive Schemes. Ph.D. thesis, Rutgers The State University of New Jersey, School of Graduate Studies. find

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/yolyan-2026-phonological-processes-as-modal-transductions/