Reversible Automata and Induction of the English Auxiliary System

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.