Star-Connected Flat Languages and Automata

• Autorzy: Klunder, B.
• Języki publikacji: EN

Abstrakty

EN

Star-connected rational expressions were considered only as expressions defining trace languages. In this paper we continue the study of the class of flat languages defined by this kind of rational expressions. We strengthen results of [4] and prove that any star-connected language has an automaton with cycles which are composition of connected cycles. This condition is sufficient for star-connected languages provided that the dependency relation is transitive. As a consequence we obtain for every alphabet stronger pumping lemma for star-connected languages. Finally, the product of two automata inherits this property from the components and thus for alphabet with transitive dependency relation the set of all star-connected languages is closed under intersections.

Słowa kluczowe

EN

trace language; star-connected rational expressions; finite automata

• Czasopismo: Fundamenta Informaticae
• Rocznik: 2006
• Tom: Vol. 72, nr 1-3
• Strony: 235-243
• Opis fizyczny: bibliogr. 7 poz.

Twórcy

autor

Klunder, B.

• Faculty of Mathematics and Computer Science, Nicolaus Copernicus University, Chopina 12/18, 87-100 Toruń, Poland,

Bibliografia

• [1] M. Clerbout, M. Latteux: Semi-commutations. Information & Computation 73, pp. 59-74, 1987.
• [2] V. Diekert, G. Rozenberg (eds.): The Book of Traces. World Scientific, 1995.
• [3] J.E. Hopcroft, R. Motwani, J.D. Ullman: Introduction to Automata Theory, Languages and Computation. Addison-Wesley, 2001.
• [4] B. Klunder, E. Ochmański, K. Stawikowska: On Star-Connected Flat Languages. Fundamenta Informaticae 67 (1-3), pp. 93-105, 2005.
• [5] A. Mazurkiewicz: Concurrent Program Schemes and Their Interpretations. Report DAIMI-PB-78, Aarhus University, 1977.
• [6] E. Ochmański: Regular Behaviour of Concurrent Systems. Bulletin of EATCS 27, pp. 56-67, 1985.
• [7] E. Ochmański: Recognizable Trace Languages. In [2], pp.167-204.World Scientific, 1995.