State-merging DFA Induction Algorithms with Mandatory Merge Constraints

Lambeau, Bernard;Damas, Christophe;Dupont, Pierre
(2008) 9th International Colloquium on Grammatical Inference (ICGI) — ISBN: [978-3-540-88008-0], p. 139-153, published

Files

state.pdf
  • Restricted Access
  • Adobe PDF
  • 1.06 MB
Request a copy

Details

Authors
  • Lambeau, BernardUCLouvain
    Author
  • Damas, ChristopheUCLouvain
    Author
  • Dupont, PierreUCLouvain
    Author
Abstract
Standard state-merging DFA induction algorithms, such as RPNI or Blue-Fringe, aim at inferring a regular language from positive and negative strings. In particular, the negative information prevents merging incompatible states:merging those stateswould lead to produce an inconsistent DFA.Whenever available, domain knowledge can also be used to extend the set of incompatible states. We introduce here mandatory merge constraints, which form the logical counterpart to the usual incompatibility constraints. We show how state-merging algorithms can benefit from these new constraints. Experiments following the Abbadingo contest protocol illustrate the interest of using mandatory merge constraints. As a side effect, this paper also points out an interesting property of statemerging techniques: they can be extended to take any pair of DFAs as inputs rather than simple strings.
Affiliations

Citations

  • APA
  • Chicago
  • FWB

Lambeau, B., Damas, C., & Dupont, P. (2008). State-merging DFA Induction Algorithms with Mandatory Merge Constraints. In 9th International Colloquium on Grammatical Inference (ICGI) (p. p. 139-153). Springer-Verlag. https://hdl.handle.net/2078.5/253812