Paper

A Family of Effective Methods for Decompiling Canonical Acceptors, Instantiated for Languages of Dot-Depth One and Tier-Based Extensions

---

Abstract

Many kinds of logical systems have been employed in constructing formal languages to model phonological phenomena. A common theme among them is that the systems compile into finite automata. Two questions naturally arise. Can a given phenomenon be described with another logical system? And, if so, what is that description?

To the first question, algebraic techniques are well established through deep connections with logic and automata. To the second, the situation is less clear. Translations from automata are established for first-order and monadic second-order logics under precedence, but these may not translate easily to the simpler systems we often use. Translations for simple cases of restricted propositional logic (strictly local or strictly piecewise languages) are established, but insufficient to describe attested phenomena.

The present work establishes a general way to handle many systems in between. Specifically, we show how to translate between certain kinds of algebraic varieties 𝐕 (systems defined by universally satisfied identities) and associated logical systems, then use decomposition to handle classes of the form 𝐕∗𝐃, where the notion of ``symbol'' is replaced by “𝑘-block”. With this, we handle several (unrestricted) propositional logics, facilitating logical description of natural language.

Keywords: formal languages, factoring, automata, finite-state automata, algebra

How to Cite:

Lambert, D., (2026) “A Family of Effective Methods for Decompiling Canonical Acceptors, Instantiated for Languages of Dot-Depth One and Tier-Based Extensions”, Society for Computation in Linguistics 9(1). doi: https://doi.org/10.7275/scil.4031