Elamur Research⌕
☰
home / papers / 2026 / Learning Process Interaction Through Simplex ISL Transducers

Learning Process Interaction Through Simplex ISL Transducers

Paper · 2026 · Chenli Wang and Adam Jardine

Summary

Phonological processes often interact: one rule can create or destroy the context another rule needs. An example is Votic, where vowel raising feeds palatalization of /k/. Learners must therefore recover both the separate processes and the order they apply in, from surface data that reflect only the combined mapping. Wang and Jardine treat this as a function decomposition problem within a restricted subregular class, simplex ISL 2 functions, which change exactly one symbol in exactly one one-symbol context.

Their method has two stages. First, OSTIA learns a transducer for the composed function. This works because subsequential functions remain subsequential under composition. Second, the authors' algorithm, SI 2 FIDA, splits that transducer into two component machines. It then fixes their ordering by testing for feeding-type or bleeding-type relations between environments, targets and outputs.

The authors prove that SI 2 FIDA identifies the correct pair of transducers in the limit, using polynomial time and data. The result extends earlier decomposition work and is a first formal step toward learning interacting processes. Chinese tone sandhi is a motivating case.

Key points

  • The learning problem is decomposing g ∘ f, where both f and g are left-simplex ISL 2 functions. This generalizes Hua and Jardine (2021), who decomposed a homomorphism composed with one simplex ISL 2 function.
  • The approach relies on a structural fact: the canonical SFST of a simplex ISL 2 function has exactly two states (q def and q env) and exactly one non-identity output.
  • The ordering step (Algorithm 3) separates feeding cases, where one function's environment matches the other's output, from bleeding cases, where it matches the other's target. It then uses transitions in the composed machine to decide which function applies first.
  • Complexity results:
    • The characteristic sample is linear in grammar size.
    • The running time is cubic, inherited from OSTIA.
    • Theorem 1 states strong identification in the limit in polynomial time and data.
  • Motivation and future directions:
    • In the Changting dialect, 15 of the 25 possible disyllabic tone pairs undergo sandhi, and each process fits the simplex ISL 2 class.
    • Proposed extensions are k > 2 and more than two composed functions.
    • The work was supported by NSF grant #2416184.

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

 Institutions

🎓Rutgers, The State University of New JerseyNew Brunswick · United States19 works · 11,379 citations

📚 Shelves 6The field of science this work belongs to (OpenAlex fields).Computer Science · 9,086 worksArts and Humanities · 9,296 worksLanguage and Linguistics · 9,206 worksPsychology · 798 worksExperimental and Cognitive Psychology · 463 worksComputational Theory and Mathematics · 116 works

Cite

Cite as Chenli Wang and Adam Jardine. 2026. Learning Process Interaction Through Simplex ISL Transducers. Proceedings of the Society for Computation in Linguistics 2026.

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

@inproceedings{wang2026learning,
  title = {{Learning Process Interaction Through Simplex ISL Transducers}},
  author = {Chenli Wang and Adam Jardine},
  booktitle = {Proceedings of the Society for Computation in Linguistics 2026},
  year = {2026},
  doi = {10.18653/v1/2026.scil-main.28},
  url = {https://doi.org/10.18653/v1/2026.scil-main.28}
}

References

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

  1. Paul Ariste. 1968. A Grammar of the Votic Language. Bloomington: Indiana University Press. find
  2. Eric Baković. 2007. A revised typology of opaque generalisations. Phonology, 24(2):217259. find
  3. Jane Chandlee. 2014. Strictly Local Phonological Processes. Ph.D. thesis, University of Delaware. find
  4. Jane Chandlee, Rémi Eyraund, and Jeffery Heinz. 2015. Output strictly local functions. Proceedings of the 14th Meeting on the Mathematics of Language. find
  5. Colin de la Higuera. 2010. Grammatical Inference: Learning Automata and Grammars. Cambridge University Press. find
  6. Wenyue Hua and Adam Jardine. 2021. Learning input strictly local functions from their composition. In ICGI 15, volume 153, pages 47–65. PMLR. find
  7. Adam Jardine, Jane Chandlee, Rémi Eyraud, and Jeffrey Heinz. 2014. Very efficient learning of structured classes of subsequential functions from positive data. In Proceedings of the 12th International Conference on Grammatical Inference (ICGI 2014), JMLR Workshop Proceedings, pages 94–108. find
  8. Paul Kiparsky. 1973. Abstractness, opacity, and global rules. In Osamu Fujimura, editor, Three dimensions in linguistic theory, pages 57–86. Tokyo: TEC. find
  9. M. Lothaire. 2005. Applied Combinatorics on Words. Cambridge University Press. find
  10. David Odden. 2005. Introducing Phonology. Cambridge University Press. find
  11. 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. find
  12. Jacques Sakarovitch. 2009. Elements of Automata Theory. Cambridge University Press. find
  13. Marcel Paul Schützenberger. 1977. Sur une variante des fonctions séquentielles. Theoretical Computer Science, 4:47–57. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/wang-2026-learning-process-interaction-through-simplex/