The independence of certain operations on semiAFLs
Book, Ronald V. ; Greibach, Sheila A.
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 12 (1978), p. 369-385 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Publié le : 1978-01-01
@article{ITA_1978__12_4_369_0,
     author = {Book, Ronald V. and Greibach, Sheila A.},
     title = {The independence of certain operations on semiAFLs},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {12},
     year = {1978},
     pages = {369-385},
     mrnumber = {517636},
     zbl = {0388.68068},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_1978__12_4_369_0}
}

Book, Ronald V.; Greibach, Sheila A. The independence of certain operations on semiAFLs. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 12 (1978) pp. 369-385. http://gdmltest.u-ga.fr/item/ITA_1978__12_4_369_0/

1. B. Baker and R. Book, Reversal-bounded Multipushdown Machine, J. Comput. Syst. Sc., Vol. 8, 1974, pp. 315-332. | MR 375844 | Zbl 0309.68043

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

3. R. Book and S. Greibach, Quasirealtime Languages, Math. Syst. Theory, Vol. 4, 1970, pp. 97-111. | MR 276019 | Zbl 0188.33102

4. R. Book, S. Greibach and C. Wrathall, Comparison and Reset Machines, to be presented at 5th Intl. Golloq. Automata, Languages and Programming, Udine, Italy, 1978. | MR 556604 | Zbl 0388.03017

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

6. R. Book, M. Nivat and M. Paterson, Reversal-bounded Acceptors and Intersections of Linear Languages, SIAM J. Computing, Vol. 3, 1974, pp. 283-295. | MR 433992 | Zbl 0292.68023

7. R. Book and B. Wegbreit, A Note on AFLs and Bounded Erasing, Inform. and Control, Vol. 19, 1971, pp. 18-29. | MR 319411 | Zbl 0237.68021

8. R. Book and C. Wrathall, On Languages Specified by Relative Acceptance, Theoret. Comput. Sc., Vol. 7, 1978 (to appear). | MR 509016 | Zbl 0385.68061

9. P. C. Fischer, A. R. Meyer and A. L. Rosenberg, Counter Machines and Counter Languages, Math. Syst. Theory, Vol. 2, 1968, pp. 265-283. | MR 235932 | Zbl 0165.32002

10. S. Ginsburg and J. Goldsttne, Intersection Closed full AFL and the Recursively Enumerables Languages, Inform. and Control, Vol. 22, 1973, pp. 201-231. | MR 327087 | Zbl 0267.68035

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

12. S. Ginsburg, S. Greibach and M. A. Harrison, One-way Stack Automata, J. Assoc. Comput. Mach., Vol. 14, 1967, pp. 389-418. | MR 243944 | Zbl 0171.14803

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. J. Goldstine, Continuous Operations on Languages, Math. Syst. Theory, Vol. 11, 1977, pp. 29-46. | MR 455567 | Zbl 0364.68068

15. S. Greibach, The Unsolvability of the Recognition of Linear Context-free Languages, J. Assoc Comput. Mach., Vol. 13, 1966, pp. 582-587. | MR 205770 | Zbl 0148.00901

16. S. Greibach, An Infinite Hierarchy of Context-free Languages, J. Assoc. Comput. Mach., Vol. 16, 1969, pp. 91-106. | MR 238632 | Zbl 0182.02002

17. S. Greibach, Erasing on Context-free AFLs, Inform. and Control, Vol. 21, 1972, pp. 436-465. | MR 331876 | Zbl 0248.68036

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

19. S. Greibach, Remarks on the Complexity of Nondeterministic Counter Languages, Theoret. Comput. Sc., Vol. 1, 1976, pp. 269-288. | MR 411257 | Zbl 0332.68039

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

21. S. Greibach, One-way Finite Visit Automata, Theoret. Comput. Sc, Vol. 6, 1978, pp. 175-221. | MR 489039 | Zbl 0368.68059

22. S. Greibach, Remarks on Blind and Partially Blind Multicounter Machines, Theoret. Comput. Sc. (to appear). | Zbl 0389.68030

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

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

25. K. Klingenstein, ρ-matrix Languages, Theoret. Comput. Sc. (to appear).

26. J. L. Peterson, Computation Sequence Sets, J. Comput. Syst. Sc, Vol. 13, 1976, pp. 1-24. | MR 411260 | Zbl 0354.68100

27. V. Rajlich, Absolutely Parallel Grammars and two-way Finite-state Transducers, J. Comput. Syst. Sc, Vol. 6, 1972, pp. 324-342. | MR 300833 | Zbl 0246.68013

28. V. Rajlich, Bounded-crossing transducers, Inform. and Control, Vol. 27, 1975, pp. 329-335. | MR 373377 | Zbl 0297.68069

29. J. I. Seiferas, M. J. Fischer and A. R. Meyer, Separating Deterministic time Complexity Classes, J. Assoc. Comput. Mach., Vol. 25, 1978, pp. 146-167. | MR 464703 | Zbl 0366.68038

30. G. S. Sacerdote and R. L. Tenney, The Dedidability of the Reachability Problem for Vector Addition Systems, Proc. 9th Annual Symposium on Theory of Computing, Boulder, Colorado, May 1977, pp. 61-76. | MR 488989

31. R. Siromoney, On Equal Matrix Languages, Inform. and Control, Vol. 14, 1969, pp. 135-151. | MR 253838 | Zbl 0169.31402