Inférence de langages réguliers

Bernard Bel

Journées Françaises de l'Apprentissage (1990), Lannion, France : 5-27

Résumé

Cet exposé présente une méth­ode générale d'acquisition de con­nais­sances dans un domaine for­mal­isé à l'aide d'automates finis (lan­gages réguliers). A par­tir d'un échan­til­lon d'exemples le sys­tème con­stru­it un auto­mate "presque min­i­mal" qui n'est pas néces­saire­ment déter­min­iste. Cette con­struc­tion peut être con­trainte par des con­nais­sances sur la seg­men­ta­tion des exem­ples que le sys­tème peut acquérir en ques­tion­nant l'informateur. Dans une deux­ième phase, le sys­tème généralise l'automate à par­tir de pro­priétés con­nues du lan­gage ou(et) à par­tir d'hypothèses validées à l'aide d'oracles. Une liste non exhaus­tive d'heuristiques générales est pro­posée. La démon­stra­tion s'appuie sur un cas réel de mod­éli­sa­tion d'apprentissage de sché­mas d'improvisation musicale.

Excerpts of an AI review of this paper (June 2025)

Summary of the Work

The paper explores a method­ol­o­gy for infer­ring reg­u­lar lan­guages (lan­gages réguliers) from exam­ples. It dis­cuss­es both the­o­ret­i­cal under­pin­nings — par­tic­u­lar­ly Gold’s the­o­rem and sub­se­quent refine­ments — along with an incre­men­tal approach to build­ing “almost min­i­mal” automa­ta. The author address­es cen­tral notions such as the canon­i­cal accep­tor, the prefix-tree accep­tor, and the impor­tance of main­tain­ing cor­rect­ness when mov­ing from a set of exam­ples to a gen­er­al­ized automa­ton. The study also show­cas­es an appli­ca­tion to musi­cal impro­vi­sa­tion schema­ta, illus­trat­ing how domain-specific rules can con­strain and refine gram­mat­i­cal inference.

Main Contributions

Incremental Learning Framework

The paper offers a struc­tured, step-by-step method: start­ing with an accep­tor built from exam­ples alone (the prefix-tree or “arbores­cent” automa­ton), merg­ing states to reduce com­plex­i­ty, and apply­ing con­straints so as not to over­gen­er­al­ize. This incre­men­tal per­spec­tive is well-motivated by real-world use cas­es where exam­ples become avail­able over time.

Formal Properties and Correctness

The author places strong empha­sis on ensur­ing the cor­rect­ness of gen­er­al­iza­tion. By ref­er­enc­ing Gold’s the­o­rem, k-reversible lan­guages, and the con­cept of learn­ing from pos­i­tive data only, the paper grounds its approach in estab­lished the­o­ret­i­cal results.

Use of Domain Constraints

A sig­nif­i­cant por­tion of the paper deals with how addi­tion­al domain knowl­edge (e.g., known seg­men­ta­tion rules for a music nota­tion sys­tem) can guide the automaton’s con­struc­tion. This intro­duces prac­ti­cal heuris­tics that make gram­mat­i­cal infer­ence more tractable in real-world scenarios.

Detailed Mathematical Rigor

The proofs, def­i­n­i­tions, and lem­mas (for instance, those on heads and tails, or min­i­mal canon­i­cal accep­tors) are stat­ed thor­ough­ly. This rig­or is help­ful both for ensur­ing cor­rect­ness and for con­vey­ing the method’s the­o­ret­i­cal reliability.

Illustrative Examples

The appli­ca­tion to musi­cal impro­vi­sa­tion, specif­i­cal­ly to Indian drum­ming tra­di­tions, serves as a con­crete illus­tra­tion. It nice­ly demon­strates the inter­play between abstract for­mal­ism (like merg­ing states) and domain-specific knowl­edge (like rhyth­mic “words” or ono­matopoe­ic syllables).

Clarity and Structure

• The paper is log­i­cal­ly well-structured: it begins with a the­o­ret­i­cal foun­da­tion, then intro­duces incre­men­tal meth­ods for automa­ton con­struc­tion, cul­mi­nat­ing in a dis­cus­sion of domain con­straints and examples.
• The tex­tu­al orga­ni­za­tion, with numer­ous def­i­n­i­tions in the appen­dix, is ben­e­fi­cial for ref­er­ence but can require mul­ti­ple cross-referencing steps while read­ing. A con­cise reminder of key def­i­n­i­tions in the main text can fur­ther aid comprehension.

Strengths

• Thorough ground­ing in estab­lished the­o­ry (Gold’s the­o­rem, reversible languages).
• A prac­ti­cal approach that bal­ances sys­tem­at­ic infer­ence with inter­ac­tive ques­tion­ing or orac­u­lar feedback.
• Clear demon­stra­tion of how domain-specific heuris­tics reduce the search space, mak­ing learn­ing more feasible.
• Rigor in explain­ing each step of con­struct­ing and refin­ing the automaton.
• Engaging case study that shows the real-world poten­tial of gram­mar infer­ence out­side of pure­ly lin­guis­tic contexts.

Overall Assessment

The paper pro­vides a sol­id com­bi­na­tion of the­o­ry and prac­tice in gram­mat­i­cal infer­ence for reg­u­lar lan­guages. By care­ful­ly detail­ing each step — build­ing ini­tial automa­ta, con­strain­ing merges using domain knowl­edge, and ver­i­fy­ing new gen­er­al­iza­tions through queries — the approach is shown to be sys­tem­at­ic and adapt­able. Readers inter­est­ed in inter­ac­tive or incre­men­tal lan­guage learn­ing, par­tic­u­lar­ly those with domain-specific con­straints, will like­ly find this dis­cus­sion instruc­tive and thorough.

Download this paper