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

• Autorzy: Wieczorek W.

Identyfikatory

DOI

10.1515/fcds-2016-0016

• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

context-free cover-grammar (CFCG); grammatical inference; Ant Colony Optimization (ACO); clique

• Wydawca: Wydawnictwo Politechniki Poznańskiej
• Czasopismo: Foundations of Computing and Decision Sciences
• Rocznik: 2016
• Tom: Vol. 41, No. 4
• Strony: 297--315
• Opis fizyczny: Bibliogr. 27 poz., fig., tab

Twórcy

autor

Wieczorek W.

• Faculty of Computer Science and Materials Science, University of Silesia, Poland

Bibliografia

• [1] Bondy J.A., Murty U.S.R.: Graph Theory. Graduate Texts in Mathematics 244, Springer, 2008.
• [2] Bunke H., Sanfelieu A. (eds): Syntactic and Structural Pattern Recognition Theory and Applications. World Scientific, Singapore, 1990.
• [3] Câmpeanu C., Sântean N., Yu S.: Minimal cover-automata for finite languages. Theor. Comput. Sci. 267, 3-16, 2001.
• [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.
• [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.
• [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.
• [7] Cormen T.H., Leiserson C.E., Rivest R.L., Stein C.: Introduction to Algorithms. MIT Press, second edition, 2001.
• [8] Dré J., Pétrowski A., Siarry P., Taillard E.: Meta-heuristics for Hard Optimization. Springer, 2006.
• [9] Du D.-Z., Ko K.-I: Problem Solving in Automata, Languages, and Complexity. Wiley, 2001.
• [10] Eyraud R., de la Higuera C., Janodet J.: LARS: A learning algorithm for rewriting systems. Mach. Learn. 66, 7-31, 2007.
• [11] Garey M.R., Johnson D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979.
• [12] de la Higuera C.: Characteristic sets for polynomial grammatical inference. Mach. Learn. 27, 125-138, 1997.
• [13] de la Higuera C.: A bibliographical study of grammatical inference. Pattern Recognit. 38, 1332-1348, 2005.
• [14] de la Higuera C.: Grammatical Inference: Learning Automata and Grammars. Cambridge University Press, 2010.
• [15] Hopcroft J.E., Motwani R., Ullman J.D.: Introduction to Automata Theory, Languages, and Computation, 2nd ed. Addison-Wesley, 2001.
• [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.
• [17] Körner H.: On minimizing cover automata for finite languages in O(n log n) time. LNCS 2608, Springer, 359-400, 2003.
• [18] Lothaire M.: Algebraic Combinatorics on Words. Encyclopedia of Mathematics and Its Applications 90, Cambridge, 2002.
• [19] Mateescu A., Salomaa A., Yu S.: On the decomposition of finite languages. Technical Report 222, Turku Centre for Computer Science, December 1998.
• [20] Moon J.W., Moser L.: On cliques in graphs. Isr. J. Math. 3, 23-28, 1965.
• [21] Nakamura K., Ishiwata T.: Synthesizing context free grammars from sample strings based on inductive CYK algorithm. LNAI 1891, Springer, 186-195, 2000.
• [22] Nakamura K., Matsumoto M.: Incremental learning of context free grammars based on bottom-up parsing and search. Pattern Recognit. 38, 1384-1392, 2005.
• [23] Papadimitriou C.H., Steiglitz K.: Combinatorial Optimization: Algorithms and Complexity. Dover Publications, July 1998.
• [24] Rabhi F., Lapalme G.: Algorithms: A Functional Programming Approach. Addison-Wesley, 1999.
• [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.
• [26] Wieczorek W.: An algorithm for the decomposition of finite languages. Logic Journal of the IGPL 18, 355-366, 2010.
• [27] Wood D.: A generalized normal form theorem for context-free grammars. Comput. J. 13, 272-277, 1970.

Uwagi

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę.