Analysis of algorithms for the recognition of rational and context-free trace languages

A. Avellone; M. Goldwurm

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

  • Volume: 32, Issue: 4-6, page 141-152
  • ISSN: 0988-3754

How to cite

top

Avellone, A., and Goldwurm, M.. "Analysis of algorithms for the recognition of rational and context-free trace languages." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 32.4-6 (1998): 141-152. <http://eudml.org/doc/92583>.

@article{Avellone1998,
author = {Avellone, A., Goldwurm, M.},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
language = {eng},
number = {4-6},
pages = {141-152},
publisher = {EDP-Sciences},
title = {Analysis of algorithms for the recognition of rational and context-free trace languages},
url = {http://eudml.org/doc/92583},
volume = {32},
year = {1998},
}

TY - JOUR
AU - Avellone, A.
AU - Goldwurm, M.
TI - Analysis of algorithms for the recognition of rational and context-free trace languages
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 1998
PB - EDP-Sciences
VL - 32
IS - 4-6
SP - 141
EP - 152
LA - eng
UR - http://eudml.org/doc/92583
ER -

References

top
  1. 1. I. J. AALBERSBERG and E. WELZL, Trace languages defined by regular string languages, R.A.I.R.O. - Informatique Théorique et Applications, 1986, 20, pp. 103-119. Zbl0612.68071MR860763
  2. 2. A. V. AHO, J. E. HOPCROFT and J. D. ULLMAN, The design and analysis of computer algorithms, Addison-Wesley, 1974. Zbl0326.68005MR413592
  3. 3. A. BERTONI and M. GOLDWURM, On the prefixes of a random trace and the membership problem for context-free trace languages. In L. HUGUET and A. POLI, eds, Applied Algebra, Algebraic Algorithms and Error-Correcting Codes (Proceedings AAECC 5), Menorca (Spain) June 15-19, 1987, number 356 in Lecture Notes in Computer Science, pp. 35-59, Berlin-Heidelberg-New York, 1989, Springer. Zbl0679.68134MR1008528
  4. 4. A. BERTONI, M. GOLDWURM and N. SABADINI, Analysis of a class of algorithms for problems on trace languages. In Th. BETH and M. CLAUSEN, eds., Applicable Algebra, Error-Correcting Codes, Combinatorics and Computer Algebra (Proceedings AAECC 4), Karlsruhe (FRG) September 23-26, 1986, number 307 in Lecture Notes in Computer Science, pp. 202-214, Berlin-Heidelberg-New York, 1988, Springer. Zbl0648.68079MR950738
  5. 5. A. BERTONI, G. MAURI and N. SABADINI, Context-free trace languages, In Proceedings 7th Coll. on Trees in Algebra and Programming (CAAP), Lille (France), 1982, pp. 32-42. Zbl0548.68072
  6. 6. A. BERTONI, G. MAURI and N. SABADINI, Equivalence and membership problems for regular trace languages, In Proc. 9th ICALP, number 140 in Lecture Notes in Computer Science, pp. 61-71, Berlin-Heidelberg-New York, 1982, Springer. Zbl0486.68079MR675445
  7. 7. A. BERTONI, G. MAURI and N. SABADINI, Membership problems for regular and context free trace languages, Information and Computation, 1989, 82, pp. 135-150. Zbl0682.68040MR1010929
  8. 8. R. CORI and D. PERRIN, Automates et commutations partielles, R.A.I..R.O. - Informatique Théorique et Applications, 1985, 19 (1), pp. 21-32. Zbl0601.68055MR795769
  9. 9. V. DIEKERT and G. ROZENBERG (Eds.), The book of traces, World Scientific, 1995. MR1478992
  10. 10. C. DUBOC, Commutations dans des monoides libres : un cadre théorique pour l'étude du parallélisme. Thèse, Faculté des Sciences de l'Université de Rouen, 1986. 
  11. 11. M. GOLDWURM, Probabilistic estimation of the number of prefixes of a trace, Theoretical Computer Science, 1992, 92, pp. 249-268. Zbl0747.68034MR1148573
  12. 12. M. H. HARRISON, Introduction to formal language theory, Addison-Wesley, 1978. Zbl0411.68058MR526397
  13. 13. A. MAZURKIEWICZ, Concurrent program schemes and their interpretations, DAIMI Rep. PB 78, Aarhus University, Aarhus, 1977. 
  14. 14. E. OCHMANSKI, Regular behaviour of concurrent Systems, Bulletin of the European Association for Theoretical Computer Science (EATCS), Oct 1985, 27, pp. 56-67. 
  15. 15. W. RYTTER, Some properties of trace languages, Fundamenta Informaticae, VII, 1984, pp. 117-127. Zbl0546.68064MR745541
  16. 16. M. SZUJÁRTÓ, A classification and closure properties of languages for describing concurrent System behaviours, Fundamenta Informaticae, 1981, 4 (3), pp. 531-549. Zbl0486.68074MR678010
  17. 17. L. G. VALIANT, General context-free recognition in less than cubic time, Journal of Computer and System Sciences, 1975, 10, pp. 308-315. Zbl0312.68042MR428796

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.