Trace languages defined by regular string languages

 Access to full text

 Full (PDF)

1. 1. IJ.J. AALBERSBERG and G. ROZENBERG, Traces - a Survey, Techn. Rep. 85-16, Inst. of Appl. Math. and Comput. Sc., Univ. of Leiden, Leiden, 1985. 
2. 2. IJ. J. AALBERSBERG and G. ROZENBERG, Traces, Dependency Graphs and DNLC Grammars, Discrete Appl. Math, Vol. 11, 1985, pp.299-306. Zbl0601.68045MR792896
3. 3. A. BERTONI, M. BRAMBILLA, G. MAURI and N. SABADINI, An Application of the Theory of Free Partially Commutative Monoids : Asymptotic Densities of Trace Languages, Lecture Notes in Computer Science, Vol. 118, 1981, pp. 205-215. Zbl0468.68081
4. 4. A. BERTONI, G. MAURI and N. SABADINI, A Hierarchy of Regular Trace Languages and Sorne Combinatorial Applications, Proc. 2nd.World Conf. on Math, at the Service of Men, Las Palmas, 1982, pp.146-153. Zbl0512.68056
5. 5. A. BERTONI, G. MAURI and N. SABADINI, Equivalence and Membership Problems for Regular Trace Languages, Lecture Notes in Computer Science, Vol. 140, 1982, pp. 61-71. Zbl0486.68079MR675445
6. 6. A. BERTONI, G. MAURI and N. SABADINI, Unambiguous Regular Trace Languages, to appear in Algebra, Combinatorics and Logic in Comput. Sc. (to appear), Colloquia Math. Soc. J. Bolay. Zbl0627.68060MR875858
7. 7. R. CORI and D. PERRIN, Automates et Commutations Partielles, R.A.I.R.O., Inform. Théor., Vol. 19, 1985, pp. 21-32. Zbl0601.68055MR795769
8. 8. M. FLEISS, Matrices de Hankel, J. Math. Pures Appl., Vol. 53, 1974, pp. 197-222. Zbl0315.94051MR364328
9. 8. S. GINSBURG, The Mathematical Theory of Context Free Languages, Mc-Graw-Hill Book Company, New York, London, 1966. Zbl0184.28401MR211815
10. 10. J. E. HOPCROFT and J. D. ULLMAN, Introduction to automata theory, languages and computation, Addison -Wesley, Reading, Mass, 1979. Zbl0426.68001MR645539
11. 11. G. LALLEMENT, Semigroups and combinatorial applications, J. Wiley and Sons, New York, 1979. Zbl0421.20025MR530552
12. 12. A. MAZURKIEWICZ, Concurrent Program Schemes and Their Interpretations, DAIMI Rep. PB-78, Aarhus Univ., Aarhus, 1977. 
13. 13. A. MAZURKIEWICZ, Traces, Histories, Graphs: Instances of a Process Monoid, Lecture Notes in Computer Science, Vol. 176, 1984, pp.115-133. Zbl0577.68061MR783441
14. 14. A. MAZURKIEWICZ, Semantics of Concurrent Systems: a Modular Fixed-Point Trace Approach, Lecture Notes in Computer Science, Vol. 188, 1985, pp.353-375. Zbl0576.68044MR807209
15. 15. J. SAKAROVITCH, On Regular Trace Languages, R.A.I.R.O., Inform. Théor. (to appear). MR918113
16. 16. A. SALOMAA, Theory of automata, Pergamon Press, Oxford - New York, 1969. Zbl0193.32901MR262021
17. 17. A. SALOMAA, Formal languages, Academic Press, New York, 1973. Zbl0262.68025MR438755
18. 18. M. SZIJARTO, A Classification and Closure Properties of Languages for Describing Concurrent System Behaviours, Fund. Inform., Vol. 4, 1981, pp. 531-549. Zbl0486.68074MR678010
19. 19. A. TARLECKI, Notes on the Implementability of Formal Languages by Concurrent Systems, ICS PAS Rep. 481, Inst. of Comput. Sc., Polish Acad. of Sc., Warshaw, 1982. 

1. G. Guaiana, A. Restivo, S. Salemi, Complete subgraphs of bipartite graphs and applications to trace languages
2. A. Avellone, M. Goldwurm, Analysis of algorithms for the recognition of rational and context-free trace languages
3. A. Ehrenfeucht, H. J. Hoogeboom, G. Rozenberg, On the structure of recognizable languages of dependence graphs