×
Varricchio, Stefano

On the decidability of the equivalence problem for partially commutative rational power series. (English) Zbl 0779.20038

Theor. Comput. Sci. 99, No. 2, 291-299 (1992).
The author uses the equality theorem of Eilenberg, T. Harju and J. Karhumäki [see Theor. Comput. Sci. 78, 347-355 (1991; Zbl 0727.68063)] and the embedding result of G. Duchamp and D. Krob [LITP Report No. 90, 64 (1990)] to show that the equivalence problem is decidable for rational power series over a free partially commutative monoid.
Reviewer: T.J.Harju (Turku)

Cited in 2 Documents

MSC:

20M05 Free semigroups, generators and relations, word problems
20M35 Semigroups in automata theory, linguistics, etc.
68Q45 Formal languages and automata

Keywords:

equality theorem; equivalence problem; rational power series; free partially commutative monoid

Citations:

Zbl 0727.68063
Cite Review PDF
Full Text: DOI

References:

[1] Aalbersbeg, IJ. J.; Welzel, E., Trace languages defined by regular string languages, RAIRO Inform. Théor. Appl., 20, 103-119 (1986) · Zbl 0612.68071
[2] Berstel, J.; Reutenauer, C., Rational Series and Their Languages (1988), Springer: Springer Berlin · Zbl 0668.68005
[3] Bertoni, A.; Mauri, G.; Sabadini, N., Equivalence and membership problems for regular trace languages, (ICALP ’82. ICALP ’82, Lecture Notes in Computer Science, Vol. 140 (1982), Springer: Springer Berlin), 61-72 · Zbl 0486.68079
[4] Bertoni, A.; Mauri, G.; Sabadini, N., Unambiguous regular trace languages, (Algebra, Combinatorics and Logic in Computer Sciences. Algebra, Combinatorics and Logic in Computer Sciences, Colloq. Math. Soc. János Bolyai, Vol. 42 (1985), North-Holland: North-Holland Amsterdam), 113-123 · Zbl 0627.68060
[5] Bruschi, D.; Pighizzini, G.; Zabadini, N., On the existence of minimal asynchronous automata and on the equivalence problem for unambiguous regular trace languages, (STACS ’88. STACS ’88, Lectures Notes in Computer Science, Vol. 294 (1988), Springer: Springer Berlin), 334-346 · Zbl 0644.68099
[6] Choffrut, C., Free partially commutative monoids, Research Report LITP 86-20 (1986), Paris
[7] Duchamp, G.; Krob, D., The lower central series of the free partially commutative group, LITP Report No. 90.64 (1990), Paris · Zbl 0814.20025
[8] Duchamp, G.; Krob, D., Partially commutative formal power series, LITP Report no. 90.64 (1990), Paris · Zbl 0814.20025
[9] Eilenberg, S., Automata, Languages and Machines, Vol. A (1974), Academic Press: Academic Press New York · Zbl 0317.94045
[10] Fisher, P. C.; Rozemberg, A. L., Multitape one-way nonwriting automata, J. Comput. System Sci., 2, 88-101 (1968) · Zbl 0159.01504
[11] Harju, T.; Karhumäki, J., Decidability of the multiplicity equivalence of multitape finite automata, Theoret. Comput. Sci., 78, 347-355 (1991) · Zbl 0727.68063
[12] Mazurkiewicz, A., Concurrent program schemes and their interpretations, (DAIMI Report PB-78 (1977), Aarhus University)
[13] Passman, D. S., The Algebraic Structure of Group Rings (1977), Wiley: Wiley New York · Zbl 0366.16003
[14] Sakarovitch, J., On regular trace languages, Theoret. Comput. Sci., 52, 59-75 (1987) · Zbl 0634.68076
[15] Salomaa, A.; Soittola, M., Automata-Theoretic Aspects of Formal Power Series (1978), Springer: Springer New York · Zbl 0377.68039
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.