Efficient Induction of Finite State Automata

2013/02/06 by Matthew S. Collins, Collins, Matthew S., Jonathan Oliver +1
Computer Science · #Artificial Intelligence (cs.AI) #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #cs.AI #cs.FL

paper · pdf · doi:10.48550/arxiv.1302.1530

Appears in Proceedings of the Thirteenth Conference on Uncertainty in Artificial Intelligence (UAI1997)

arxiv created 2013/02/06 · arxiv updated 2013/02/08

Abstract

This paper introduces a new algorithm for the induction if complex finite state automata from samples of behavior. The algorithm is based on information theoretic principles. The algorithm reduces the search space by many orders of magnitude over what was previously thought possible. We compare the algorithm with some existing induction techniques for finite state automata and show that the algorithm is much superior in both run time and quality of inductions.

Related

• IDS: An Incremental Learning Algorithm for Finite Automata
• A lower bound on the state complexity of transforming two-way nondeterministic finite automata to unambiguous finite automata
• A Close Analysis of the Subset Construction
• Learning Several Languages from Labeled Strings: State Merging and Evolutionary Approaches
• Simulations and Antichains for Efficient Handling of Finite Automata