On the Accuracy of Rough Approximations of Regular Languages

• Autorzy: Torres G. M.

Identyfikatory

DOI

10.3233/FI-2014-1058

• Języki publikacji: EN

Abstrakty

EN

In this paper we attempt to measure the accuracy of approximations of regular languages by languages in +−varieties (as defined by Eilenberg). These approximations are upper approximations in the sense of Pawlak’s rough set theory with respect to congruences belonging to the variety of congruences corresponding to the given +−variety. In our approach, the accuracy of an approximation is measured by the relative density of the object language in the approximation language and the asymptotic behavior of this quotient. In particular, we apply our measures of accuracy to k-definite, reverse k-definite, i, j-definite and k-testable approximations.

Słowa kluczowe

EN

rough sets; approximation theory; programming languages; congruences; measure theory

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2014
• Tom: Vol. 132, nr 4
• Strony: 533--545
• Opis fizyczny: Bibliogr. 26 poz.

Twórcy

autor

Torres G. M.

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

Bibliografia

• [1] J. Almeida. Finite Semigroups and Universal Algebra. World Scientific, Singapore, 1995.
• [2] D. Angluin and C. H. Smith, Inductive inference: theory and methods, ACM Computing Surveys 15, No. 3(1983), 237 –270.
• [3] J. Berstel. Sur la densité asymptotique de langages formels. Automata, Languages, and Programming, M. Nivat (ed.), North Holland, 1973, 345–358.
• [4] P. E. Black (ed.) Dictionary of Algorithms and Data Structures [online], U.S. National Institute of Standards and Technology, 2005.
• [5] J. A. Brzozowski. Canonical regular expressions and minimal state graphs of definite events. Proc. Symp.Math. Theory of Automata, Microwave Research Inst. Symp. Ser. 12, Brooklyn, New York, 1963, 529–561.
• [6] A. Ginzburg. About some properties of definite, reverse-definite and related automata. IEEE Trans. Electronic Computers EC-15, 1966, 809–810.
• [7] R.C. Gonzalez and M. G. Thomason, Syntactic Pattern Recognition: An Introduction, Addison-Wesley, Reading,MA, 1978.
• [8] D. Knuth. Big Omicron and big Omega and big Theta. ACM SIGACT News, 1976, Volume 8, Issue 2.
• [9] A. Kornai. Quantitative comparison of languages. Grammars 1, number 2, 1988, 155–165.
• [10] J. Kozik. Conditional densities of regular languages. Electronic Notes in Theoretical Computer Science, 2005, Volume 140, 67-79.
• [11] G. Martın and M. Steinby. Rough Approximations in varieties of regular languages. Fundamenta Informaticae,FI 112(4), 2011, 281-303.
• [12] R. McNaughton and S. Papert. Counter-free Automata. MIT Press, Cambridge, Massachusetts, 1971.
• [13] L. Miclet, Structural Methods in Pattern Recognition, Springer-Verlag, New York, 1986.
• [14] E. Orłowska (ed.). Incomplete Information: Rough Set Analysis. Studies in Fuzziness and Soft Computing, Physica-Verlag, Heidelberg, 1998.
• [15] Gh. Păun, L. Polkowski and A. Skowron. 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, Granada, Spain, 1996, 891–895.
• [16] Gh. Păun, L. Polkowski and A. Skowron. Rough set of approximations of languages. Fundamenta Informaticae32, 1997, 149–162.
• [17] Z. Pawlak. Rough sets, Theoretical Aspects of Reasoning About Data. Kluwer Academic Publishers, Dordrecht,1991.
• [18] M. Perles, M. O. Rabin and E. Shamir. The theory of definite automata. IEEE Trans. Electronic ComputersEC-12, 1963, 233–243.
• [19] L. Polkowski. Rough sets, Mathematical Foundations. Advances in Soft Computing, Physica-Verlag, Heidelberg,2002.
• [20] M. Solomon. On the length of words. Jewels are Forever. Contributions on Theoretical Computer Science in Honour of Arto Salomaa. Juhani Karhumäki, Hermann Maurer, Gheorghe Paun (eds.), Springer, London,1999, 194–203.
• [21] S. Yu. Regular languages. Handbook of Formal Languages, Vol.1. G. Rozenberg and A. Salomaa (eds.),Springer, Berlin, 1997, 80–110.
• [22] Shur, A. M. Combinatorial Complexity of Rational Languages. Discr. Anal. and Oper. Research, 2005, Ser.1, 12:2, 7899.
• [23] M. Spivak. Calculus. University Press, Cambridge, UK, 2006.
• [24] M. Steinby. A theory of tree language varieties. Tree Automata and Languages. M. Nivat and A. Podelski,(eds.), North-Holland, Amsterdam, 1992, 57–81.
• [25] A. Szilard, S. Yu, K. Zhang and J. Shallit. Characterizing Regular Languages with Polynomial Densities. Lecture Notes in Computer Science, Mathematical Foundations of Computer Science, Springer-Verlag, London, UK, 1992, Volume 629, 494-503.
• [26] S. Yu. Regular languages. Handbook of Formal Languages, Vol. 1. G. Rozenberg and A. Salomaa (eds.),Springer-Verlag, Berlin, 1997, 41–110.