Abstract
We deal with the star problem in trace monoids which means to decide whether the iteration of a recognizable trace language is recognizable. We consider trace monoids K n={a 1 b 1}* × … ×{a n b n }*. Our main theorem asserts that the star problem is decidable in a trace monoid M iff it is decidable in the biggest K n submonoid in M. Thus, future research on the star problem can focus on the trace monoids K n. The recently shown decidability equivalence between the star problem and the finite power problem [14] plays a crucial role in the paper.
Partially supported by the PhD program “Specification of discrete processes and systems of processes by operational models and logics” of the DFG.
See author’s homepage for a long version including complete proofs [13].
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
J. Berstel. Transductions and Context-Free Languages. B.G.Teubner, Stutt., 1979.
P. Cartier and D. Foata. Problèmes combinatoires de commutation et réarrangements, vol. 85 of Lecture Notes in Mathematics. Springer-Verlag, Berlin, 1969.
M. Clerbout and M. Latteux. Semi-commutations. Inf. and Comp., 73:59–74, 1987.
R. Cori and D. Perrin. Automates et commutations partielles. R.A.I.R.O.-Informatique Théorique et Applications, 19:21–32, 1985.
V. Diekert and Y. Métivier. Partial commutation and traces. In G. Rozenberg and A. Salomaa, eds., Handbook of Formal Languages, Vol. 3, Beyond Words, pages 457–534. Springer-Verlag, Berlin, 1997.
V. Diekert and G. Rozenberg, eds., The Book of Traces. World Scient., 1995.
C. Duboc. Mixed product and asynchronous automata. Theoretical Computer Science, 48:183–199, 1986.
M. Fliess. Matrices de Hankel. J. de Math. Pures et Appl., 53:197–224, 1974.
P. Gastin, E. Ochmański, A. Petit, and B. Rozoy. Decidability of the star problem in A∗ ×{b}∗. Information Processing Letters, 44(2):65–71, 1992.
S. Ginsburg and E. Spanier. Semigroups, Presburger formulas, and languages. Pacific Journal of Mathematics, 16:285–296, 1966.
K. Hashiguchi. A decision procedure for the order of regular events. Theoretical Computer Science, 8:69–72, 1979.
D. Kirsten. A connection between the star problem and the finite power property in trace monoids. In P. van Emde Boas et al., eds., ICALP’99 Proceedings, vol. 1644 of LNCS, pages 473–482. Springer-Verlag, Berlin, 1999.
D. Kirsten. The star problem in trace monoids: Reductions beyond C4. Technical Report MATH-AL-01-2001, Dresden University of Technology, 2001. (submitted)
D. Kirsten and G. Richomme. Decidability equivalence between the star problem and the finite power problem in trace monoids. Theory of Computing Systems, 34:3:193–227, 2001.
A. Mazurkiewicz. Concurrent program schemes and their interpretations. DAIMI Rep. PB 78, Aarhus University, 1977.
Y. Métivier. Une condition suffisante de reconnaissabilité dans un monoïde partiellement commutatif. R.A.I.R.O.-Inform. Théor. et Appl., 20:121–127, 1986.
Y. Métivier and G. Richomme. New results on the star problem in trace monoids. Information and Computation, 119(2):240–251, 1995.
R. Morin. On regular MSC languages and relationships to Mazurkiewicz trace theory. In F. Honsell and M. Miculan, eds., FoSSaCS’2001 Proceedings, vol. 2030 of LNCS, pages 332–346. Springer-Verlag, Berlin, 2001.
E. Ochmański. Recognizable trace languages. Chapter 6 in [6], pages 167–204.
E. Ochmański. Regular Trace Languages (in Polish). PhD thesis, Warszawa, 1984.
E. Ochmański. Notes on a star mystery. Bulletin of the EATCS, 40:252–257, 1990.
G. Pighizzini. Synthesis of nondeterministic asynchronous automata. In M. Droste and Y. Gurevich, eds., Semantics of Progr. Lang. and Model Theory, number 5 in Algebra, Logic and Appl., p. 109–126. Gordon and Breach Sc. Publ., 1993.
G. Richomme. Some trace monoids where both the star problem and the finite power property problem are decidable. In I. Privara et al., eds., MFCS’94 Proceedings, vol. 841 of LNCS, pages 577–586. Springer-Verlag, Berlin, 1994.
J. Sakarovitch. The“last” decision problem for rational trace languages. In I. Simon, ed., LATIN’92 Proc., vol. 583 of LNCS, p. 460–473. Springer-Verlag, 1992.
I. Simon. Limited subsets of a free monoid. In Proceedings of the 19th IEEE Annual Symposium on Found. of Comp. Sc., pages 143–150. North Carolina Press, 1978.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kirsten, D. (2001). The Star Problem in Trace Monoids: Reductions Beyond C4. In: Orejas, F., Spirakis, P.G., van Leeuwen, J. (eds) Automata, Languages and Programming. ICALP 2001. Lecture Notes in Computer Science, vol 2076. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-48224-5_49
Download citation
DOI: https://doi.org/10.1007/3-540-48224-5_49
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-42287-7
Online ISBN: 978-3-540-48224-6
eBook Packages: Springer Book Archive