@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. 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
, and ,2. 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
, , , and ,3. Alternation, J. Assoc. Comput. Math., 1981, 28, pp. 114-133. | MR | Zbl
, and ,4. Tree automata, Akadémiai Kiadó, Budapest, 1984. | MR | Zbl
and ,5. On the power of synchronization in parallal computations, Discrete Appl. Math., 1991, 32, pp. 155-182. | MR | Zbl
, , and ,6. Deterministic versus nondeterministic space in ternis of synchronized alternating machines, Theory. Comput. Sci., 1994, 132, pp. 319-336. | MR | Zbl
, and ,7. The strong equivalence of ETOL grammars. In: Developments in Language Theory, G. Rozenberg and A. Salomaa (eds.), World, Scientific, 1994, pp. 81-89.
,8. Complexity of some problems concerning L Systems, Math. Systems Theory, 1979, 13, pp. 29-43. | MR | Zbl
and ,9. 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
and ,10. Parenthesis grammars, J. Assoc. Comput. Mach., 1967, 14, pp. 490-500. | MR | Zbl
,11. 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. Defining families of trees with EOL grammars, Discrete Applied Math., 1991, 32, pp. 195-209. | MR | Zbl
and ,13. 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
and ,14. Structural equivalence of context-free grammars, J. Comput. System Sci., 1968, 2, pp. 427-463. | MR | Zbl
and ,15. The Mathematical Theory of L Systems, Academic Press, New York, 1980. | MR | Zbl
and ,16. Decidability of structural equivalence of EOL grammars, Theoret Comput. Sci., 1991, 82, pp. 131-139. | MR | Zbl
and ,17. 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
, and ,18. Deciding equivalence of finite tree automata, SIAM J. Comput., 1990, 19, pp. 424-437. | MR | Zbl
,19. Communication for alternating machines, Acta Inform., 1992, 29, pp. 425-441. | MR | Zbl
,20. 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. The membership question for ETOL languages is polynomially complete, Inform. Process. Lett., 1975, 3, pp. 138-143. | MR | Zbl
,22. The tape-complexity of context-independent developmental languages, 7. Comput System. Sci., 1975, 11, pp. 203-211. | MR | Zbl
,23. On the power of synchronization, J. Inf. Process. Cybern. EIK, 1989, 25, pp. 499-506. | MR | Zbl
,24. Theory of Computation, John Wiley & Sons, New York, 1987. (Second edition, 1996, in preparation.) | Zbl
,