On the hierarchy of Petri net languages

Matthias Jantzen

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

  • Volume: 13, Issue: 1, page 19-30
  • ISSN: 0988-3754

How to cite

top

Jantzen, Matthias. "On the hierarchy of Petri net languages." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 13.1 (1979): 19-30. <http://eudml.org/doc/92087>.

@article{Jantzen1979,
author = {Jantzen, Matthias},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {Petri Net Languages; Least Intersection-Closed Full Trio; One-Sided Dyck Langugage; Computation Sequence Sets},
language = {eng},
number = {1},
pages = {19-30},
publisher = {EDP-Sciences},
title = {On the hierarchy of Petri net languages},
url = {http://eudml.org/doc/92087},
volume = {13},
year = {1979},
}

TY - JOUR
AU - Jantzen, Matthias
TI - On the hierarchy of Petri net languages
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 1979
PB - EDP-Sciences
VL - 13
IS - 1
SP - 19
EP - 30
LA - eng
KW - Petri Net Languages; Least Intersection-Closed Full Trio; One-Sided Dyck Langugage; Computation Sequence Sets
UR - http://eudml.org/doc/92087
ER -

References

top
  1. 1. B. S. BAKER and R. V. BOOK, Reversal-Bounded Multipushdown Machines, J. Comp. Syst. Sc., Vol. 8, 1974, pp. 315-332. Zbl0309.68043MR375844
  2. 2. E. T. BELL, Interpolated Denumerants and Lambert Series, Amer. J. Math., Vol. 65, 1943, pp. 382-386. Zbl0060.09603MR9043
  3. 3. W. BRAUER, On Grammatical Complexity of Context-Free Languages, M.F.C.S. Proceedings of Symposium and Summerschool, High Tatras, 1973, pp. 191-196. MR398178
  4. 4. S. CRESPI-REGHIZZI and D. MANDRIOLI, Petri Nets and Commutative Grammars, Technical Report 74-5, Istituto Elettronica del Politecnico di Milano, 1974. 
  5. 5. S. CRESPI-REGHIZZI and D. MANDRIOI, A Decidability Theorem for a Class of Vector-Addition Systems, Information Processing Letters, Vol. 3, 1975, pp. 78-80. Zbl0302.68065MR421162
  6. 6. S. CRESPI-REGHIZZI and D. MANDRIOLI, Petri Nets and Szilard Languages, Information and Control, Vol. 33, 1977, pp. 177-192. Zbl0354.68098MR426506
  7. 7. S. GINSBURG and S. A. GREIBACH, Principal AFL, J. Comp. Syst. Sc., Vol. 4, 1970, pp. 308-338. Zbl0198.03102MR286599
  8. 8. S. GINSBURG, Algebraic and Automata-Theoretic Properties of Formal Languages, North-Holland Publishing Company, 1975. Zbl0325.68002MR443446
  9. 9. S. GINSBURG, J. GOLDSTINE and S. A. GREIBACH, Some Uniformly Erasable Families of Languages, Theoretical Computer Science, Vol. 2, 1976, pp. 29-44. Zbl0343.68033MR411254
  10. 10. S. A. GREIBACH, An Infinite Hierarchy of Context-Free Languages, J. Assoc. Computing Machinery, Vol. 16, 1969, pp. 91-106. Zbl0182.02002MR238632
  11. 11. S. A. GREIBACH, Remarks on the Complexity of Nondeterministic Counter Languages, Theoretical Computer Science, Vol. 1, 1976, pp. 269-288. Zbl0332.68039MR411257
  12. 12. S. A. GREIBACH, Remarks on Blind and Partially Blind One-Way Multicounter Machines, Submitted for Publication, 1978. Zbl0389.68030MR513714
  13. 13. M. HACK, Petri Net Languages, Computation Structures Group Memo 124, Project MAC, M.I.T., 1975. 
  14. 14. M. HÖPNER, Über den Zusammenhang von Szilardsprachen und Matrixgrammatiken, Technical Report IFI-HH-B-12/74, Univ. Hamburg, 1974. 
  15. 15. M. HÖPNER and M. OPP, About Three Equational Classes of Languages Built up by Shuffle Operations, Lecture Notes in Computer Science, Springer, Vol. 45, 1976, pp. 337-344. Zbl0413.68072
  16. 16. M. JANTZEN, Eigenschaften von Petrinetzsprachen, Research Report, Univ. Hamburg, 1978. 
  17. 17. M. LATTEUX, Cônes rationnels commutativement clos, R.A.I.R.O., Informatique théorique, Vol. 11, 1977, pp. 29-51. Zbl0354.68103MR478782
  18. 18. J. VAN LEEUWEN, A Partial Solution to the Reachibility-Problem for Vector Addition Systems, Proceedings of the 6th annual A.CM. Symposium on Theory of Computing, 1974, pp. 303-309. Zbl0362.68105MR413611
  19. 19. E. MORIYA, Associate Languages and Derivational Complexity of Formal Grammars and Languages, Information and Control, Vol. 22, 1973, pp. 139-162. Zbl0254.68017MR323171
  20. 20. B. O. NASH, Reachibility Problems in Vector-Addition Systems, Amer. Math. Monthly, Vol. 80, 1973, pp. 292-295. Zbl0273.68034MR319420
  21. 21. J. L. PETERSON, Computation Sequence Sets, J. Comp. Syst. Sc., Vol. 13, 1976, pp. 1-24. Zbl0354.68100MR411260
  22. 22. M. PENTTONEN, On Derivation Languages Corresponding to Context-Free Grammars, Acta Informatica, Vol. 3, 1974, pp. 285-293. Zbl0268.68033MR349074
  23. 23. G. S. SACERDOTE and R. L. TENNEY, The Decidability of the Reachability Problem for Vector-Addition Systems, Proceedings of the 9th annual A.C.M. Symposium on Theory of Computing, 1977, pp. 61-76. MR488989
  24. 24. A. SALOMAA, Formal Languages, Academic Press New York and London, 1973. Zbl0262.68025MR438755
  25. 25. E. D. STOTZKIJ, On Some Restrictions on Derivations in Phrase-Structure Grammars, Akad. Nauk. S.S.S.R. Nauchno-Tekhn., Inform. Ser. 2, 1967, pp. 35-38 (in Russian). 
  26. 26. R. VALK, Self-Modifying Nets, Technical Report IFI-HH-B-34/77, Univ. Hamburg, 1977. Zbl0415.68025
  27. 27. G. VIDAL-NAQUET, Méthodes pour les problèmes d'ndécidabilité et de complexité sur les réseaux de Petri, in Proceedings of the AFCET Workshop on Petri Nets, Paris, 1977, pp. 137-144. 

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.