Inductive Synthesis of Cover-Grammars with the Help of Ant Colony Optimization

Wieczorek, Wojciech

doi:10.1515/fcds-2016-0016

Abstract

A cover-grammar of a finite language is a context-free grammar that accepts all words in the language and possibly other words that are longer than any word in the language. In this paper, we describe an efficient algorithm aided by Ant Colony System that, for a given finite language, synthesizes (constructs) a small cover-grammar of the language. We also check its ability to solve a grammatical inference task through the series of experiments.

References

[1] Bondy, J.A., Murty, U.S.R.: Graph Theory. Graduate Texts in Mathematics 244, Springer, 2008.10.1007/978-1-84628-970-5
Search in Google Scholar Back to article
[2] Bunke, H., Sanfelieu, A. (eds): Syntactic and Structural Pattern Recognition Theory and Applications. World Scientific, Singapore, 1990.10.1142/0580
Search in Google Scholar Back to article
[3] Câmpeanu, C., Sântean, N., Yu, S.: Minimal cover-automata for finite languages. Theor. Comput. Sci. 267, 3-16, 2001.10.1016/S0304-3975(00)00292-9
Search in Google Scholar Back to article
[4] Charikar, M., Lehman, E., Liu, D., Panigrahy, R., Prabhakaran, M., Sahai, A., Shelat, A.: The smallest grammar problem. IEEE Trans. Inf. Theory 51, 2554-2576, 2005.10.1109/TIT.2005.850116
Search in Google Scholar Back to article
[5] Chirathamjaree, C., Ackroyd, M.: A method for the inference of non-recursive context-free grammars. Int. J. Man-Machine Studies 12, 379-387, 1980.10.1016/S0020-7373(80)80022-8
Search in Google Scholar Back to article
[6] Colorni, A., Dorigo, M., Maniezzo, V.: Distributed Optimization by Ant Colonies. In Varela, F. and Bourgine, P., editors, Proceedings of ECAL91 - First European Conference on Artificial Life, Elsevier Publishing, 134-142, 1992.
Search in Google Scholar Back to article
[7] Cormen, T. H., Leiserson, C. E., Rivest, R. L., Stein C.: Introduction to Algorithms. MIT Press, second edition, 2001.
Search in Google Scholar Back to article
[8] Dréo, J., Pétrowski, A., Siarry, P., Taillard, E.: Meta-heuristics for Hard Optimization. Springer, 2006.
Search in Google Scholar Back to article
[9] Du, D.-Z., Ko, K.-I: Problem Solving in Automata, Languages, and Complexity. Wiley, 2001.10.1002/0471224642
Search in Google Scholar Back to article
[10] Eyraud, R., de la Higuera, C., Janodet, J.: LARS: A learning algorithm for rewriting systems. Mach. Learn. 66, 7-31, 2007.10.1007/s10994-006-9593-8
Search in Google Scholar Back to article
[11] Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979.
Search in Google Scholar Back to article
[12] de la Higuera, C.: Characteristic sets for polynomial grammatical inference. Mach. Learn. 27, 125-138, 1997.10.1023/A:1007353007695
Search in Google Scholar Back to article
[13] de la Higuera, C.: A bibliographical study of grammatical inference. Pattern Recognit. 38, 1332-1348, 2005.10.1016/j.patcog.2005.01.003
Search in Google Scholar Back to article
[14] de la Higuera, C.: Grammatical Inference: Learning Automata and Grammars. Cambridge University Press, 2010.10.1017/CBO9781139194655
Search in Google Scholar Back to article
[15] Hopcroft, J.E., Motwani, R., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation, 2nd ed. Addison-Wesley, 2001.10.1145/568438.568455
Search in Google Scholar Back to article
[16] Kieffer, J.C., Yang, E.: Grammar Based Codes: A New Class of Universal Lossless Source Codes. IEEE Trans. Inf. Theory 46, 737-754, 2000.10.1109/18.841160
Search in Google Scholar Back to article
[17] Körner, H.: On minimizing cover automata for finite languages in O(n log n) time. LNCS 2608, Springer, 359-400, 2003.10.1007/3-540-44977-9_11
Search in Google Scholar Back to article
[18] Lothaire, M.: Algebraic Combinatorics on Words. Encyclopedia of Mathematics and Its Applications 90, Cambridge, 2002.10.1017/CBO9781107326019
Search in Google Scholar Back to article
[19] Mateescu, A., Salomaa, A., Yu, S.: On the decomposition of finite languages. Technical Report 222, Turku Centre for Computer Science, December 1998.
Search in Google Scholar Back to article
[20] Moon, J.W., Moser, L.: On cliques in graphs. Isr. J. Math. 3, 23-28, 1965.10.1007/BF02760024
Search in Google Scholar Back to article
[21] Nakamura, K., Ishiwata, T.: Synthesizing context free grammars from sample strings based on inductive CYK algorithm. LNAI 1891, Springer, 186-195, 2000.10.1007/978-3-540-45257-7_15
Search in Google Scholar Back to article
[22] Nakamura, K., Matsumoto, M.: Incremental learning of context free grammars based on bottom-up parsing and search. Pattern Recognit. 38, 1384-1392, 2005.10.1016/j.patcog.2005.01.004
Search in Google Scholar Back to article
[23] Papadimitriou, C. H., Steiglitz K.: Combinatorial Optimization: Algorithms and Complexity. Dover Publications, July 1998.
Search in Google Scholar Back to article
[24] Rabhi, F., Lapalme, G.: Algorithms: A Functional Programming Approach. Addison-Wesley, 1999.
Search in Google Scholar Back to article
[25] Salomaa, A., Yu, S.: On the decomposition of finite languages. In Rozenberg, G., and Thomas, W., editors, Developments in Language Theory, World Scientific, 22-31, 2000.10.1142/9789812792464_0003
Search in Google Scholar Back to article
[26] Wieczorek, W.: An algorithm for the decomposition of finite languages. Logic Journal of the IGPL 18, 355-366, 2010.10.1093/jigpal/jzp032
Search in Google Scholar Back to article
[27] Wood, D.: A generalised normal form theorem for context-free grammars. Comput. J. 13, 272-277, 1970.10.1093/comjnl/13.3.272
Search in Google Scholar Back to article

Inductive Synthesis of Cover-Grammars with the Help of Ant Colony Optimization

Abstract

Paradigm

My account