The MathNet Korea
Information Center for Mathematical Science

논문검색

Information Center for Mathematical Science

논문검색

SIAM Journal on Computing
( Vol. 25 NO.6 / (1996))
Learning Behaviors of Automata from Multiplicity and Equivalence Queries
Francesco Bergadano, Stefano Varricchio,
Pages. 1268-1280
Abstract We consider the problem of identifying the behavior of an unknown automaton with multiplicity in the field $Q$ of rational numbers $(Q$-automaton) from multiplicity and equivalence queries. We provide an algorithm which is polynomial in the size of the $Q$-automaton and in the maximum length of the given counterexamples. As a consequence, we have that $Q$-automata are probably approximately correctly learnable (PAC-learnable) in polynomial time when multiplicity queries are allowed. A corollary of this result is that regular languages are polynomially predictable using membership queries with respect to the representation of unambiguous nondeterministic automata. This is important since there are unambiguous automata such that equivalent deterministic automaton has an exponentially larger number of states.
Contents 1. Introduction
2. Multiplicity automata
3. Observation tables
4. The learning algorithm
4.1. Closing a table
4.2. Making tables consistent
4.3. The algorithm
4.4. Complexity analysis
5. Complete sets of strings
6. PAC-learnability and extensions
Key words PAC-learning, exact identificaton, learning from examples, learning from queries, equivalence queries, multiplicity queries, membership queries, multiplicity automata, probabilistic automata, unambiguous nondeterministic automata.
Mathmatical Subject Classification 68Q68, 68Q70, 68Q75, 68T05