On Star-Connected Flat Languages

• Autorzy: Klunder B. , Ochmański E. , Stawikowska K.
• Języki publikacji: EN

Abstrakty

EN

Up to now, star-connected rational expressions were considered only as expressions defining trace languages. In this paper we study the class of flat languages defined by this kind of rational expressions. We consider regular languages inducing recognizable trace languages and its subclasses: languages of finite ranks and star-connected languages. Main results are the following: rank of any star-connected language is finite; any star-connected language has an automaton with connected simple cycles; two pumping lemmas for star-connected languages. Moreover, we show that none of the investigated classes is closed under complement and that the class of languages of finite ranks is not closed under intersection. Finally, we briefly mention some decision problems and formulate several open questions.

Słowa kluczowe

EN

trace language; star-connected rational expressions; finite automata

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2005
• Tom: Vol. 67, nr 1-3
• Strony: 93--105
• Opis fizyczny: Bibliogr. 9 poz.

Twórcy

autor

Klunder B.

• Faculty of Mathematics and Computer Science, Nicolaus Copernicus University Toruń, Poland

autor

Ochmański E.

• Faculty of Mathematics and Computer Science, Nicolaus Copernicus University Toruń, Poland

autor

Stawikowska K.

• Faculty of Mathematics and Computer Science, Nicolaus Copernicus University Toruń, Poland

Bibliografia

• [1] J. Berstel: Transductions and Context Free Languages. B.G.Teubner, Stuttgart, 1979.
• [2] M. Clerbout, M. Latteux: Semi-commutations. Information & Computation 73, pp. 59-74, 1987.
• [3] V. Diekert, G. Rozenberg (eds.): The Book of Traces. World Scientific, 1995.
• [4] K. Hashiguchi: Recognizable Closures and Submonoids of Free Partially Commutative Monoids. Theoretical Computer Science 86, pp. 233-241, 1991.
• [5] J.E. Hopcroft, R. Motwani, J.D. Ullman: Introduction to Automata Theory, Languages and Computation. Addison-Wesley, 2001.
• [6] A. Mazurkiewicz: Concurrent Program Schemes and Their Interpretations. Report DAIMI-PB-78, Aarhus University, 1977.
• [7] E. Ochmański: Regular Behaviour of Concurrent Systems. Bulletin of EATCS 27, pp. 56-67, 1985.
• [8] E. Ochmański: Recognizable Trace Languages. In [3], pp.167-204.World Scientific, 1995.
• [9] E. Ochmański, P.A. Wacrenier: On Regular Compatibility of Semi-Commutations. Proc. of ICALP 1993, LNCS 700, pp. 445-456. Springer, 1993.