×

zbMATH — the first resource for mathematics

On the structure of recognizable languages of dependence graphs. (English) Zbl 0787.68060
Summary: Within the theory of traces a dependence graph represents a behaviour of a concurrent system (e.g., a safe Petri net) in a very much the same way that a string represents a behaviour of a sequential system (e.g., a finite automaton). A recognizable language of dependence graphs, RecDG language) for short, represents the set of all behaviours of a concurrent system (with a “regular behaviour”).
We characterize naked RecDG languages, i.e., the sets of unlabelled graphs obtained by erasing labels from graphs of RecDG languages.
MSC:
68Q45 Formal languages and automata
68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
PDF BibTeX XML Cite
Full Text: DOI EuDML
References:
[1] IJ. J. AALBERSBERG and G. ROZENBERG, Theory of Traces, Theoretical Computer Science, Vol. 60 1988, pp. 1-82. Zbl0652.68017 MR947532 · Zbl 0652.68017
[2] IJ. J. AALBERSBERG and G. ROZENBERG, Traces, Dependency Graphs and DNLC Grammars, Discrete Applied Mathematics, Vol. 11 1985, pp. 299-306. Zbl0601.68045 MR792896 · Zbl 0601.68045
[3] IJ. J. AALBERSBERG and E. WELZL, Trace Languages Defined by Regular String Languages, RAIRO Informatique Théorique, Vol. 20 1986, pp. 103-119 Zbl0612.68071 MR860763 · Zbl 0612.68071
[4] A. BERTON, G. MAURI and N. SABADIN, Equivalence and Membership Problems for Regular Trace Languages, Lecture Notes in Computer Science, Vol. 140, 1982, pp. 61-71. Zbl0486.68079 MR675445 · Zbl 0486.68079
[5] P. CARTIER and D. FOATA, Problèmes combinatoires de commutation et rearrangements, Lecture Notes in Mathematics, Vol. 85, 1981. · Zbl 0186.30101
[6] R. CORI and D. PERRIN, Automates et commutations partielles, RAIRO Informatique Théorique, Vol. 19, 1985, pp. 21-32 Zbl0601.68055 MR795769 · Zbl 0601.68055
[7] H. EHRIG, M. NAGL and G. ROZENBERG eds. Graph Grammars and their Applications to Computer Science, Lecture Notes in Computer Science, Vol. 153 1983. Zbl0512.00027 MR707856 · Zbl 0512.00027
[8] A. EHRENFEUCHT and G. ROZENBERG, On the structure of dependency graphs, in: Concurrency and nets, K. Voss, H. J. GENRICH, G. ROZENBERG Eds., Springer Verlag, 1987, pp. 141-170. Zbl0642.68031 MR911917 · Zbl 0642.68031
[9] M. P. FLÉ and G. ROUCAIROL, On Serizlizability of Iterated Transactions, Proc. ACM SIGACT-SIGOPS Symp. on Principles of Distributed Computing, 1982, pp. 194-200.
[10] R. M. KELLER, A Solvable Program-Schema Equivalence Problem, Proc. 5th Annual Princeton Conference on Information Sciences and Systems, Princeton, 1971, pp. 301-306.
[11] A. MAZURKIEWICZ, Concurrent Program Schemes and their Interpretations, Dept. of Computer Science, University of Aarhus, Technical Report No. PB-78, Aarhus, 1977.
[12] A. MAZURKIEWICZ, Semantics of Concurrent Systems: a Modular Fixed Point Approach, Lecture Notes in Computer Science, Vol. 188, 1985, pp. 353-375. Zbl0576.68044 MR807209 · Zbl 0576.68044
[13] Y. METIVIER, Une condition suffisante de reconnaissabilité dans un monoïde partiellement commutatif, RAIRO Informatique Théorique, Vol. 20, 1986, pp. 121-127. Zbl0599.20107 MR860764 · Zbl 0599.20107
[14] E. OCHMANSKI, Regular Trace Languages, Ph.D. Thesis, Dept. of Mathematics, University of Warsaw, 1985.
[15] D. PERRIN, Partial Commutations, Lecture Notes in Computer Science, Vol. 372, pp. 637-651. MR1037081
[16] G. ROZENBERG and E. WELZL, Boundary NLC grammars. Basic Definitions, Normal Forms and Complexity, Information and Control, Vol. 69, 1986, pp. 136-167. Zbl0608.68060 MR848438 · Zbl 0608.68060
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.