The independence of certain operations on semiAFLs

Ronald V. Book; Sheila A. Greibach

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (1978)

  • Volume: 12, Issue: 4, page 369-385
  • ISSN: 0988-3754

How to cite

top

Book, Ronald V., and Greibach, Sheila A.. "The independence of certain operations on semiAFLs." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 12.4 (1978): 369-385. <http://eudml.org/doc/92086>.

@article{Book1978,
author = {Book, Ronald V., Greibach, Sheila A.},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
language = {eng},
number = {4},
pages = {369-385},
publisher = {EDP-Sciences},
title = {The independence of certain operations on semiAFLs},
url = {http://eudml.org/doc/92086},
volume = {12},
year = {1978},
}

TY - JOUR
AU - Book, Ronald V.
AU - Greibach, Sheila A.
TI - The independence of certain operations on semiAFLs
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 1978
PB - EDP-Sciences
VL - 12
IS - 4
SP - 369
EP - 385
LA - eng
UR - http://eudml.org/doc/92086
ER -

References

top
  1. 1. B. BAKER and R. BOOK, Reversal-bounded Multipushdown Machine, J. Comput. Syst. Sc., Vol. 8, 1974, pp. 315-332. Zbl0309.68043MR375844
  2. 2. R. BOOK, Simple Representations of Certain Classes of Languages, J. Assoc. Comput. Mach., Vol. 25, 1978, pp. 23-31. Zbl0364.68073MR461992
  3. 3. R. BOOK and S. GREIBACH, Quasirealtime Languages, Math. Syst. Theory, Vol. 4, 1970, pp. 97-111. Zbl0188.33102MR276019
  4. 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. Zbl0388.03017MR556604
  5. 5. R. BOOK M. NIVAT, Linear Languages and the Intersection Closures of Classes of Languages, SIAM J. Computing, Vol. 7, 1978, pp. 167-177. Zbl0376.68049MR492911
  6. 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. Zbl0292.68023MR433992
  7. 7. R. BOOK and B. WEGBREIT, A Note on AFLs and Bounded Erasing, Inform. and Control, Vol. 19, 1971, pp. 18-29. Zbl0237.68021MR319411
  8. 8. R. BOOK and C. WRATHALL, On Languages Specified by Relative Acceptance, Theoret. Comput. Sc., Vol. 7, 1978 (to appear). Zbl0385.68061MR509016
  9. 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. Zbl0165.32002MR235932
  10. 10. S. GINSBURG and J. GOLDSTTNE, Intersection Closed full AFL and the Recursively Enumerables Languages, Inform. and Control, Vol. 22, 1973, pp. 201-231. Zbl0267.68035MR327087
  11. 11. S. GINSBURG and S. GREIBACH, Principal AFL, J. Comput. Syst. Sc., Vol. 4, 1970, pp. 308-338. Zbl0198.03102MR286599
  12. 12. S. GINSBURG, S. GREIBACH and M. A. HARRISON, One-way Stack Automata, J. Assoc. Comput. Mach., Vol. 14, 1967, pp. 389-418. Zbl0171.14803MR243944
  13. 13. S. GINSBURG and E. H. SPANIER, AFL with the Semilinear Property, J. Comput. Syst. Sc., Vol. 5, 1971, pp. 365-396. Zbl0235.68029MR339558
  14. 14. J. GOLDSTINE, Continuous Operations on Languages, Math. Syst. Theory, Vol. 11, 1977, pp. 29-46. Zbl0364.68068MR455567
  15. 15. S. GREIBACH, The Unsolvability of the Recognition of Linear Context-free Languages, J. Assoc Comput. Mach., Vol. 13, 1966, pp. 582-587. Zbl0148.00901MR205770
  16. 16. S. GREIBACH, An Infinite Hierarchy of Context-free Languages, J. Assoc. Comput. Mach., Vol. 16, 1969, pp. 91-106. Zbl0182.02002MR238632
  17. 17. S. GREIBACH, Erasing on Context-free AFLs, Inform. and Control, Vol. 21, 1972, pp. 436-465. Zbl0248.68036MR331876
  18. 18. S. GREIBACH, Syntactic Operators on Full semi AFLs, J. Comput. Syst. Sc., Vol. 6, 1972, pp. 30-76. Zbl0269.68046MR307535
  19. 19. S. GREIBACH, Remarks on the Complexity of Nondeterministic Counter Languages, Theoret. Comput. Sc., Vol. 1, 1976, pp. 269-288. Zbl0332.68039MR411257
  20. 20. S. GREIBACH, Control Sets on Context-free Grammar Forms, J. Comput. Syst. Sc., Vol. 15, 1977, pp. 35-98. Zbl0359.68093MR502294
  21. 21. S. GREIBACH, One-way Finite Visit Automata, Theoret. Comput. Sc, Vol. 6, 1978, pp. 175-221. Zbl0368.68059MR489039
  22. 22. S. GREIBACH, Remarks on Blind and Partially Blind Multicounter Machines, Theoret. Comput. Sc. (to appear). Zbl0389.68030
  23. 23. S. GREIBACH and S. GINSBURG, Multitape AFA, J. Assoc. Comput. Mach., Vol. 19, 1972, pp. 193-21. Zbl0241.68031MR300828
  24. 24. K. KLIGENSTEIN, Structures of Bounded Languages in Certain Classes of Languages, Inform. and Control (to appear). 
  25. 25. K. KLINGENSTEIN, ρ-matrix Languages, Theoret. Comput. Sc. (to appear). 
  26. 26. J. L. PETERSON, Computation Sequence Sets, J. Comput. Syst. Sc, Vol. 13, 1976, pp. 1-24. Zbl0354.68100MR411260
  27. 27. V. RAJLICH, Absolutely Parallel Grammars and two-way Finite-state Transducers, J. Comput. Syst. Sc, Vol. 6, 1972, pp. 324-342. Zbl0246.68013MR300833
  28. 28. V. RAJLICH, Bounded-crossing transducers, Inform. and Control, Vol. 27, 1975, pp. 329-335. Zbl0297.68069MR373377
  29. 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. Zbl0366.68038MR464703
  30. 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. MR488989
  31. 31. R. SIROMONEY, On Equal Matrix Languages, Inform. and Control, Vol. 14, 1969, pp. 135-151. Zbl0169.31402MR253838

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.