Rough Approximations in Varieties of Regular Languages

• Autorzy: Martin G. , Steinby M.
• Języki publikacji: EN

Abstrakty

EN

We study approximations of regular languages bymembers of a given variety L of regular languages. These are upper or lower approximations in the sense of Pawlak’s rough set theory with respect to congruences belonging to the variety of congruences corresponding to L. In particular, we consider the closest upper and lower approximations in L. In so-called principal varieties these always exist, and we present algorithms for finding them, but for other varieties the situation is more complex. Although we consider just Eilenberg’s +-varieties, the general ideas apply also to other types of varieties of languages. Our work may also be viewed as an approach to the characterizable inference problem in which a language of a certain kind is to be inferred from a given sample.

Słowa kluczowe

EN

regular language; rough approximation; varieties of languages; finite automata

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2011
• Tom: Vol. 112, nr 4
• Strony: 281--303
• Opis fizyczny: Bibliogr. 31 poz., tab.

Twórcy

autor

Martin G.

autor

Steinby M.

• Department of Mathematics, University of Turku, FI-20014 Turku, Finland,

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. A. Brzozowski, Canonical regular expressions and minimal state graphs of definite events, in: Proc. Symp. Math. Theory of Automata,Microwave Research Inst. Symp. Ser. 12 (1963), Brooklyn, New York, 529-561.
• [4] S. Burris and H. P. Sankappanavar, A Course in Universal Algebra, Springer-Verlag, New York, 1981.
• [5] B. Cordy and K. Salomaa, On the existence of regular approximations, Theoret. Comput. Sci 387 (2007) 125-135.
• [6] B. A. Davey and H. A. Priestley, Introduction to Lattices and Order, 2. edition, Cambridge University Press, Cambridge 2002.
• [7] S. Eilenberg, Automata, Languages, and Machines, Vol. A, Academic Press, New York, 1974.
• [8] S. Eilenberg, Automata, Languages, and Machines, Vol. B, Academic Press, New York, 1976.
• [9] S. Ginsburg and E.H. Spanier, Bounded regular sets, Proc. American Mathematical Soc. 17 (1966), 1043-1049.
• [10] A. Ginzburg, About some properties of definite, reverse-definite and related automata. IEEE Trans. Electronic Computers EC-15 (1966), 809-810.
• [11] R.C. Gonzalez and M. G. Thomason, Syntactic Pattern Recognition: An Introduction, Addison-Wesley, Reading, MA, 1978.
• [12] S. C. Kleene, Representation of events in nerve nets and finite automata, in C. E. Shannon and J. McCarthy (eds.) Automata Studies, Princeton University Press, Princeton, NJ, 1956, 3-42.
• [13] D. C. Kozen, Automata and Computability, Springer, New York 1997.
• [14] M. V. Lawson, Finite Automata, Chapman & Hall/CRC, Boca Raton, 2004.
• [15] R. McNaughton and S. Papert, Counter-free automata,MIT Press, Cambridge, Massachusetts 1971.
• [16] L. Miclet, Structural Methods in Pattern Recognition, Springer-Verlag, New York, 1986.
• [17] E. Orłowska (ed.), Incomplete Information: Rough Set Analysis, Studies in Fuzziness and Soft Computing, Physica-Verlag, Heidelberg 1998.
• [18] 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, July 1-5, 1996, Granada, Spain), Universidad de Granada 1996, 891-895.
• [19] Gh. Pǎun, L. Polkowski and A. Skowron, Rough set of approximations of languages, Fundamenta Informaticae 32 (1997), 149-162.
• [20] Z. Pawlak, Rough sets, Internat. J. Comput. Inform. Sci 11 (1982), 341-356.
• [21] Z. Pawlak, Rough sets. Theoretical aspects of reasoning about data, Kluwer Academic Publishers, Dordrecht 1991.
• [22] M. Perles, M. O. Rabin and E. Shamir, The theory of definite automata, IEEE Trans. Electronic Computers EC-12 (1963), 233-243.
• [23] V. Piirainen, Principal varieties of finite congruences, TUCS Technical Report No 874, Turku Centre for Computer Science, Turku 2008.
• [24] J.-E. Pin, Varieties of formal languages, North Oxford Academic Publ., London 1986.
• [25] J.-E. Pin, Syntactic semigroups, Handbook of Formal Languages, Vol.1 (G. Rozenberg and A. Salomaa, eds.), Springer, Berlin 1997, 679-746.
• [26] L. Polkowski, Rough sets. Mathematical Foundations, Advances in Soft Computing, Physica-Verlag, Heidelberg 2002.
• [27] M. Steinby, A theory of tree language varieties, in: Tree Automata and Languages (M. Nivat and A. Podelski, eds.), North-Holland, Amsterdam 1992, 57-81.
• [28] M. Steinby, Algebraic classifications of regular tree languages, in: Structural Theory of Automata, Semigroups, and Universal Algebra (eds. V:B: Kudryavtsev and I:G. Rosenberg), Springer, Dordrecht 2005, 381-432.
• [29] D. Thérien, Classification of regular congruences, Ph.D. Thesis, Research Report CS-80-19, Department of Computer Science, University of Waterloo, Waterloo, Ontario, 1980.
• [30] D. Thérien, Classification of finite monoids: the language approach, Theoretical Computer Science 14 (1981), 195-208.
• [31] S. Yu, Regular languages, in: Handbook of Formal Languages, Vol. 1 (G. Rozenberg and A. Salomaa, eds.), Springer-Verlag, Berlin 1997, 41-110.