Decision Problems and Applications of Rational Sets of Regular Languages

• Autorzy: Afonin S.

Identyfikatory

DOI

10.3233/FI-2018-1716

• Konferencja: RuFiDiM Conference, Russian-Finnish Symposium in Discrete Mathematics (5; 16-19.05. 2017; Turku; Finland)
• Języki publikacji: EN

Abstrakty

EN

In this paper we summarize known results on decision problems for finitely generated semigroups and rational sets of regular languages and prove various statements on the topic. In particular, we prove undecidability of the equivalence problem for rational set of finite languages, automaticity of finitely generated semigroups of factorial languages, and provide an algorithm for automatic presentation construction in case of regular factorial languages. We also discuss possible direction for future research and describe applications of rational sets of regular languages to computer science problems.

Słowa kluczowe

EN

rational set of regular languages; semigroup of regular languages; membership problem; automatic structure; factorial languages

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2018
• Tom: Vol. 162, nr 2/3
• Strony: 101--118
• Opis fizyczny: Bibliogr. 21 poz.

Twórcy

autor

Afonin S.

• Institute of Mechanics, M.V. Lomonosov Moscow State University, Michurinskij av., 1, Moscow, Russian Federation

Bibliografia

• [1] Campbell CM, Robertson EF, Ruškuc N, Thomas RM. Automatic semigroups. Theoretical Computer Science, 2001. 250(1-2):365-391. URL https://doi.org/10.1016/S0304-3975(99)00151-6.
• [2] Calvanese D, De Giacomo G, Lenzerini M, Vardi M. Rewriting of Regular Expressions and Regular Path Queries. Journal of Computer and System Sciences, 2002. 64:443-465. URL https://doi.org/10.1006/jcss.2001.1805.
• [3] Hashiguchi K. Representation theorems on regular languages. Journal of computer and system sciences, 1983. 27:101-115. URL https://doi.org/10.1016/0022-0000(83)90031-4.
• [4] Karhumäki J, Lisovik LP. The Equivalence Problem of Finite Substitutions on ab*c, with Applications. In: ICALP ’02: Proceedings of the 29th International Colloquium on Automata, Languages and Programming. Springer-Verlag, London, UK. ISBN 3-540-43864-5, 2002 pp. 812-820.
• [5] Karhumäki J, Saarela A. The Unique Decipherability in the Monoid of Regular Languages is Undecidable. Fundamenta Informaticae, 2011. 110(1-4):197-200. doi:10.3233/FI-2011-537.
• [6] Afonin S. The View Selection Problem for Regular Path Queries. In: Laber ES, Bornstein C (eds.), Proceedings of the LATIN 2008, volume 4957 of Lecture Notes in Computer Science. Springer, 2008 pp. 121-132. doi:10.1007/978-3-540-78773-0_11.
• [7] Holzer A, Schallhart C, Tautschnig M, Veith H. Closure properties and complexity of rational sets of regular languages. Theoretical Computer Science, 2015. 605:62-79. doi:http://dx.doi.org/10.1016/j.tcs.2015.08.035.
• [8] Howie J. Fundamentals of semigroup theory. London Mathematical Society monographs. Clarendon, 1995. ISBN 9780198511946.
• [9] Sakarovitch J. Easy Multiplications I: The Realm of Kleene’s Theorem. Inf. Comput., 1987. 74(3):173-197. URL https://doi.org/10.1016/0890-5401(87)90020-4.
• [10] Hoffmann M, Kuske D, Otto F, Thomas RM. Some relatives of automatic and hyperbolic groups. In: Semigroups, Algorithms, Automata and Languages. World Scientific Pub Co Pte Lt, 2002 doi:10.1142/9789812776884_0016.
• [11] Afonin S, Khazova E. Membership and Finiteness Problems for Rational Sets of Regular Languages. International Journal of Foundations of Computer Science, 2006. 17(3):493-506. URL https://doi.org/10.1142/S0129054106003954.
• [12] Brzozowski J, Culik K, Gabrielian A. Classification of noncounting events. Journal of computer and system sciences, 1971. 5:41-53. URL https://doi.org/10.1016/S0022-0000(71)80006-5.
• [13] Afonin S, Khazova E. On the Structure of Finitely Generated Semigroups of Unary Regular Languages. Int. J. Found. Comput. Sci., 2010. 21(5):689-704. URL https://doi.org/10.1142/S0129054110007507.
• [14] Hoffmann M, Thomas RM. Automaticity and commutative semigroups. Glasgow Mathematical Journal, 2002. 44:167-176. URL https://doi.org/10.1017/S0017089502010121Pu.
• [15] Avgustinovich SV, Frid AE. Canonical Decomposition of a Regular Factorial Language. In: Computer Science Symposium in Russia, CSR 2006, volume 3967 of Lecture Notes in Computer Science. Springer, 2006 pp. 18-22. doi:10.1007/11753728_5.
• [16] Frid AE. Simple equations on binary factorial languages. Theor. Comput. Sci., 2009. 410(30-32):2947-2956. URL https://doi.org/10.1016/j.tcs.2009.03.001.
• [17] Avgustinovich SV, Frid AE. A Unique Decomposition Theorem for Factorial Languages. IJAC, 2005. 15(1):149-160. URL https://doi.org/10.1142/S0218196705002116.
• [18] Halevy AY. Theory of answering queries using views. SIGMOD Record (ACM Special Interest Group on Management of Data), 2000. 29(4):40-47. doi:10.1145/369275.369284.
• [19] Grahne G, Thomo A. Query containment and rewriting using views for regular path queries under constraints. In: PODS ’03: Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems. ACM Press, New York, NY, USA. ISBN 1-58113-670-6, 2003 pp. 111-122. doi:http://doi.acm.org/10.1145/773153.773165.
• [20] Calvanese D, Giacomo GD, Lenzerini M, Vardi MY. Answering Regular Path Queries Using Views. In: ICDE. 2000 pp. 389-398. doi: 10.1109/ICDE.2000.839439.
• [21] Segoufin L, Vianu V. Views and queries: determinacy and rewriting. In: PODS ’05: Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems. ACM Press, New York, NY, USA. ISBN 1-59593-062-0, 2005 pp. 49-60. doi:http://doi.acm.org/10.1145/1065167.1065174.