Geodesic
Complexity of E0L structural equivalence
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 29 (1995) no. 6, pp. 471-485.

Voir la notice de l'article provenant de la source Numdam

@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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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. | Zbl | MR

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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