@inproceedings{hung-etal-2026-information,
title = "An Information-Theoretic Foundation for the Subregular Hierarchy",
author = "Hung, Mai Phan Quoc and
Quoc, Khanh Nguyen and
Luong, {\DJ}o{\`a}n Minh and
Ngan, Duong Thu and
Thao, Duong Thi Phuong and
Do, Tuan",
editor = "Liakata, Maria and
Moreira, Viviane P. and
Zhang, Jiajun and
Jurgens, David",
booktitle = "Proceedings of the 64th Annual Meeting of the {A}ssociation for {C}omputational {L}inguistics (Volume 1: Long Papers)",
month = jul,
year = "2026",
address = "San Diego, California, United States",
publisher = "Association for Computational Linguistics",
url = "https://aclanthology.org/2026.acl-long.2153/",
pages = "46417--46429",
ISBN = "979-8-89176-390-6",
abstract = "The Subregular Hypothesis posits that phonological patterns in natural languages occupy a restricted region of the formal language hierarchy, yet the cognitive basis for this restriction remains unclear. We propose an information-theoretic characterization: Strictly Local languages, when formalized as shifts of finite type, are exactly those admitting stationary Markov sources, which exhibit zero conditional mutual information between distant positions given intervening symbols. We prove that certain non-subregular patterns such as first-last assimilation admit no such Markov realization, explaining their unlearnability. Empirical validation on English phonotactics versus Finnish, Turkish, and Hungarian vowel harmony confirms that MI profiles statistically distinguish SL-like from TSL-like patterns ($p < 0.001$, $r = 0.84$). This work bridges formal language theory and information theory, offering a unified framework for understanding computational restrictions on natural language phonology."
}<?xml version="1.0" encoding="UTF-8"?>
<modsCollection xmlns="http://www.loc.gov/mods/v3">
<mods ID="hung-etal-2026-information">
<titleInfo>
<title>An Information-Theoretic Foundation for the Subregular Hierarchy</title>
</titleInfo>
<name type="personal">
<namePart type="given">Mai</namePart>
<namePart type="given">Phan</namePart>
<namePart type="given">Quoc</namePart>
<namePart type="family">Hung</namePart>
<role>
<roleTerm authority="marcrelator" type="text">author</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Khanh</namePart>
<namePart type="given">Nguyen</namePart>
<namePart type="family">Quoc</namePart>
<role>
<roleTerm authority="marcrelator" type="text">author</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Đoàn</namePart>
<namePart type="given">Minh</namePart>
<namePart type="family">Luong</namePart>
<role>
<roleTerm authority="marcrelator" type="text">author</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Duong</namePart>
<namePart type="given">Thu</namePart>
<namePart type="family">Ngan</namePart>
<role>
<roleTerm authority="marcrelator" type="text">author</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Duong</namePart>
<namePart type="given">Thi</namePart>
<namePart type="given">Phuong</namePart>
<namePart type="family">Thao</namePart>
<role>
<roleTerm authority="marcrelator" type="text">author</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Tuan</namePart>
<namePart type="family">Do</namePart>
<role>
<roleTerm authority="marcrelator" type="text">author</roleTerm>
</role>
</name>
<originInfo>
<dateIssued>2026-07</dateIssued>
</originInfo>
<typeOfResource>text</typeOfResource>
<relatedItem type="host">
<titleInfo>
<title>Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)</title>
</titleInfo>
<name type="personal">
<namePart type="given">Maria</namePart>
<namePart type="family">Liakata</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Viviane</namePart>
<namePart type="given">P</namePart>
<namePart type="family">Moreira</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Jiajun</namePart>
<namePart type="family">Zhang</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">David</namePart>
<namePart type="family">Jurgens</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<originInfo>
<publisher>Association for Computational Linguistics</publisher>
<place>
<placeTerm type="text">San Diego, California, United States</placeTerm>
</place>
</originInfo>
<genre authority="marcgt">conference publication</genre>
<identifier type="isbn">979-8-89176-390-6</identifier>
</relatedItem>
<abstract>The Subregular Hypothesis posits that phonological patterns in natural languages occupy a restricted region of the formal language hierarchy, yet the cognitive basis for this restriction remains unclear. We propose an information-theoretic characterization: Strictly Local languages, when formalized as shifts of finite type, are exactly those admitting stationary Markov sources, which exhibit zero conditional mutual information between distant positions given intervening symbols. We prove that certain non-subregular patterns such as first-last assimilation admit no such Markov realization, explaining their unlearnability. Empirical validation on English phonotactics versus Finnish, Turkish, and Hungarian vowel harmony confirms that MI profiles statistically distinguish SL-like from TSL-like patterns (p < 0.001, r = 0.84). This work bridges formal language theory and information theory, offering a unified framework for understanding computational restrictions on natural language phonology.</abstract>
<identifier type="citekey">hung-etal-2026-information</identifier>
<location>
<url>https://aclanthology.org/2026.acl-long.2153/</url>
</location>
<part>
<date>2026-07</date>
<extent unit="page">
<start>46417</start>
<end>46429</end>
</extent>
</part>
</mods>
</modsCollection>
%0 Conference Proceedings
%T An Information-Theoretic Foundation for the Subregular Hierarchy
%A Hung, Mai Phan Quoc
%A Quoc, Khanh Nguyen
%A Luong, Đoàn Minh
%A Ngan, Duong Thu
%A Thao, Duong Thi Phuong
%A Do, Tuan
%Y Liakata, Maria
%Y Moreira, Viviane P.
%Y Zhang, Jiajun
%Y Jurgens, David
%S Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)
%D 2026
%8 July
%I Association for Computational Linguistics
%C San Diego, California, United States
%@ 979-8-89176-390-6
%F hung-etal-2026-information
%X The Subregular Hypothesis posits that phonological patterns in natural languages occupy a restricted region of the formal language hierarchy, yet the cognitive basis for this restriction remains unclear. We propose an information-theoretic characterization: Strictly Local languages, when formalized as shifts of finite type, are exactly those admitting stationary Markov sources, which exhibit zero conditional mutual information between distant positions given intervening symbols. We prove that certain non-subregular patterns such as first-last assimilation admit no such Markov realization, explaining their unlearnability. Empirical validation on English phonotactics versus Finnish, Turkish, and Hungarian vowel harmony confirms that MI profiles statistically distinguish SL-like from TSL-like patterns (p < 0.001, r = 0.84). This work bridges formal language theory and information theory, offering a unified framework for understanding computational restrictions on natural language phonology.
%U https://aclanthology.org/2026.acl-long.2153/
%P 46417-46429
Markdown (Informal)
[An Information-Theoretic Foundation for the Subregular Hierarchy](https://aclanthology.org/2026.acl-long.2153/) (Hung et al., ACL 2026)
ACL
- Mai Phan Quoc Hung, Khanh Nguyen Quoc, Đoàn Minh Luong, Duong Thu Ngan, Duong Thi Phuong Thao, and Tuan Do. 2026. An Information-Theoretic Foundation for the Subregular Hierarchy. In Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 46417–46429, San Diego, California, United States. Association for Computational Linguistics.