Grammar Inference Based on Passive Learning and Genetic Algorithm
Pages 87 - 92
Abstract
The mathematical model of a deterministic finite automaton has a wide potential of application, for instance, in control systems. Some of that systems are not trivial and can be defined only in terms of formal language theory. In this paper, we propose a new model for grammar inference, i.e. synthesizing of a deterministic finite automaton by a list of positive and negative examples. We present the results of testing developed model on formal grammars of various complexity.
References
[1]
Angluin D. 1982. Inference of reversible languages. Journal of the ACM (JACM) 29, 3, 741--765
[2]
Bahlke. R., and Snelting., G. 1986. The PSG system: from formal language definitions to interactive programming environments. ACM Transactions on Programming Languages and Systems (TOPLAS) 8, 4, 547--576
[3]
Carrasco, R.C., and Oncina, J. 1994. Learning stochastic regular grammars by means of a state merging method. In Proceedings of International Colloquium on Grammatical Inference (Alicante, Spain, September 21--23, 1994). Springer, 139--152
[4]
Domaratzki, M., Okhotin, A., Salomaa, K., and Yu, S. 2004. Report on CIAA 2004. In Proceedings of 9th International Conference on Implementation and Application of Automata:, (Kingston, Canada, July 22--24, 2004). Springer, 135--145
[5]
Giles, C. L., Chen, D., Miller, C.B., Chen, H.H., Sun, G.Z., and Lee, Y.C. 1991. Second-order recurrent neural networks for grammatical inference. In International Joint Conference on Neural Networks (Seattle, WA, USA, July 8--12, 1991). IEEE, 273--281
[6]
Gold E.M, 1978. Complexity of automaton identification from given data. Information and control 37, 3, 302--320
[7]
Gold E.M. 1967. Language identification in the limit. Information and control 10, 5, 447--474
[8]
Grachev, P., Lobanov, I., Smetannikov, I., and Filchenkov, A. 2017. Neural network for synthesizing deterministic finite automata. Procedia computer science 119, 73--82
[9]
Gribkoff, E. 2013. Applications of Deterministic Finite Automata. ECS 120 UC Davis
[10]
Higuera. C., 2010. Grammatical inference: Learning Automata and Grammars. Cambridge University Press
[11]
Hoare, C.A.R., and Wirth, N., 1973. An axiomatic definition of the programming language PASCAL. Acta Informatica, 2, 4, 335--355
[12]
Kate, R.J., Wong, Y.W., and Mooney, R.J. 2005. Learning to transform natural to formal languages. In Proceedings of the National Conference on Artificial Intelligence (Pittsburgh, Pennsylvania, USA, July 9--13, 2005). AAAI Press
[13]
Lambeau, B. and Damas, C. and Dupont, P. 2008. State-merging DFA induction algorithms with mandatory merge constraints. In Proceedings of the International Colloquium on Grammatical Inference (Saint-Malo, France, September 22--24, 2008). Springer, 139--153
[14]
Lucas, S.M., and Reynolds, T.J. 2008. Learning DFA: evolution versus evidence driven state merging. In Proceedings of the 2003 Congress on Evolutionary Computation (Canberra, Australia, December 8--12, 2003). IEEE, 351--358
[15]
Manolios, P., and Fanelli, R. 1994. First-order recurrent neural networks and deterministic finite state automata. Neural Computation 6, 6, 1155--1173
[16]
Mayr, F., and Yovine, S. 2018. Regular Inference on Artificial Neural Networks. In International Cross-Domain Conference for Machine Learning and Knowledge Extraction (Hamburg, Germany, August 27--30, 2018). Springer, 350--369
[17]
Sakarovitch, J. 2009. Elements of automata theory. Cambridge University Press
[18]
Ulyantsev, V., and Tsarev, F. 2011. Extended finite-state machine induction using SAT-solver. In 10th International Conference on Machine Learning and Applications and Workshops (ICMLA), 2011 (Honolulu, Hawaii, December 18--21, 2011). IEEE, 346--349
[19]
Ulyantsev, V., Zakirzyanov, I., and Shalyto, A., 2015. BFS-based symmetry breaking predicates for DFA identification. In International Conference on Language and Automata Theory and Applications, 2015 (Nice, France, March 2--6, 2015). Springer, 611--622
[20]
Van Fraasen B.C., 1971. Formal semantics and logic, Macmillan
[21]
Zeng, Z., Goodman, R. M., and Smyth, P. 1993. Self-clustering recurrent networks. In Proceedings of IEEE International Conference on Neural Networks, 1993 (San Francisco, CA, USA, March 28 - April 1, 1993). IEEE, 33--38
Index Terms
- Grammar Inference Based on Passive Learning and Genetic Algorithm
Recommendations
Reputational Genetic Model for Regular Inference
ICAIP '19: Proceedings of the 2019 3rd International Conference on Advances in Image ProcessingThe regular inference is one of the main problems of the formal language theory, which is to synthesize a finite-state automaton corresponding to some unknown regular language represented with a list of positive and negative examples. In this paper, we ...
Exploring the Relationship between the Structural and the Actual Similarities of Automata
ICMLSC '19: Proceedings of the 3rd International Conference on Machine Learning and Soft ComputingOne of the most common representations of formal languages is deterministic finite-state automata. In recent years, a bunch of papers dedicated to the problem of synthesizing such an automaton by a list of positive and negative examples of some formal ...
Grammar Inference with Multiparameter Genetic Model
ICAIP '19: Proceedings of the 2019 3rd International Conference on Advances in Image ProcessingThe problem of regular inference is of interest in the formal language theory and its conjugates. In recent years, models have been proposed that solve this problem using machine learning methods. In this paper, we present a brand new model for regular ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
January 2019
268 pages
ISBN:9781450366120
DOI:10.1145/3310986
Copyright © 2019 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 25 January 2019
Check for updates
Author Tags
Qualifiers
- Research-article
- Research
- Refereed limited
Funding Sources
- Russian Ministry of Science and Higher Education
Conference
ICMLSC 2019
ICMLSC 2019: 2019 the 3rd International Conference on Machine Learning and Soft Computing
January 25 - 28, 2019
Da Lat, Viet Nam
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 87Total Downloads
- Downloads (Last 12 months)3
- Downloads (Last 6 weeks)0
Reflects downloads up to 19 Feb 2025
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in