State Complexity of Multiple Catenations

• Autorzy: Caron P. , Luque J.-G. , Patrou B.

Identyfikatory

DOI

10.3233/FI-2018-1683

• Języki publikacji: EN

Abstrakty

EN

We improve some results relative to the state complexity of the multiple catenations described by Gao and Yu. In particular we nearly divide by 2 the size of the alphabet needed for witnesses. We also give some refinements to the algebraic expression of the state complexity, which is especially complex with this operation. We obtain these results by using peculiar DFAs defined by Brzozowski.

Słowa kluczowe

EN

deterministic finite automata; computational complexity; combinatorial analysis; generalization; bounds; formal languages

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2018
• Tom: Vol. 160, nr 3
• Strony: 255--279
• Opis fizyczny: Bibliogr. 14 poz., rys.

Twórcy

autor

Caron P.

• LITIS, Université de Rouen, Avenue de l’Université, 76801 Saint-Étienne du Rouvray Cedex, France

autor

Luque J.-G.

• LITIS, Université de Rouen, Avenue de l’Université, 76801 Saint-Étienne du Rouvray Cedex, France

autor

Patrou B.

• LITIS, Université de Rouen, Avenue de l’Université, 76801 Saint-Étienne du Rouvray Cedex, France

Bibliografia

• [1] Yu S, Zhuang Q, Salomaa K. The State Complexities of Some Basic Operations on Regular Languages. Theoret. Comput. Sci., 1994. 125(2):315-328. URL https://doi.org/10.1016/0304-3975(92)00011-F.
• [2] Gao Y, Salomaa K, Yu S. The State Complexity of Two Combined Operations: Star of Catenation and Star of Reversal. Fundam. Inform., 2008. 83(1-2):75-89.
• [3] Cui B, Gao Y, Kari L, Yu S. State Complexity of Two Combined Operations: Catenation-Union and Catenation-Intersection. Int. J. Found. Comput. Sci., 2011. 22(8):1797-1812. doi:10.1142/S0129054111009045.
• [4] Jirásková G, Okhotin A. On the State Complexity of Star of Union and Star of Intersection. Fundam. Inform., 2011. 109(2):161-178. doi:10.3233/FI-2011-502.
• [5] Caron P, Luque J, Mignot L, Patrou B. State Complexity of Catenation Combined with a Boolean Operation: A Unified Approach. Int. J. Found. Comput. Sci., 2016. 27(6):675-704. doi:10.1142/S0129054116500234. URL http://dx.doi.org/10.1142/S0129054116500234.
• [6] Gao Y, Moreira N, Reis R, Yu S. A Survey on Operational State Complexity. CoRR, 2015. abs/1509.03254. URL http://arxiv.org/abs/1509.03254.
• [7] Maslov AN. Estimates of the number of states of finite automata. Soviet Math. Dokl., 1970. 11:1373-1375.
• [8] Jirásková G. State complexity of some operations on binary regular languages. Theor. Comput. Sci., 2005. 330(2):287-298. URL https://doi.org/10.1016/j.tcs.2004.04.011.
• [9] Gao Y, Yu S. State Complexity Approximation. In: Dassow J, Pighizzini G, Truthe B (eds.), Proceedings Eleventh International Workshop on Descriptional Complexity of Formal Systems, DCFS 2009, Magdeburg, Germany, July 6-9, 2009., volume 3 of EPTCS. 2009 pp. 121-130. doi:10.4204/EPTCS.3.11. URL http://dx.doi.org/10.4204/EPTCS.3.11.
• [10] Domaratzki M, Okhotin A. State complexity of power. Theoretical Computer Science, 2009. 410(24):2377-2392. doi:http://dx.doi.org/10.1016/j.tcs.2009.02.025. Formal Languages and Applications: A Collection of Papers in Honor of Sheng Yu, URL http://www.sciencedirect.com/science/article/pii/S0304397509001820.
• [11] Brzozowski JA. In Search of Most Complex Regular Languages. Int. J. Found. Comput. Sci., 2013. 24(6):691-708. URL https://doi.org/10.1142/S0129054113400133.
• [12] Hopcroft JE, Ullman JD. Introduction to Automata Theory, Languages and Computation. Addison-Wesley, Reading, MA, 1979. ISBN-020102988X, 9780201029888.
• [13] Jirásek J, Jirásková G, Szabari A. State complexity of concatenation and complementation. Int. J. Found. Comput. Sci., 2005. 16(3):511-529. URL https://doi.org/10.1142/S0129054105003133.
• [14] Ganyushkin O, Mazorchuk V. Classical finite transformation semigroups: an introduction. Algebra and Applications. Springer, Dordrecht, 2008. ISBN-1848002815, 9781848002814.

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2018).