On Rough Approximations of Languages under Infinite Index Indiscernibility Relations

• Autorzy: Martín Torres Gabriela

Identyfikatory

DOI

10.3233/FI-2021-2024

• Języki publikacji: EN

Abstrakty

EN

In the paper [13] Păun, Polkowski and Skowron introduce several indiscernibility relations among strings that are infinite index equivalence or tolerance relations, and study lower and upper rough approximations of languages defined by them. In this paper we develop a further study of some of these indiscernibility relations among strings. We characterize the classes defined by them, and the rough approximations of general and context free languages under them. We also compare some of the rough approximations these relations produce to the ones given by the congruences defining testable, reverse testable, locally testable, piecewise testable and commutative languages. Those yield languages belonging to that families. Next, we modify some of the relations to obtain congruences, and study the families of languages the rough approximations under them give rise to. One of these modificated relations turns out to be the k-abelian congruence, that was defined by J. Karhumäki in [7], in the context of combinatorics on words. We show that it defines a pseudo-principal +-variety, a term defined in [9]. Our results in that work are then applied to determine when a given language has a best upper approximation in that family. Finally, we make some comments on the accuracy of the rough approximations obtained in each case.

Słowa kluczowe

EN

congruence lattices; language; combinatorics

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2021
• Tom: Vol. 179, nr 3
• Strony: 275--293
• Opis fizyczny: Bibliogr. 22 poz.

Twórcy

autor

Martín Torres Gabriela

• Research Group on Mathematical Linguistics, Rovira i Virgili University, Spain

Bibliografia

• [1] Almeida J. Finite Semigroups and Universal Algebra, World Scientific, Singapore, 1995. ISBN-13:978-9810218959, 10:9810218958.
• [2] Berstel J. Sur la densité asymptotique de langages formels, Automata, Languages, and Programming, M. Nivat (ed.), North Holland, 1973, pp. 345-358. ID:29271284.
• [3] Brzozowski JA. Canonical regular expressions and minimal state graphs of definite events, in: Proc. Symp. Math. Theory of Automata, Microwave Research Inst. Symp. Ser. 12, 1963 pp. 529-561, Brooklyn, New York. ID:118363215.
• [4] Chomsky N, and Schützenberger MP. The algebraic theory of context-free languages. Computer Programming and Formal Languages, P. Braffort and D. Hirschberg (eds.), North Holland, 1963. 35:118-161. doi:10.1016/S0049-237X(08)72023-8.
• [5] Eilenberg S. Automata, Languages, and Machines, Vol. B, Academic Press, New York, 1976. ISBN:9780080873749.
• [6] McNaughton R, and Papert SA. Counter-free automata, MIT Press, Cambridge, Massachusetts 1971. ISBN:978-0-262-13076-9.
• [7] Karhumäki J. Generalized Parikh Mappings and Homomorphisms, Information and Control, 1980. 47(3):155-165. doi:10.1016/S0019-9958(80)90493-3.
• [8] Maňuch J. Characterization of a word by its subwords, Developments in Language Theory, G. Rozenberg and W.Thomas (eds.), World Scientific, 2000 pp. 210-219. doi:10.1142/9789812792464_0018.
• [9] Martín Torres G, and Steinby M. Rough Approximations in varieties of regular languages, Fundamenta Informaticae 2011. 112(4):281-303. doi:10.3233/FI-2011-591.
• [10] Martín Torres G. On the Accuracy of Rough Approximations of Regular Languages, Fundamenta Informaticae 2014. 132(4):1-13. doi:10.3233/FI-2014-1058.
• [11] Orłowska E (ed.), Incomplete Information: Rough Set Analysis, Studies in Fuzziness and Soft Computing, Physica-Verlag, Heidelberg 1998. doi:10.1007/978-3-7908-1888-8_1.
• [12] Păun Gh, Polkowski L, and Skowron A. Rough-set-like approximations of context-free and regular languages, Information Processing and Management of Uncertainity on Knowledge Based Systems, Vol.II (Proc. IPMU-96, July 1-5, 1996, Granada, Spain), Universidad de Granada. 1996 pp. 891-895. ID:16004176.
• [13] Păun Gh, Polkowski L, and Skowron A. Rough set approximations of languages, Fundamenta Informaticae 1997. 32:149-162.
• [14] Pawlak Z. Rough sets. Theoretical aspects of reasoning about data, Kluwer Academic Publishers, Dordrecht 1991. ISBN-13:978-0792314721, 10:0792314727.
• [15] Perles M, Rabin MO, and Shamir E. The theory of definite automata, IEEE Trans. Electronic Computers 1963. EC-12:233-243. doi:10.1109/PGEC.1963.263534.
• [16] Pin J-E. Varieties of formal languages, North Oxford Academic Publ., London 1986. ISBN-10:0946536120, 13:978-0946536122.
• [17] Pin J-E. Syntactic semigroups, Handbook of Formal Languages, Vol.1 (G. Rozenberg and A. Salomaa, eds.), Springer, Berlin. 1997 pp. 679-746. doi:10.1007/978-3-642-59136-5_10.
• [18] Polkowski L. Rough sets. Mathematical Foundations, Advances in Soft Computing, Physica-Verlag, Heidelberg 2002.
• [19] Simon I. Piecewise testable events, Proceedings of the 2nd GI Conference on Automata Theory and Formal Languages, Lecture Notes in Computer Sciences. 1975. 33:214-222. doi:10.1007/3-540-07407-4_23.
• [20] Thérien D. Classification of regular congruences, Ph.D. Thesis, Research Report CS-80-19, Department of Computer Science, University of Waterloo, Waterloo, Ontario, 1980. ID:123832199.
• [21] Thérien D. Classification of finite monoids: the language approach, Theoretical Computer Science 1981. 14(2):195-208. doi:10.1016/0304-3975(81)90057-8.
• [22] Yu S. Regular languages, in: Handbook of Formal Languages, Vol. 1 (G. Rozenberg and A. Salomaa, eds.), Springer-Verlag, Berlin. 1997 pp. 41-110. doi:10.1007/978-3-642-59136-5_2.

Uwagi

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