×
Metivier, Y.

On recognizable subsets of free partially commutative monoids. (English) Zbl 0658.20031

Theor. Comput. Sci. 58, No. 1-3, 201-208 (1988).
Author’s abstract: “We show that, in a free partially abelian monoid generated by a finite alphabet A, the subset [X] of \(A^*\) containing all the words equivalent to a word of X is recognizable if X is recognizable and if any iterative factor h has a connected noncommutation graph.”
Reviewer: I.Peák

Cited in 11 Documents

MSC:

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

Keywords:

free partially abelian monoid; finite alphabet; words; recognizable
PDF BibTeX XML Cite
\textit{Y. Metivier}, Theor. Comput. Sci. 58, No. 1--3, 201--208 (1988; Zbl 0658.20031)
Full Text: DOI

References:

[1] AAlbersberg, I. J.J.; Rozenberg, G., Trace Theory—a survey, (Tech. Rept. (1985), Institute of Applied Mathematics and Computer Science, University of Leiden)
[3] Berstel, J., Transductions and Context-Free Languages (1979), Teubner: Teubner Stuttgart · Zbl 0424.68040
[4] Bertoni, A.; Mauri, G.; Sabadini, N., Equivalence and membership problems for regular trace languages, (Proc. 9th ICALP 1982. Proc. 9th ICALP 1982, Lecture Notes in Computer Science, 140 (1982), Springer: Springer Berlin), 61-71 · Zbl 0486.68079
[5] Cartier, P.; Foata, D., Problèmes combinatoires de commutation et de réarrangements, (Lecture Notes in Mathematics, 85 (1969), Springer: Springer Berlin) · Zbl 0186.30101
[6] Cori, R.; Perrin, D., Sur la reconnaissabilité dans les monoïdes partiellement commutatifs libres, RAIRO Inform. Théor., 19, 21-32 (1985)
[7] Cori, R.; Métivier, Y., Recognizable subsets of partially abelian monoids, Theoret. Comput. Sci., 35, 179-189 (1985) · Zbl 0559.20040
[8] Flé, M. P.; Roucairol, G., Maximal serializability of iterated transactions, Theoret. Comput. Sci., 38, 1-16 (1985) · Zbl 0572.68082
[9] Lothhaire, M., Combinatorics on Words (1983), Addison-Wesley: Addison-Wesley Reading, MA
[10] McNaughton, R.; Yamada, Y., Regular expressions and state graphs for automata, IRE Trans. On Electric Comput., EC-9, 38-47 (1960) · Zbl 0156.25501
[11] Métivier, Y., Une condition suffisante de reconnaissabilité dans un monoïde partiellement commutatif, RAIRO Inform. Théor., 20, 121-127 (1986) · Zbl 0599.20107
[12] Perrin, D., Words over a partially commutative alphabet, (Apostolico, A.; Galil, Z., Combinatorial Algorithms on Words, F12 (1985), Springer: Springer Berlin), NATO ASI-Series · Zbl 0602.68070
[13] Ochmanski, E., Regular behaviour of concurrent systems, EATCS Bull. (October 1985)
[14] Viennot, G., Empilement et commutation: théorie combinatoire et applications, (Proc. Coll. Combinatoire énumérative. Proc. Coll. Combinatoire énumérative, Lecture Notes in Mathematics, 1234 (1987), Springer: Springer Berlin), 321-350, Montréal 1985
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.