---
title: "Reversible Automata and Induction of the English Auxiliary System"
authors:
  - "Robert C. Berwick"
  - "Samuel F. Pilato"
doi: ""
url: "https://ijcai.org/proceedings/1985/174"
pdf: "https://ijcai.org/proceedings/1985/0174.pdf"
venue: "Proceedings of the Ninth International Joint Conference on Artificial Intelligence"
year: 1985
pages: "880-881"
track: "Natural Language"
keywords:
---

# Reversible Automata and Induction of the English Auxiliary System

Robert C. Berwick, Samuel F. Pilato

*Proceedings of the Ninth International Joint Conference on Artificial Intelligence*, pages 880-881.

## Abstract

Tu thi,; papc•r wc• <tpply somc• rc·n·ut work of Augluin (1982) to t hc· indnction of th<' En~]i,;h auxiliary V<'rh sy:.;t<'m. In ~c'H<'ral , t h(' inclnction of finite• antomata is compntatio11ally iutractah!C'. How<'vc·r . An~lnin ;llow,; tbat r<',;trictPd finite• antomat.a, tlw krcvfr.<ihlt: auto1uala. rau bc· lc•am<'d by d!iri<'nt (polynomial time) al~orit !im;. Wc• pn·".•ul m1 c•x plirit coHtJHII.<T mockl c!Pmomt.ratin~ I bat tll<' Engli,;!J anxiliary wrh syst<'lll can in fact h<' karned a; a1-n•vc-r;ibk antomatou. ancl hc•un• in a rompntat.ionally fc ·a~i hlP illliOtiiJt of liltH'. Thl' <'lllire systemraube acqnin·d by Ionking at nn!y halft ltc• pos;ibk anxiliary wrb s<'qnmcc•s, ancl thP pattcrn of ~ <'nPralizat iou ,;c•c·ms rompat ihll' with what is known abont Imman au]nisition of anxiliarics. We concliak tliitt certain lingnist.ic snb,;ys tc·ms may wdl hc• karnahle by incha:tive infnence methods of this kincJ. ancl su~gC'st an cxtc·nsion to context-frce languagcs.