Complexity of E0L structural equivalence
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 29 (1995) no. 6, pp. 471-485. 
@article{ITA_1995__29_6_471_0,
     author = {Salomaa, Kai and Wood, Derick and Yu, Sheng},
     title = {Complexity of {E0L} structural equivalence},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {471--485},
     publisher = {EDP-Sciences},
     volume = {29},
     number = {6},
     year = {1995},
     mrnumber = {1377026},
     zbl = {0881.68070},
     language = {en},
     url = {http://www.numdam.org/item/ITA_1995__29_6_471_0/}
}
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
SP  - 471
EP  - 485
VL  - 29
IS  - 6
PB  - EDP-Sciences
UR  - http://www.numdam.org/item/ITA_1995__29_6_471_0/
LA  - en
ID  - ITA_1995__29_6_471_0
ER  - 
%0 Journal Article
%A Salomaa, Kai
%A Wood, Derick
%A Yu, Sheng
%T Complexity of E0L structural equivalence
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 1995
%P 471-485
%V 29
%N 6
%I EDP-Sciences
%U http://www.numdam.org/item/ITA_1995__29_6_471_0/
%G en
%F ITA_1995__29_6_471_0
Salomaa, Kai; Wood, Derick; Yu, Sheng. Complexity of E0L structural equivalence. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 29 (1995) no. 6, pp. 471-485. http://www.numdam.org/item/ITA_1995__29_6_471_0/

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. | MR | Zbl

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. | MR | Zbl

3. A. K. Chandra, D. C. Kozen and L. J. Stockmeyer, Alternation, J. Assoc. Comput. Math., 1981, 28, pp. 114-133. | MR | Zbl

4. F. Gécseg and M. Steinby, Tree automata, Akadémiai Kiadó, Budapest, 1984. | MR | Zbl

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. | MR | Zbl

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. | MR | Zbl

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. N. Jones and S. Skyum, Complexity of some problems concerning L Systems, Math. Systems Theory, 1979, 13, pp. 29-43. | MR | Zbl

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. | MR | Zbl

10. R. Mcnaughton, Parenthesis grammars, J. Assoc. Comput. Mach., 1967, 14, pp. 490-500. | MR | Zbl

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. | MR | Zbl

12. T. Ottmann and D. Wood, Defining families of trees with EOL grammars, Discrete Applied Math., 1991, 32, pp. 195-209. | MR | Zbl

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. | MR | Zbl

14. M. Paull and S. Unger, Structural equivalence of context-free grammars, J. Comput. System Sci., 1968, 2, pp. 427-463. | MR | Zbl

15. G. Rozenberg and A. Salomaa, The Mathematical Theory of L Systems, Academic Press, New York, 1980. | MR | Zbl

16. K. Salomaa and S. Yu, Decidability of structural equivalence of EOL grammars, Theoret Comput. Sci., 1991, 82, pp. 131-139. | MR | Zbl

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. | Zbl

18. H. Seidl, Deciding equivalence of finite tree automata, SIAM J. Comput., 1990, 19, pp. 424-437. | MR | Zbl

19. A. Slobodová, Communication for alternating machines, Acta Inform., 1992, 29, pp. 425-441. | MR | Zbl

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. | MR

21. J. Van Leeuwen, The membership question for ETOL languages is polynomially complete, Inform. Process. Lett., 1975, 3, pp. 138-143. | MR | Zbl

22. J. Van Leeuwen, The tape-complexity of context-independent developmental languages, 7. Comput System. Sci., 1975, 11, pp. 203-211. | MR | Zbl

23. J. Wiedermann, On the power of synchronization, J. Inf. Process. Cybern. EIK, 1989, 25, pp. 499-506. | MR | Zbl

24. D. Wood, Theory of Computation, John Wiley & Sons, New York, 1987. (Second edition, 1996, in preparation.) | Zbl