Complexity of E0L structural equivalence
Salomaa, Kai ; Wood, Derick ; Yu, Sheng
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 29 (1995), p. 471-485 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Publié le : 1995-01-01
@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},
     volume = {29},
     year = {1995},
     pages = {471-485},
     mrnumber = {1377026},
     zbl = {0881.68070},
     language = {en},
     url = {http://dml.mathdoc.fr/item/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) pp. 471-485. http://gdmltest.u-ga.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. | MR 1047862 | Zbl 0638.68040

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 1036799 | Zbl 0755.68045

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

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

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 1120667 | Zbl 0734.68036

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 1290547 | Zbl 0821.68056

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 548547 | Zbl 0449.68038

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 1226691 | Zbl 0769.68064

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

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 1226689 | Zbl 0769.68073

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

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 1226690 | Zbl 0769.68074

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

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

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

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 0794.68093

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

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

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 426502

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

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

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

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