Characterizations of stack uniform strict deterministic languages

Jan Pittl

Kybernetika (1981)

  • Volume: 17, Issue: 3, page 209-221
  • ISSN: 0023-5954

How to cite

top

Pittl, Jan. "Characterizations of stack uniform strict deterministic languages." Kybernetika 17.3 (1981): 209-221. <http://eudml.org/doc/28582>.

@article{Pittl1981,
author = {Pittl, Jan},
journal = {Kybernetika},
keywords = {pushdown automata; context-free grammars; stack uniform automata; strict deterministic grammars; Greibach normal form},
language = {eng},
number = {3},
pages = {209-221},
publisher = {Institute of Information Theory and Automation AS CR},
title = {Characterizations of stack uniform strict deterministic languages},
url = {http://eudml.org/doc/28582},
volume = {17},
year = {1981},
}

TY - JOUR
AU - Pittl, Jan
TI - Characterizations of stack uniform strict deterministic languages
JO - Kybernetika
PY - 1981
PB - Institute of Information Theory and Automation AS CR
VL - 17
IS - 3
SP - 209
EP - 221
LA - eng
KW - pushdown automata; context-free grammars; stack uniform automata; strict deterministic grammars; Greibach normal form
UR - http://eudml.org/doc/28582
ER -

References

top
  1. A. V. Aho J. D. Ullman, The Theory of Parsing, Translation, and Compiling, Vols. I, II. Prentice Hall, Englewood Cliffs, N. J. 1972, 1973. (1972) 
  2. E. P. Friedman, The inclusion problem for simple languages, Theoretical Computer Science 7 (1976), 297-316. (1976) Zbl0349.68032MR0405936
  3. J. N. Gray M. A. Harrison, On the covering and reduction problems for context-free grammars, J. ACM 19 (1972), 675-698. (1972) MR0359410
  4. M. A. Harrison I. M. Havel, Strict deterministic grammars, Journal of Computer and System Sciences 7 (1973), 237-277. (1973) MR0319415
  5. M. A. Harrison I. M. Havel, Real-time strict deterministic languages, SIAM Journal on Computing 1 (1972), 333-349. (1972) MR0323164
  6. A. J. Korenjak J. E. Hopcroft, Simple deterministic languages, IEEE Conference Record of the 7th Annual Symposium on Switching and Automata Theory (1966), 36 - 46. (1966) 
  7. M. Linna, Two decidability results for deterministic pushdown automata, Journal of Computer and System Sciences 18 (1979), 92-107. (1979) Zbl0399.03023MR0525833
  8. R. McNaughton, Parenthesis grammars, J. ACM 14 (1967), 490-500. (1967) Zbl0168.01206MR0234781
  9. M. Oyamaguchi N. Honda Y. Inagaki, The equivalence problem for real-time strict deterministic languages, Information and Control 45 (1980), 90-115. (1980) MR0582147
  10. J. Pittl, On two subclasses of real-time grammars, Mathematical Foundations of Computer Science 1978 (J. Winkowski, ed.). Lecture Notes in Computer Science 64, Springer-Verlag, Berlin 1978, 426-435. (1978) Zbl0389.68041MR0519859
  11. L. G. Valiant, Decision Problems for Families of Deterministic Pushdown Automata, University of Warwick, Computer Centre, Report No. 7, 1973. (1973) 

NotesEmbed ?

top

You must be logged in to post comments.