Publikace na Matematicko-fyzikální fakulta |
2007
Abstrakt
Je známo několik metod využívajících slévání stavů pro inferenci regulárních jazyků z pozitivních a negativních příkladů. Jedna z nich je algoritmus RPNI, který slévá páry stavů prefix tree acceptoru pozitivních příkladů v pevném pořadní při zachování konzistence výsledného automatu.
Výsledný automat nemusí být optimální. Zakázáním některých slití, která provádí původní algoritmus RPNI, je možno získat lepší automat.
Navrhujeme novou metodu hledání párů stavů, které se nemají slévat pomocí genetických algoritmů a náhodné procházky. Zlepšení oproti původnímu algoritmu RPNI je změřeno experimentálně.