The strong independence of substitution and homomorphic replication
Greibach, S. A.
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 12 (1978), p. 213-234 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Publié le : 1978-01-01
@article{ITA_1978__12_3_213_0,
     author = {Greibach, S. A.},
     title = {The strong independence of substitution and homomorphic replication},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {12},
     year = {1978},
     pages = {213-234},
     mrnumber = {510639},
     zbl = {0387.68048},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_1978__12_3_213_0}
}

Greibach, S. A. The strong independence of substitution and homomorphic replication. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 12 (1978) pp. 213-234. http://gdmltest.u-ga.fr/item/ITA_1978__12_3_213_0/

1. A. V. Aho, Indexed Grammars. An Extension of Context-Free Grammars, J. Assoc. Comp. Mach., Vol. 15, 1968, pp. 647-671. | MR 258547 | Zbl 0175.27801

2. P. Asveld and J. Engelfriet, Iterated Deterministic Substitution, Acta Informatica, Vol. 8, 1977, pp. 285-302. | MR 478764 | Zbl 0343.68034

3. R. Book, Simple Representations of Certain Classes of Languages, J. Assoc. Comp. Mach., Vol. 25, 1978, pp. 23-31. | MR 461992 | Zbl 0364.68073

4. R. Book and M. Nivat, Linear Languages and the Intersection Closures of Classes of Languages, S.I.A.M. J. Computing, Vol. 7, 1978, pp. 167-177. | MR 492911 | Zbl 0376.68049

5. R. Book and C. Wrathall, On Languages Specified byRelative Acceptance, Theoret. Comp. Science (to appear). | Zbl 0385.68061

6. R. W. Ehrich and S. S. Yau, Two-Way Sequential Transductions and Stack Automata, Inform. and Control, Vol. 18, 1971, pp. 404-446. | MR 311427 | Zbl 0222.94063

7. C. C. Elgot and J. E. Mezei, On Relations Defined by Generalized Finite Automata, I.B.M. J. Res. and Devel., Vol. 9, 1975, pp. 47-68. | MR 216903 | Zbl 0135.00704

8. J. Engelfriet and E. M. Schmidt, 10 and 01, J. Comput. Syst. Sc. (to appear).

9. J. Engelfriet and S. Skyum, Copying Theorems, Inform. Processing Letts., Vol. 4, 1976, pp. 157-161. | MR 400806 | Zbl 0323.68051

10. S. Ginsburg, , Algebraic and Automata-Theoretic Properties of Formal Languages, North-Holland, Amsterdam, 1975. | MR 443446 | Zbl 0325.68002

11. S. Ginsburg and S. A. Greibach, Abstract Families of Languages, in Studies in Abstract Families of Languages GINSBURG, GREIBACH and HOPCROFT, eds., Memoirs Amer. Math. Soc., Vol. 87, 1969, pp. 1-32. | MR 297491

12. S. Ginsburg and S. A. Greibach, Principal AFL, J. Comput. Syst. Sc., Vol. 4, 1970, pp. 308-338. | MR 286599 | Zbl 0198.03102

13. S. Ginsburg and E. H. Spanier, AFL with the Semilinear Property, J. Comput. Syst. Sc., Vol. 5, 1971, pp. 365-396. | MR 339558 | Zbl 0235.68029

14. S. Ginsburg, and E. H. Spanier, Dérivation-Bounded Languages, J. Comput. Syst. Sc., Vol. 2, 1968, pp. 228-250. | MR 241201 | Zbl 0176.16703

15. S. Greibach, Chains of Full AFLs, Math. Syst. Theory, Vol. 4, 1970, pp. 231-242. | MR 329324 | Zbl 0203.30102

16. S. Greibach, Checking Automata and One-Way Stack Languages, J. Comput. Syst. Sc., Vol. 3, 1969, pp. 196-217. | MR 243953 | Zbl 0174.02702

17. S. Greibach, Control Sets on Context-Free Grammar Forms, J. Comput. Syst. Sc., Vol. 15, 1977, pp. 35-98. | MR 502294 | Zbl 0359.68093

18. S. Greibach, Erasing in Context-Free AFLs, Inform. and Control, Vol. 21, 1972, pp. 436-465. | MR 331876 | Zbl 0248.68036

19. S. Greibach, One-Way Finite Visit Automata, Theoret. Comput. Sc., Vol. 6, 1978, pp. 175-222. | MR 489039 | Zbl 0368.68059

20. S. Greibach, Full AFLs and Nested Iterated Substitution, Inform. and Control, Vol. 16, 1970, pp. 7-35. | MR 269446 | Zbl 0188.03102

21. S. Greibach, Syntactic Operators on Full Semi AFLs, J. Comput. Syst. Sc., Vol. 6, 1972, pp. 30-76. | MR 307535 | Zbl 0269.68046

22. S. Greibach and S. Ginsburg, Multitape AFA, J. Assoc Comput. Mach., Vol. 19, 1972, pp. 193-221. | MR 300828 | Zbl 0241.68031

23. O. H. Ibarra, Controlled Pushdown Automata, inform. Sc., Yol. 6, 1973, pp. 327-342. | MR 327080 | Zbl 0278.68047

24. N. A. Khabbaz, Control Sets on Linear Grammars, Inform. and Control, Vol. 25, 1974, pp. 206-221. | MR 356590 | Zbl 0298.68059

25. N. A. Khabbaz, A Geometrical Hierarchy of Languages, J. Comput. Syst. Sc., Vol. 8, 1974, pp. 142-157. | MR 334595 | Zbl 0294.68029

26. K. Klingenstein, Structures of Bounded Languages in Certain Classes of Languages, Inform. and Control (to appear).

27. K. Klingenstein, p-Matrix Languages, Theoret. Comput. Sc. (to appear).

28. A. Nerode, Linear Automata Transformations, Proc. Amer. Math. Soc., Vol. 9, 1958, pp. 541-544. | MR 135681 | Zbl 0089.33403

29. W. Ogden, A Helpful Result in Proving Inherent Ambiguity, Math. Syst. Theory, Vol. 2, 1968, pp. 191-194. | MR 233645 | Zbl 0175.27802

30. A. Salomaa, Formal Languages, Academic Press, New York, 1973. | MR 438755 | Zbl 0262.68025

31. A. Salomaa, Macros, Iterated Substitution and Lindenmayer AFLs, DAIMI, PB-18, University of Aarhus, Aarhus, Denmark.

32. I. H. Sudborough, On the Complexity of the Membership Problem for some Extensions of Context-Free Languages, Intl. J. Computer Math. (to appear). | MR 464751 | Zbl 0398.68037

33. M. Latteux, Cônes rationnels commutativement clos, R.A.I.R.O. Informatique théorique, Vol. 11, 1977, pp. 29-51. | Numdam | MR 478782 | Zbl 0354.68103

34. J. Engelfriet, Three Hierarchies of Transducers, Memo 217, Dept. Appl. Math., Twente Univ. Technology, 1978.

35. A. Van Der Walt, Locally Linear Families of Languages, Inform. and Control, Vol. 32, 1976, pp. 27-32. | MR 411265 | Zbl 0336.68031