{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:54:33Z","timestamp":1750308873544,"version":"3.41.0"},"reference-count":14,"publisher":"Association for Computing Machinery (ACM)","issue":"108","license":[{"start":{"date-parts":[[1989,4,1]],"date-time":"1989-04-01T00:00:00Z","timestamp":607392000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGART Bull."],"published-print":{"date-parts":[[1989,4]]},"abstract":"<jats:p>\n            Inductive inference is a learning process based on discovering models for bodies of knowledge, given sample information. The inference process we discuss here is concerned with inductive acquisition of syntactic models for context-free languages (CFLs), given appropriate language samples. The knowledge to be modeled in this case is any CFL\n            <jats:italic>L,<\/jats:italic>\n            with the model to be determined a recognitive or generative characterization of\n            <jats:italic>L's<\/jats:italic>\n            syntactic structure.\n            <jats:italic>L<\/jats:italic>\n            will be learned syntactically once a machine\n            <jats:italic>M<\/jats:italic>\n            recognizing\n            <jats:italic>L,<\/jats:italic>\n            or a context-free grammar (CFG)\n            <jats:italic>G<\/jats:italic>\n            generating\n            <jats:italic>L,<\/jats:italic>\n            is inductively inferred from a sentence sample. The capability of distinguishing between\n            <jats:italic>L<\/jats:italic>\n            and its complement, or of generating all and only\n            <jats:italic>L<\/jats:italic>\n            's sentences, is the knowledge acquired, with the learner (inference process) gaining this knowledge by acquiring\n            <jats:italic>M<\/jats:italic>\n            or\n            <jats:italic>G.<\/jats:italic>\n            An observer (informant, teacher, or oracle) has such knowledge of\n            <jats:italic>L<\/jats:italic>\n            and can provide the learner with appropriate sample information to ensure that\n            <jats:italic>M<\/jats:italic>\n            or\n            <jats:italic>G<\/jats:italic>\n            is correctly identified.\n          <\/jats:p>","DOI":"10.1145\/63266.63306","type":"journal-article","created":{"date-parts":[[2007,1,17]],"date-time":"2007-01-17T18:32:02Z","timestamp":1169058722000},"page":"175-176","update-policy":"https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Learnability of CFLs: inferring syntactic models from constituent structure"],"prefix":"10.1145","author":[{"given":"L. F.","family":"Fass","sequence":"first","affiliation":[{"name":"Naval Postgraduate School, Monterey, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[1989,4]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/356914.356918"},{"key":"e_1_2_1_2_1","unstructured":"Bainbridge E.S. and L.F. Fass \"Minimal Structures for Context-Free Languages \" (project in progress).  Bainbridge E.S. and L.F. Fass \"Minimal Structures for Context-Free Languages \" (project in progress)."},{"key":"e_1_2_1_3_1","unstructured":"Berwick R.C. and S.F. Pilato \"Reversible Automata and Induction of the English Auxiliary System \" IJCAI 85 Vol. 2 pp. 880-882.   Berwick R.C. and S.F. Pilato \"Reversible Automata and Induction of the English Auxiliary System \" IJCAI 85 Vol. 2 pp. 880-882."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/8307.8310"},{"key":"e_1_2_1_5_1","unstructured":"Fass L.F. \"A minimal Deterministic Acceptor for any (Structured) Context-Free Language \" in preparation.  Fass L.F. \"A minimal Deterministic Acceptor for any (Structured) Context-Free Language \" in preparation."},{"volume-title":"Addison-Wesley","year":"1979","author":"Hoproft J.E.","key":"e_1_2_1_7_1"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(78)90849-5"},{"volume-title":"August, 1986.","author":"Lust B.","key":"e_1_2_1_9_1"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/321406.321411"},{"key":"e_1_2_1_11_1","first-page":"57","volume-title":"Rpt.","author":"Myhill J.","year":"1957"},{"key":"e_1_2_1_12_1","first-page":"541","article-title":"Linear Automaton Transformations","author":"Nerode A.","year":"1959","journal-title":"Proc. AMS"},{"key":"e_1_2_1_13_1","first-page":"427","article-title":"Structural Equivalence of Context-Free Languages","volume":"2","author":"Paul M.C.","year":"1968","journal-title":"JCSS"},{"key":"e_1_2_1_14_1","doi-asserted-by":"crossref","unstructured":"Thatcher J.W. \"Characterizing Derivation Trees of Context-Free Languages through a Generalization of Finite Automata Theory \" JCSS (1967) pp. 317-322.  Thatcher J.W. \"Characterizing Derivation Trees of Context-Free Languages through a Generalization of Finite Automata Theory \" JCSS (1967) pp. 317-322.","DOI":"10.1016\/S0022-0000(67)80022-9"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01691346"}],"container-title":["ACM SIGART Bulletin"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/dl.acm.org\/doi\/10.1145\/63266.63306","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/dl.acm.org\/doi\/pdf\/10.1145\/63266.63306","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T21:15:16Z","timestamp":1750281316000},"score":1,"resource":{"primary":{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/dl.acm.org\/doi\/10.1145\/63266.63306"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1989,4]]},"references-count":14,"journal-issue":{"issue":"108","published-print":{"date-parts":[[1989,4]]}},"alternative-id":["10.1145\/63266.63306"],"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.1145\/63266.63306","relation":{},"ISSN":["0163-5719"],"issn-type":[{"type":"print","value":"0163-5719"}],"subject":[],"published":{"date-parts":[[1989,4]]},"assertion":[{"value":"1989-04-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}