Abstract
Regular language learning from positive examples alone is infeasible. Subclasses of regular languages, though, can be inferred from positive examples only. The most common approach for learning such is the specific-to-general technique of merging together either states of an initial finite state automaton or nonterminals in a regular grammar until convergence.
In this paper we seek to unify some language learning approaches under the general-to-specific learning scheme. In automata terms it is implemented by refining the partition of the states of the automaton starting from one block until desired decomposition is obtained; i.e., until all blocks in the partition are uniform according to the predicate determining the properties required from the language.
We develop a series of learning algorithms for well-known classes of regular languages as instantiations of the same master algorithm. Through block decomposition we are able to describe in the same scheme, e.g., the learning by rote approach of minimizing the number of states in the automaton and inference of k-reversible languages.
Under the worst-case analysis partition-refinement is less efficient than alternative approaches. However, for many cases it turns out more efficient in practice. Moreover, it ensures the inference of the canonical automaton, whereas the state-merging approach will leave excessive states to the final automaton without a separate minimization step.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Ahonen, H., Mannila, H., Nikunen, E.: Forming grammars for structured documents: An application of grammatical inference. In: Carrasco, R., Oncina, J. (eds.): Proc. Second International Colloquium on Grammatical Inference and Applications. Lecture Notes in Computer Science 862. Springer-Verlag, (1994) 153–167
Angluin, D.: Inference of reversible languages. J. ACM 29 (1982) 741–765
Bierman, A.W., Feldman, J.A. On the synthesis of finite-state machines from samples of their behavior. IEEE Trans. Comput. 21 (1972) 592–597
Firoiu, L., Oates, T., Cohen, P.R.: Learning regular languages from positive evidence. In: Proc. Twentieth Annual Meeting of the Cognitive Science Society. (1998) 350–355
Gold, E.M.: Language identification in the limit. Inf. Control 37 (1967) 302–320
Hopcroft, J.E.: An n log n algorithm for minimizing the states in a finite automaton. In: Kohavi, Z. (ed.): The Theory of Machines and Computations. Academic Press, New York (1971) 189–196
Hopcroft, J.E., Motwani, R., and Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation. 2nd Ed. Addison-Wesley, Reading, MA: (2001)
Itoga, S.Y.: A new heuristic for inferring regular grammars. IEEE Trans. Pattern Anal. Mach. Intell. 3 (1981) 191–197
Koshiba, T., Mäkinen, E., Takada, Y.: Learning deterministic even linear languages from positive examples. Theor. Comput. Sci. 185 (1997) 63–79
Levine, B.: The use of tree derivatives and a sample support parameter for inferring tree systems. IEEE Trans. Pattern Anal. Mach. Intell. 4 (1982) 25–34
Mäkinen, E.: Inferring regular languages by merging nonterminals. Int. J. Comput. Math. 70 (1999) 601–616
Mäkinen, E.: On inferring zero-reversible languages. Acta Cybernetica 14 (2000) 479–484
Mäkinen, E.: On inferring linear single-tree languages. Inf. Process. Lett. 73 (2000) 1–3
Miclet, L.: Regular inference with a tail clustering method. IEEE Trans. Syst. Man Cybern. 10 (1980) 737–743
Muggleton, S.: Inductive Acquisition of Expert Knowledge. Addison-Wesley, Wokingham, UK (1990)
Muggleton, S.: Learning from positive data. Mach. Learn., to appear
Pitt, L., Warmuth, M.K.: The minimum consistent DFA problem cannot be approximated within any polynomial. In: Proceedings of the Twenty First Annual ACM Symposium on Theory of Computing. New York: ACM Press (1989) 421–432.
Sakakibara, Y.: Recent advances of grammatical inference. Theor. Comput. Sci. 185 (1997) 15–45
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Elomaa, T. (2002). Partition-Refining Algorithms for Learning Finite State Automata. In: Hacid, MS., Raś, Z.W., Zighed, D.A., Kodratoff, Y. (eds) Foundations of Intelligent Systems. ISMIS 2002. Lecture Notes in Computer Science(), vol 2366. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-48050-1_27
Download citation
DOI: https://doi.org/10.1007/3-540-48050-1_27
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-43785-7
Online ISBN: 978-3-540-48050-1
eBook Packages: Springer Book Archive