Tutorial on Automata Learning

In this tutorial we will get acquainted with the research area called grammatical inference or automata learning. We will start with the earliest results on the subject, and span different learning paradigms. We will describe several positive results, and efficient algorithms for learning regular languages in various different formalisms, including deterministic, non-deterministic and alternating automata. We will prove several negative results for learning different classes of languages in different learning paradigms. We will discuss connection between learning problems and other problems in automata theory.

Authors

• Dana Fisman Ben-Gurion University

Keywords

No keywords are indexed for this paper.