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.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.