On the structure of recognizable languages of dependence graphs

A. Ehrenfeucht; H. J. Hoogeboom; G. Rozenberg

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (1993)

  • Volume: 27, Issue: 1, page 7-22
  • ISSN: 0988-3754

How to cite

top

Ehrenfeucht, A., Hoogeboom, H. J., and Rozenberg, G.. "On the structure of recognizable languages of dependence graphs." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 27.1 (1993): 7-22. <http://eudml.org/doc/92440>.

@article{Ehrenfeucht1993,
author = {Ehrenfeucht, A., Hoogeboom, H. J., Rozenberg, G.},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {theory of traces; dependence graph; behaviour; concurrent system; safe Petri net; RecDG language},
language = {eng},
number = {1},
pages = {7-22},
publisher = {EDP-Sciences},
title = {On the structure of recognizable languages of dependence graphs},
url = {http://eudml.org/doc/92440},
volume = {27},
year = {1993},
}

TY - JOUR
AU - Ehrenfeucht, A.
AU - Hoogeboom, H. J.
AU - Rozenberg, G.
TI - On the structure of recognizable languages of dependence graphs
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 1993
PB - EDP-Sciences
VL - 27
IS - 1
SP - 7
EP - 22
LA - eng
KW - theory of traces; dependence graph; behaviour; concurrent system; safe Petri net; RecDG language
UR - http://eudml.org/doc/92440
ER -

References

top
  1. [AR1] IJ. J. AALBERSBERG and G. ROZENBERG, Theory of Traces, Theoretical Computer Science, Vol. 60 1988, pp. 1-82. Zbl0652.68017MR947532
  2. [AR2] IJ. J. AALBERSBERG and G. ROZENBERG, Traces, Dependency Graphs and DNLC Grammars, Discrete Applied Mathematics, Vol. 11 1985, pp. 299-306. Zbl0601.68045MR792896
  3. [AW] IJ. J. AALBERSBERG and E. WELZL, Trace Languages Defined by Regular String Languages, RAIRO Informatique Théorique, Vol. 20 1986, pp. 103-119 Zbl0612.68071MR860763
  4. [BMS] 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.68079MR675445
  5. [CF] P. CARTIER and D. FOATA, Problèmes combinatoires de commutation et rearrangements, Lecture Notes in Mathematics, Vol. 85, 1981. Zbl0186.30101
  6. [CP] R. CORI and D. PERRIN, Automates et commutations partielles, RAIRO Informatique Théorique, Vol. 19, 1985, pp. 21-32 Zbl0601.68055MR795769
  7. [ENR] 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.00027MR707856
  8. [ER] 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.68031MR911917
  9. [FR] 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. [K] 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. [Ml] A. MAZURKIEWICZ, Concurrent Program Schemes and their Interpretations, Dept. of Computer Science, University of Aarhus, Technical Report No. PB-78, Aarhus, 1977. 
  12. [M2] A. MAZURKIEWICZ, Semantics of Concurrent Systems: a Modular Fixed Point Approach, Lecture Notes in Computer Science, Vol. 188, 1985, pp. 353-375. Zbl0576.68044MR807209
  13. [Me] Y. METIVIER, Une condition suffisante de reconnaissabilité dans un monoïde partiellement commutatif, RAIRO Informatique Théorique, Vol. 20, 1986, pp. 121-127. Zbl0599.20107MR860764
  14. [O] E. OCHMANSKI, Regular Trace Languages, Ph.D. Thesis, Dept. of Mathematics, University of Warsaw, 1985. 
  15. [P] D. PERRIN, Partial Commutations, Lecture Notes in Computer Science, Vol. 372, pp. 637-651. MR1037081
  16. [RW] G. ROZENBERG and E. WELZL, Boundary NLC grammars. Basic Definitions, Normal Forms and Complexity, Information and Control, Vol. 69, 1986, pp. 136-167. Zbl0608.68060MR848438

NotesEmbed ?

top

You must be logged in to post comments.