--- title: "Reversible Automata and Induction of the English Auxiliary System" description: "The learner builds a prefix-tree automaton and merges states that share a k-word history. 5 references, cited by 3 papers here." authors: ["Samuel F. Pilato"] year: 1985 venue: "23rd Annual Meeting of the Association for Computational Linguistics" source: "https://aclanthology.org/P85-1009/" doi: "10.3115/981210.981219" licence: "CC BY-NC-SA 3.0 (ACL Anthology, before 2016)" licence_url: "https://creativecommons.org/licenses/by-nc-sa/3.0/" summary_licence: "Elamur Cosmic License" canonical: "https://research.elamur.ai/free/en/papers/pilato-1985-reversible-automata-induction-english-auxiliary/" --- [Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/pilato-1985-reversible-automata-induction-english-auxiliary/) [home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [1985](https://md.research.elamur.ai/free/en/papers/1985/) / Reversible Automata and Induction of the English Auxiliary System # Reversible Automata and Induction of the English Auxiliary System **Authors:** Samuel F. Pilato · **Year:** 1985 · **Venue:** [23rd Annual Meeting of the Association for Computational Linguistics](https://md.research.elamur.ai/free/en/venues/acl/) ([ACL 1985](https://md.research.elamur.ai/free/en/venues/acl/1985/)) · **Publisher:** [Association for Computational Linguistics](https://md.research.elamur.ai/free/en/publishers/association-for-computational-linguistics/) · **Licence:** [CC BY-NC-SA 3.0 (ACL Anthology, before 2016)](https://creativecommons.org/licenses/by-nc-sa/3.0/) **Links:** [Publisher's page](https://aclanthology.org/P85-1009/) · [PDF](https://aclanthology.org/P85-1009.pdf) · [DOI 10.3115/981210.981219](https://doi.org/10.3115/981210.981219) · [OpenAlex](https://openalex.org/W2160137747) **Citations:** 6 citations (OpenAlex, 2026-10-14) · 3 in our library, of the 149,439 papers whose bibliographies we read ## Summary Pilato and Berwick ask whether a general-purpose induction procedure, as opposed to grammar-specific machinery, can acquire a real slice of English syntax. Inferring arbitrary finite automata is computationally intractable. Angluin (1982), however, showed that the restricted class of k-reversible regular languages can be learned in polynomial time from positive examples only. The authors implemented her algorithms in MACLISP and applied them to a corpus of 92 surface-form variants of one third-person singular declarative sentence. The corpus covers tense, aspect, voice, do-support and nine modals. The learner builds a prefix-tree automaton and merges states that share a k-word history. With k ≥ 1 the auxiliary system is modelled exactly, and a covering sample of roughly half the sequences is enough to induce the rest. With k = 0 the learner overgeneralizes: it treats do like a modal and admits endless passive chains. The result suggests that some linguistic subsystems are shaped so that cheap inductive learning works on them. The learner's behaviour also roughly matches what children do with auxiliaries. ## Key points - The corpus has 92 variants of "Judy gives bread" (e.g. *Judy would have been given bread*). They are plain word strings with no POS tags and no morphological analysis. - The full corpus is k-reversible for every k ≥ 1. Zero-reversible inference overgeneralizes the active, passive and joint corpora. In the active corpus it merges do-forms with modals, and in the passive and full corpora it creates loops that generate infinitely many illegal strings. - 1-reversible covering sample: - 45 sequences of length ≤ 3 yield the other nine short ones. - One length-four string of the *modal have been giv(ing/en)* pattern yields 17 more. - Two strings from the awkward *…be being given* pattern yield the remaining 18, nine of which have length five. - Suppose do-support and the *BE being* cases are handled externally and active and passive are kept separate. Then 0-reversible inference learns the active system from 18 of 44 variants and the passive from 14 of 22. - The induced language does not depend on the order in which examples arrive. The paper proposes extending the method to context-free rule sets, citing Berwick's LParsifal (1982). ## Interesting ideas - Generalization is controlled by a single knob, k: two states with a shared tail are merged only if their last k words also agree, so k directly trades inductive reach against overgeneralization. - Angluin's algorithm can be run in reverse to compute the minimal characteristic sample needed to induce a known language. This shows exactly which examples carry the information. - Negative examples are used to choose k: keep raising k until every one of them falls outside the language the learner induces. This is a clean stopping rule for generalization. - The authors keep raw induction powerful but route a few rare exceptions (do-support, *being* passives) to a separate mechanism. They argue this is better than weakening the learner everywhere. - A rare but legal form such as *could have been being given* is accepted without ever being seen, because a few neighbouring examples imply it. The automaton itself is compact and readable as a grammar. ## For Mova How these ideas could serve Mova, our small open language model — its files, stages and tests: - **I1** (learn): self-induced repair rules could be generalized only when their left context of length k matches, with k raised until negative controls stop firing. - **I2** (learn): computing a covering sample for a pattern family (e.g. verb-chain shapes) would show which silver sentences are worth an LLM teacher's attention and which are redundant. - **I3** (learn): it fits Mova's negative-control evaluation, where known-bad strings act as the automatic brake on how far an induced rule may generalize. - **I4** (tokens): auxiliary-chain tagging could use a small reversible automaton for regular have/be/modal sequences, with explicit exception handling for do-support, keeping each decision traceable. - **I5** (back): a minimized auxiliary DFA could drive generation of verb groups, so every produced tense/aspect/voice combination comes from a checkable path rather than from memorized strings. *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 - [Massachusetts Institute of Technology](https://md.research.elamur.ai/free/en/universities/massachusetts-institute-of-technology/) — University, Cambridge, United States · 243 works · 76,506 citations - [MIT Computer Science and Artificial Intelligence Laboratory](https://md.research.elamur.ai/free/en/labs/mit-computer-science-and-artificial-intelligence-laboratory/) — Research institute, Cambridge, United States · 76 works · 32,207 citations 📚 Shelves (5): [🖥️ Computer Science](https://md.research.elamur.ai/free/en/shelves/computer-science/) · 18,614 works · [🤖 Artificial Intelligence](https://md.research.elamur.ai/free/en/shelves/computer-science/artificial-intelligence/) · 17,965 works · [🎭 Arts and Humanities](https://md.research.elamur.ai/free/en/shelves/arts-and-humanities/) · 17,450 works · [🗣️ Language and Linguistics](https://md.research.elamur.ai/free/en/shelves/arts-and-humanities/language-and-linguistics/) · 17,296 works · [🧮 Computational Theory and Mathematics](https://md.research.elamur.ai/free/en/shelves/computer-science/computational-theory-and-mathematics/) · 321 works 🧭 Topics (1): [English](https://md.research.elamur.ai/free/en/topics/english/) · 2,379 works ## Cite Cite as: Samuel F. Pilato. 1985. Reversible Automata and Induction of the English Auxiliary System. 23rd Annual Meeting of the Association for Computational Linguistics. The paper itself, not this page. BibTeX from the library's record of the work. ```bibtex @inproceedings{pilato1985reversible, title = {{Reversible Automata and Induction of the English Auxiliary System}}, author = {Samuel F. Pilato}, booktitle = {23rd Annual Meeting of the Association for Computational Linguistics}, year = {1985}, doi = {10.3115/981210.981219}, url = {https://doi.org/10.3115/981210.981219} } ``` - [← previous A Survey of Machine Translation: Its History, Current Status and Future Prospects](https://md.research.elamur.ai/free/en/papers/slocum-1985-survey-machine-translation-its-history/) - [next → Grammatical Analysis by Computer of the Lancaster-Oslo/Bergen (LOB) Corpus of British English Texts](https://md.research.elamur.ai/free/en/papers/david-1985-grammatical-analysis-computer-lancaster-oslo/) - [↑ back to papers of 1985](https://md.research.elamur.ai/free/en/papers/1985/) ## References 5 references, 0 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet. 1. Angluin, D., "Inference of reversible laugalages," Journal of the A.~sociation /or Computing Machinery, 29(3), 741-765, 1982. [find](https://scholar.google.com/scholar?q=Angluin%2C+D%2E%2C+%22Inference+of+reversible+laugalages%2C%22+Journal+of+the+A%2E%7Esociation+%2For+Computing+Machinery%2C+29%283%29%2C+741%2D765%2C+1982%2E) 2. Berwick, R., Locality Principles and the ..lcquisitton o/ Syntactic Knowledge, PhD, MIT Department cf Electrical Engineering ,and Computer Science, 1982. [find](https://scholar.google.com/scholar?q=Berwick%2C+R%2E%2C+Locality+Principles+and+the+%2E%2Elcquisitton+o%2F+Syntactic+Knowledge%2C+PhD%2C+MIT+Department+cf+Electrical+Engineering+%2Cand+Computer+Science%2C+1982%2E) 3. Gold, E., "Complexity of Automaton Identification from Given Data," Information and Control, 37, 1978. [find](https://scholar.google.com/scholar?q=Gold%2C+E%2E%2C+%22Complexity+of+Automaton+Identification+from+Given+Data%2C%22+Information+and+Control%2C+37%2C+1978%2E) 4. Gonzalez, R., ztnd Thmnason, M., Syntactic Pattern Recognition, Reading, MA: Addison-Wesley, 1978. [find](https://scholar.google.com/scholar?q=Gonzalez%2C+R%2E%2C+ztnd+Thmnason%2C+M%2E%2C+Syntactic+Pattern+Recognition%2C+Reading%2C+MA%3A+Addison%2DWesley%2C+1978%2E) 5. Pinker, S., Language 5earnability and Language Development, Cambridge: MA: Harvard University Press, 1984. [find](https://scholar.google.com/scholar?q=Pinker%2C+S%2E%2C+Language+5earnability+and+Language+Development%2C+Cambridge%3A+MA%3A+Harvard+University+Press%2C+1984%2E) *Updated 2 November 2026*