Abstract
We compute an asynchronous automaton associated to a recognizable set closed modulo a partial commutation such that the non-commutation graph is without cycle.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
I.J.J. AALBERSBERG, G. ROZENBERG, Trace Theory — a survey, Technical report, Inst. of Appl. and Comp. Sci., University of Leiden, (1985).
R.CORI, Partially abelian monoids, Invited lecture STACS Orsay (1986), Rapport GRECO de Programmation 1.86, Bordeaux.
R. CORI and Y. METIVIER, Recognizable subsets of partially abelian monoids, Theoret. Comp. Sci. 38, (1985), 179–189.
R.CORI et Y.METIVIER, Approximation d'une trace, automates asynchrones et relation d'ordre dans les systèmes répartis, Technical report no 8708, Université de Bordeaux I, 1987.
R. CORI et D. PERRIN, Sur la reconnaissabilité dans les monoïdes partiellements commutatifs libres, RAIRO Inform. Theor. Vol. 19, (1985), 179–185.
S.EILENBERG, Automata, Languages and Machines, Vol. A, 1974, Academic Press.
M. P. FLE and G. ROUCAIROL, Maximal serializability of iterated transactions, Theoret. Comp. Sci. 38, (1985), 1–16.
M. LOTHAIRE, Combinatorics on words, Addison Wesley, 1983.
A. MAZURKIEWICZ, Traces, histories, graphs: instances of a process monoid, Lecture Notes in Comput. Sci. 176, 1984.
Y. METIVIER, On recognizable subsets of free partially commutative monoids, Lecture Notes in Comput. Sci, 226, 1986.
Y. METIVIER, An algorithm for computing asynchronous automata in the case of acyclic non-commutation graphs, Technical report Université de Bordeaux I, 1986.
E. OCHMANSKI, Regular behaviour of concurrent systems, in: EATCS Bulletin, (Oct. 1985).
C. PAPADIMITRIOU, The serializability of concurrent database updates, J.A.C.M. 26, (1979), 631–653.
D. PERRIN, Words over partially commutative alphabet, in: Combinatorial Algorithms on words, Ed.: A. APOSTOLICO and Z. GALIL, NATO ASI-Series. Vol. F12, Springer, (1985).
G. VIENNOT, Heaps of pieces, I: Basic definitions and combinatorial lemmas, Lecture Notes in Math. 1234, 1986, pp. 321–350.
W. ZIELONKA, Notes on asynchronous automata, technical report, Institute of Mathematics, Warsaw Technical University, Poland, (à paraitre dans RAIRO Inform. Theor.).
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1987 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Metivier, Y. (1987). An algorithm for computing asynchronous automata in the case of acyclic non-commutation graphs. In: Ottmann, T. (eds) Automata, Languages and Programming. ICALP 1987. Lecture Notes in Computer Science, vol 267. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-18088-5_18
Download citation
DOI: https://doi.org/10.1007/3-540-18088-5_18
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-18088-3
Online ISBN: 978-3-540-47747-1
eBook Packages: Springer Book Archive