Further remarks on the complexity of regulated rewriting

Jürgen Dassow; Gheorghe Păun

Kybernetika (1985)

  • Volume: 21, Issue: 3, page 213-227
  • ISSN: 0023-5954

How to cite

top

Dassow, Jürgen, and Păun, Gheorghe. "Further remarks on the complexity of regulated rewriting." Kybernetika 21.3 (1985): 213-227. <http://eudml.org/doc/28692>.

@article{Dassow1985,
author = {Dassow, Jürgen, Păun, Gheorghe},
journal = {Kybernetika},
keywords = {programmed grammars; matrix grammars; random context grammars; appearance checking; erasing rules},
language = {eng},
number = {3},
pages = {213-227},
publisher = {Institute of Information Theory and Automation AS CR},
title = {Further remarks on the complexity of regulated rewriting},
url = {http://eudml.org/doc/28692},
volume = {21},
year = {1985},
}

TY - JOUR
AU - Dassow, Jürgen
AU - Păun, Gheorghe
TI - Further remarks on the complexity of regulated rewriting
JO - Kybernetika
PY - 1985
PB - Institute of Information Theory and Automation AS CR
VL - 21
IS - 3
SP - 213
EP - 227
LA - eng
KW - programmed grammars; matrix grammars; random context grammars; appearance checking; erasing rules
UR - http://eudml.org/doc/28692
ER -

References

top
  1. J. Dassow, Remarks on the complexity of regulated rewriting, Fund. Inform. 7(1984), 83-103. (1984) Zbl0546.68063MR0745539
  2. S. Ginsburg, The Mathematical Theory of Context-free Languages, McGraw Hill, New York 1966. (1966) Zbl0184.28401MR0211815
  3. J. Gruska, On a classification of context-free languages, Kybernetika 3 (1967), 22-29. (1967) Zbl0158.25401MR0209092
  4. J. Gruska, Descriptional complexity of context-free languages, In: Proc. Symp. Math. Foundations of Computer Science '73, 71 - 83. MR0405938
  5. O. Ibarra, Simple matrix languages, Inform. and Control 17 (1970), 359-394. (1970) Zbl0221.68041MR0274232
  6. O. Mayer, Some restrictive devices for context-free grammars, Inform. and Control 20 (1972), 69-92. (1972) Zbl0248.68035MR0359412
  7. Gh. Păun, Matrix Grammars, (in Romanian). The Scientific and Encyclopaedic Publ. House, Bucharest 1981. (1981) 
  8. Gh. Păun, Six nonterminals are enough for generating a recursively enumerable language by a matrix grammar, Internat. J. Comput. Math. 75 (1984). (1984) MR0745561
  9. A. Pirická-Kelemenová, [unknown], Doctoral dissertation, Bratislava 1980. (1980) 
  10. A. Salomaa, Formal Languages, Academic Press, New York 1973. (1973) Zbl0262.68025MR0438755
  11. A. P. J. van der Walt, Random context languages, Information Processing 1971, North-Holland, Amsterdam 1972, 66-68. (1971) MR0400823

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.