Name
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 states would 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 state-merging techniques: they can be extended to take any pair of DFAs as inputs rather than simple strings. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1007/978-3-540-88009-7_11 | ICGI |
Keywords | Field | DocType |
state-merging algorithm,negative information,state-merging technique,standard state-merging dfa induction,abbadingo contest protocol,state-merging dfa induction algorithms,mandatory merge constraints,interesting property,domain knowledge,negative string,incompatible state,inconsistent dfa,regular language,side effect | Domain knowledge,Deterministic finite automaton,Computer science,CONTEST,Algorithm,Regular language,Merge (version control) | Conference |
Volume | ISSN | Citations |
5278 | 0302-9743 | 10 |
PageRank | References | Authors |
0.65 | 10 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Bernard Lambeau | 1 | 197 | 9.79 |
| Christophe Damas | 2 | 196 | 9.08 |
| Pierre Dupont | 3 | 380 | 29.30 |