On Star-Connected Flat Languages

Issue title: Concurrency Specification and Programming (CS&P 2004)

Article type: Research Article

Authors: Klunder, Barbara | Ochmański, Edward | Stawikowska, Krystyna

Affiliations: Faculty of Mathematics and Computer Science, Nicolaus Copernicus University, Toruń, Poland. E-mail: klunder,edoch,[email protected]

Abstract: 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.

Keywords: trace language, star-connected rational expressions, finite automata

Journal: Fundamenta Informaticae, vol. 67, no. 1-3, pp. 93-105, 2005