Parallel Algorithms for Minimal Nondeterministic Finite Automata Inference

• Autorzy: Jastrzab Tomasz , Czech Zbigniew J. , Wieczorek Wojciech

Identyfikatory

DOI

10.3233/FI-2021-2004

• Języki publikacji: EN

Abstrakty

EN

The goal of this paper is to develop the parallel algorithms that, on input of a learning sample, identify a regular language by means of a nondeterministic finite automaton (NFA). A sample is a pair of finite sets containing positive and negative examples. Given a sample, a minimal NFA that represents the target regular language is sought. We define the task of finding an NFA, which accepts all positive examples and rejects all negative ones, as a constraint satisfaction problem, and then propose the parallel algorithms to solve the problem. The results of comprehensive computational experiments on the variety of inference tasks are reported. The question of minimizing an NFA consistent with a learning sample is computationally hard.

Słowa kluczowe

EN

parallel algorithms; learning regular languages; nondeterministic finite automata; constraint satisfaction; satisfiability problem; grammatical inference

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2021
• Tom: Vol. 178, nr 3
• Strony: 203--227
• Opis fizyczny: Bibliogr. 33 poz., rys., tab.

Twórcy

autor

Jastrzab Tomasz

• Silesian University of Technology, Gliwice, Poland

autor

Czech Zbigniew J.

• Silesian University of Technology, Gliwice, Poland

autor

Wieczorek Wojciech

• University of Bielsko-Biała, Bielsko-Biała, Poland

Bibliografia

• [1] Jastrzab T, Czech ZJ, Wieczorek W. Generating minimal nondeterministic finite automata using a parallel algorithm. In: 19th International Symposium on Parallel and Distributed Computing (ISPDC 2020). IEEE, 2020 pp. 37-43. doi:10.1109/ISPDC51135.2020.00015.
• [2] Hopcroft JE, Motwani R, Ullman JD. Introduction to automata theory, languages, and computation, 3rd Edition. Pearson international, 3rd ed. Addison-Wesley, 2013. ISBN-10:0321455363, 13:978-0321455369.
• [3] de la Higuera C. Grammatical Inference: Learning Automata and Grammars. Cambridge University Press, New York, NY, USA, 2010. doi:10.1017/CBO9781139194655.
• [4] Hopcroft JE. An n log n algorithm for minimizing the states in a finite automaton. In: Kohavi Z (ed.), Theory of Machines and Computations. Academic Press, 1971 pp. 189-196.
• [5] Jiang T, Ravikumar B. Minimal NFA problems are hard. SIAM J. Comput., 1993. 22(6):1117-1141. doi:10.1137/0222067.
• [6] Gold EM. Complexity of automaton identification from given data. Information and Control, 1978. 37:302-320. doi:10.1016/S0019-9958(78)90562-4.
• [7] de la Higuera C. Characteristic sets for polynomial grammatical inference. Machine Learning Journal, 1997. 27:125-138. doi:10.1023/A:1007353007695.
• [8] Gold EM. Language identification in the limit. Information and Control, 1967. 10:447-474.
• [9] Pitt L, Warmuth MK. The minimum consistent DFA Problem Cannot Be Approximated Within Any Polynomial. J. ACM, 1993. 40(1):95-142. doi:10.1145/138027.138042.
• [10] Oncina J, García P. Inferring regular languages in polynomial updated time. In: de la Blanca NP, Sanfeliú A, Vidal E (eds.), Pattern Recognition and Image Analysis, pp. 49-61. World Scientific Pub., 1992. doi:10.1142/9789812797902_0004.
• [11] Lang K, Pearlmutter BA, Price RA. Data dependent vs data independent algorithms. In: Miclet L, de la Higuera C (eds.), Grammatical Inference: Learning Syntax from Sentences, volume 1147 of LNAI, pp. 313-325. Springer-Verlag, 1996.
• [12] Lang K, Pearlmutter BA, Price RA. Results of the Abbadingo one DFA learning competition and a new evidence-driven state merging algorithm. In: International Colloquium on Grammatical Inference ICGI 1998: Grammatical Inference, volume 1433 of LNAI, pp. 1-121. Springer, 1998. ISBN-9783540687078.
• [13] Cicehello O, Kremer SC. Beyond EDSM. In: Adriaans P, Fernau H, van Zaanen M (eds.), ICGI 2002: Grammatical Inference: Algorithms and Applications, volume 2484 of LNAI, pp. 37-48. Springer-Verlag Berlin Heidelberg, 2002. doi:10.1007/3-540-45790-9_4.
• [14] Abela J, Coste F, Spina S. Mutually compatible and incompatible merges for the search of the smallest consistent DFA. In: Paliouras G, Sakakibara Y (eds.), ICGI 2004: Grammatical Inference: Algorithms and Applications, volume 3264 of LNAI, pp. 28-39. Springer-Verlag Berlin Heidelberg, 2004. doi:10.1007/978-3-540-30195-0_4.
• [15] García P, Ruiz J, Cano A, Alvarez G. Inference improvement by enlarging the training set while learning DFAs. In: Sanfeliu A, Cortés ML (eds.), Progress in Pattern Recognition, Image Analysis and Applications, volume 3773 of LNAI. Springer-Verlag Berlin Heidelberg, 2005 pp. 59-70. doi:10.1007/11578079_7.
• [16] Arnold A, Dicky A, Nivat M. A note about minimal non-deterministic automata. Bull. European Association for Theoretical Computer Science (EATCS), 1992. 47:166-169. ID:11128091.
• [17] Gruber H, Holzer M. Inapproximability of nondeterministic state and transition complexity assuming P ≠ NP. In: Harju T, Karhumäki J, Lepistö A (eds.), Developments in Language Theory, volume 4588 of LNCS. Springer-Verlag Berlin Heidelberg, 2007 pp. 205-216. doi:10.1007/978-3-540-73208-2_21.
• [18] Biermann AW, Feldman JA. On the synthesis of finite-state machines from samples of their behavior. IEEE Trans. Computers, 1972. 21(6):592-597. doi:10.1109/TC.1972.5009015.
• [19] Denis F, Lemay A, Tarlutte A. Learning regular languages using RFSAs. Theoretical Computer Science, 2004. 313(2):267-294. doi:10.1016/j.tcs.2003.11.008.
• [20] de Parga MV, García P, Ruiz J. A family of algorithms for non deterministic regular languages inference. In: Ibarra OH, Yen HC (eds.), CIAA-2006, 11th International Conference on Implementation and Application of Automata, 21-23 August 2006, Taipei, Taiwan, volume 4094 of LNCS. Springer-Verlag, Berlin Heidelberg, 2006 pp. 265-274. doi:10.1007/11812128_25.
• [21] García P, de Parga MV, Álvarez GI, Ruiz J. Universal automata and NFA learning. Theoretical Computer Science, 2008. 407:192-202. doi:10.1016/j.tcs.2008.05.017.
• [22] García P, de Parga MV, Álvarez GI, Ruiz J. Learning regular languages using nondeterministic finite automata. In: Ibarra OH, Ravikumar B (eds.), CIAA-2008, Proceedings of the 13th International Conference on Implementation and Application of Automata, volume 5148 of LNCS. Springer-Verlag, Berlin Heidelberg, 2008 pp. 92-101. doi:10.1007/978-3-540-70844-5_10.
• [23] Bollig B, Habermehl P, Kern C, Leucker M. Angluin-style learning of NFA. In: Proceedings of the 21st International Joint Conference on Artifical Intelligence, IJCAI’09. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 2009 p. 1004-1009.
• [24] Jastrzab T, Czech ZJ, Wieczorek W. Parallel induction of nondeterministic finite automata. In: et al RW (ed.), Parallel Processing and Applied Mathematics, 11th International Conference, PPAM 2015, Kraków, Poland, September 6-9, 2015. Revised Selected Papers, Part I, volume 9573 of LNCS. Springer International Publishing, Switzerland, 2016 pp. 248-257. doi:10.1007/978-3-319-32149-3_24.
• [25] Jastrzab T. On parallel induction of nondeterministic finite automata. Procedia Computer Science, 2016. 80:257-268. doi:10.1016/j.procs.2016.05.318.
• [26] Jastrzab T. Two parallelization schemes for the induction of nondeterministic finite automata on PCs. In: Parallel Processing and Applied Mathematics, 12th International Conference, PPAM 2017, Lublin, Poland, September 10-13, 2017, Revised Selected Papers, Part I. 2017 pp. 279-289. doi:10.1007/978-3-319-78024-5_25.
• [27] Tomita M. Dynamic construction of finite automata from examples using hill-climbing. In: Proceedings of the Fourth Annual Conference of Cognitive Science Society. 1982 p. 105-108. ID:53836620.
• [28] Wieczorek W. Induction of Non-Deterministic Finite Automata on Supercomputers. In: Proceedings of the Eleventh International Conference on Grammatical Inference, ICGI 2012, University of Maryland, College Park, USA, September 5-8, 2012. 2012 pp. 237-242. URL http://proceedings.mlr.press/v21/wieczorek12a.html.
• [29] Russell S, Norvig P. Artificial Intelligence: A Modern Approach. Series in Artificial Intelligence. Prentice Hall, Upper Saddle River, NJ, third edition, 2010. ISBN-13:978-0136042594, 10:0136042597.
• [30] Apt KR. Principles of Constraint Programming. Cambridge University Press, New York, NY, USA, 2003. ISBN-9780511615320.
• [31] Niewiadomski A, Switalski P, Sidoruk T, Penczek W. Applying Modern SAT-solvers to Solving Hard Problems. Fundam. Inform., 2019. 165(3-4):321-344. doi:10.3233/FI-2019-1788.
• [32] Sipser M. Introduction to the Theory of Computation. Cengage Learning, Boston, MA, USA, 3rd edition, 2013. ISBN-10:113318779X, 13:978-1133187790.
• [33] Tseytin GS. On the complexity of derivation in propositional calculus. In: Slisenko AO (ed.), Handbook of Formal Languages: Volume 1. Word, Language, Grammar, p. 115-125. Steklov Mathematical Institute, 1970.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2021).