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 of the maximum length of the given counterexamples. As a consequence, we have that Q-automata are 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 w.r.t. the representation of unambiguous non-deterministic automata. This is important, as there are unambiguous automata such that the equivalent deterministic automaton has an exponentially larger number of states.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
A. V. Aho, J. E. Hopcroft and J. D. Ullman, The Design and Analysis of Computer Algorithms Addison-Wesley, 1974.
D. Angluin. On the complexity of minimum inference of regular sets. Information and Control, 39:337–350, 1978.
D. Angluin. A note on the number of queries needed to identify regular languages. Information and Control, 51:76–87, 1981.
D. Angluin. Learning regular sets from queries and counterexamples. Information and Computation, 75:87–106, 1987.
D. Angluin. Negative results for equivalence queries. Machine Learning, 5:121–150, 1990.
F. Bergadano and A. Giordana and L. Saitta. Machine Learning: an Integrated Framework and its Applications Ellis Horwood, 1991.
F. Bergadano and D. Gunetti. An Interactive System to Learn Functional Logic Programs. Proc. Int. Joint Conf. on Artificial Intelligence, Morgan Kaufmann, 1993.
J. Berstel and C. Reutenauer. Rational series and their languages Springer-Verlag, Berlin, 1988.
S. Eilenberg. Automata, Languages and Machines Vol. A, Academic Press, New York, 1974.
M. E. Gold. Complexity of automaton identification from given data. Information and Control, 37:302–320, 1978.
T. Harju and J. Karhumaki. Decidability of the multiplicity equivalence problem of multitape finite automata Proc. 22nd STOC, 477–481, (1990).
B. K. Natarajan. Machine Learning: a Theoretical Approach Morgan Kaufmann, 1991.
L. Pitt and M. K. Warmuth. The Minimum Consistent DFA Problem Cannot be Approximated within any Polynomial. Journal of the ACM, 40:95–142, 1993.
A. Salomaa and M. Soittola. Automata theoretic aspects of formal power series Springer-Verlag, New York, 1978.
R. E. Stearns and H. B. Hunt. On the Equivalence and Containment Problems for Unambiguous Regular Expressions, Regular Grammars and Finite Automata SIAM J. Comput., 14:3,598–611, 1985.
S. Varricchio. On the decidability of the equivalence problem for partially commutative rational power series Theoretical Computer Science, 99: 291–299, 1992.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1994 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bergadano, F., Varricchio, S. (1994). Learning behaviors of automata from multiplicity and equivalence queries. In: Bonuccelli, M., Crescenzi, P., Petreschi, R. (eds) Algorithms and Complexity. CIAC 1994. Lecture Notes in Computer Science, vol 778. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-57811-0_6
Download citation
DOI: https://doi.org/10.1007/3-540-57811-0_6
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-57811-6
Online ISBN: 978-3-540-48337-3
eBook Packages: Springer Book Archive