Complexity of E0L structural equivalence

Kai Salomaa; Derick Wood; Sheng Yu

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

  • Volume: 29, Issue: 6, page 471-485
  • ISSN: 0988-3754

How to cite

top

Salomaa, Kai, Wood, Derick, and Yu, Sheng. "Complexity of E0L structural equivalence." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 29.6 (1995): 471-485. <http://eudml.org/doc/92519>.

@article{Salomaa1995,
author = {Salomaa, Kai, Wood, Derick, Yu, Sheng},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {E0L structural equivalence},
language = {eng},
number = {6},
pages = {471-485},
publisher = {EDP-Sciences},
title = {Complexity of E0L structural equivalence},
url = {http://eudml.org/doc/92519},
volume = {29},
year = {1995},
}

TY - JOUR
AU - Salomaa, Kai
AU - Wood, Derick
AU - Yu, Sheng
TI - Complexity of E0L structural equivalence
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 1995
PB - EDP-Sciences
VL - 29
IS - 6
SP - 471
EP - 485
LA - eng
KW - E0L structural equivalence
UR - http://eudml.org/doc/92519
ER -

References

top
  1. 1. J. L. BALCÁZAR, J. DIÁZ and J. GABARRÓ, Structural Complexity I and II, EATCS Monographs on Theoretical Computer Science, Vol. 11 and Vol. 22, (Eds. W. Brauer, G. Rozenberg, A. Salomaa), Springer-Verlag, Berlin-Heidelberg, 1988 & 1900. Zbl0638.68040MR1047862
  2. 2. J. DASSOW, J. HROMKOVIC, J. KARHUMAKI, B. ROVAN and A. SLOBODOVÁ, On the power of synchronization in parallel computations, Proc. of the 14th Symposium on Mathematical Foundations of Computer Science, MFCS'89, Lect. Notes Comput. Sci., 379, Springer-Verlag, 1989, pp. 196-206. Zbl0755.68045MR1036799
  3. 3. A. K. CHANDRA, D. C. KOZEN and L. J. STOCKMEYER, Alternation, J. Assoc. Comput. Math., 1981, 28, pp. 114-133. Zbl0473.68043MR603186
  4. 4. F. GÉCSEG and M. STEINBY, Tree automata, Akadémiai Kiadó, Budapest, 1984. Zbl0537.68056MR735615
  5. 5. J. HROMKOVIČ, J. KARHUMAKI, B. ROVAN and A. SLOBODOVÁ, On the power of synchronization in parallal computations, Discrete Appl. Math., 1991, 32, pp. 155-182. Zbl0734.68036MR1120667
  6. 6. J. HROMKOVIČ, B. ROVAN and A. SLOBODOVÁ, Deterministic versus nondeterministic space in ternis of synchronized alternating machines, Theory. Comput. Sci., 1994, 132, pp. 319-336. Zbl0821.68056MR1290547
  7. 7. G. ISTRATE, The strong equivalence of ETOL grammars. In: Developments in Language Theory, G. Rozenberg and A. Salomaa (eds.), World, Scientific, 1994, pp. 81-89. 
  8. 8. N. JONES and S. SKYUM, Complexity of some problems concerning L Systems, Math. Systems Theory, 1979, 13, pp. 29-43. Zbl0449.68038MR548547
  9. 9. K. - J. LANGE and M. SCHUDY, The complexity of the emptiness problem for EOL Systems. In: Lindenmayer Systems; Impacts on Theoretical Computer Science, Computer Graphics, and Developmental Biology, G. Rozenberg and A. Salomaa (eds.), Springer, 1992, pp. 167-175. Zbl0769.68064MR1226691
  10. 10. R. MCNAUGHTON, Parenthesis grammars, J. Assoc. Comput. Mach., 1967, 14, pp. 490-500. Zbl0168.01206MR234781
  11. 11. V. NIEMI, A normal form for structurally equivalent EOL grammars. In: Lindenmayer Systems: Impacts on Theoretical Computer Science, Computer Graphics, and Developmental Biology, G. Rozenberg and A. Salomaa (eds.), Springer-Verlag, 1992, pp. 133-148. Zbl0769.68073MR1226689
  12. 12. T. OTTMANN and D. WOOD, Defining families of trees with EOL grammars, Discrete Applied Math., 1991, 32, pp. 195-209. Zbl0746.68054MR1120669
  13. 13. T. OTTMANN and D. WOOD, Simplifications of EOL grammars. In Lindenmayer Systems: Impacts on Theoretical Computer Science, Computer Graphics, and Developmental Biology, G. Rozenberg and A. Salomaa (eds)., Springer-Verlag, 1992, pp. 149-166. Zbl0769.68074MR1226690
  14. 14. M. PAULL and S. UNGER, Structural equivalence of context-free grammars, J. Comput. System Sci., 1968, 2, pp. 427-463. Zbl0179.02301MR241203
  15. 15. G. ROZENBERG and A. SALOMAA, The Mathematical Theory of L Systems, Academic Press, New York, 1980. Zbl0508.68031MR561711
  16. 16. K. SALOMAA and S. Yu, Decidability of structural equivalence of EOL grammars, Theoret Comput. Sci., 1991, 82, pp. 131-139. Zbl0729.68039MR1112113
  17. 17. K. SALOMAA, D. WOOD and S. Yu, Structural equivalence and ETOL grammars, Proc. of the 9th Conference on Fundamentals of Computation Theory, FCT'93, Lect. Notes Comput. Sci., 710, Springer-Verlag, 1993, pp. 430-439. Zbl0794.68093
  18. 18. H. SEIDL, Deciding equivalence of finite tree automata, SIAM J. Comput., 1990, 19, pp. 424-437. Zbl0699.68075MR1041537
  19. 19. A. SLOBODOVÁ, Communication for alternating machines, Acta Inform., 1992, 29, pp. 425-441. Zbl0769.68022MR1184436
  20. 20. J. W. TATCHER, Tree automata: an informal survey. In: Currents in the Theory of Computing, A. V. Aho (ed.), Prentice Hall, Englewood Cliffs, NJ, 1973, pp. 143-172. MR426502
  21. 21. J. VAN LEEUWEN, The membership question for ETOL languages is polynomially complete, Inform. Process. Lett., 1975, 3, pp. 138-143. Zbl0309.68065MR471461
  22. 22. J. VAN LEEUWEN, The tape-complexity of context-independent developmental languages, 7. Comput System. Sci., 1975, 11, pp. 203-211. Zbl0314.68017MR381397
  23. 23. J. WIEDERMANN, On the power of synchronization, J. Inf. Process. Cybern. EIK, 1989, 25, pp. 499-506. Zbl0689.68074MR1044337
  24. 24. D. WOOD, Theory of Computation, John Wiley & Sons, New York, 1987. (Second edition, 1996, in preparation.) Zbl0734.68001

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.