Regularity and Related Problems for Deterministic Pushdown Automata

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Regularity and Related Problems for Deterministic Pushdown Automata

Full text

Pdf (741 KB)

Source

Journal of the ACM (JACM) archive
Volume 22 , Issue 1 (January 1975) table of contents

Pages: 1 - 10

Year of Publication: 1975

ISSN:0004-5411

Author

Leslie G. Valiant

Centre for Computer Studies, The University of Leeds, Leeds LS2 9JT, United Kingdom and Carnegie-Mellon University, Pittsburgh, Pennsylvania

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 7, Downloads (12 Months): 48, Citation Count: 3

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/321864.321865 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	GINSBURG, S , AND GREIBACH, S A. Deterministic context-free languages. Inform and Contr 9 (1966), 620-668
	2	GINSBURG, S., AND SPANIER, E Finite-turn pushdown automata SIAM J. Control ~ (1966), 423-434
	3	HAa~ISON, M. A, AND HAVEL, I M. Strict deterministic grammars. J. Comput ~yst Sc~ 7 (1973) 237-277.
	4	Hxa~isoN, M A., ASp HAV~L, I. M Real t~me strict deterministic languages. SIAM J Computsng I (1972) 333-349
	5	KO~NJAK, A. J, AND HOPCROF% J E S~mple deterministic languages. IEEE 7th Symp. on Switching and Automata Theory, Berkeley, Calif., 1966, pp. 36-46.
	6	P. M. Lewis, II , R. E. Stearns, Syntax-Directed Transduction, Journal of the ACM (JACM), v.15 n.3, p.465-488, July 1968 [doi>10.1145/321466.321477]
	7	HEV~R, A. R, AND FISCHER, M J Economy of descriptmn by automata, grammars, and formal ~systems IEEE 12th Symp on Swltchlng and Automata Theory, 1971, 188-191.
	8	ROSENXR~NTZ, D j, X~D STEARNS, R. E. Properties of deterministic topdown grammars. Inform. and Conlr 17 (1970) 226-255
	9	ST~^RNS, R.E. A regularity test for pushdown machines. Inform and Cont. 11 (1967), 323-340
	10	L. G. Valiant, Decision Procedures for Families of Deterministic Pushdown Automata, University of Warwick, Coventry, UK, 1973
	11	VALXANT, b. G. The eqmvalence problem for deterministic fimte-turn pushdown automata Inform. and Contr ~5 (1974), 123-133
	12	VALIANT, L G.. AN~ PATERSON, M S. Deterministic one-counter automata. J. Comput. ,Syst. Sc~. (to appear).
	13	VALIANT, L.G. Manuscript.

CITED BY 3

	Christian Choffrut , Flavio DAlessandro , Stefano Varricchio, Note: On the separability of sparse context-free languages and of bounded rational relations, Theoretical Computer Science, v.381 n.1-3, p.274-279, August, 2007
	Andreas Malcher, On recursive and non-recursive trade-offs between finite-turn pushdown automata, Journal of Automata, Languages and Combinatorics, v.12 n.1, p.265-277, January 2007
	Pedro V. Silva, Rational subsets of partially reversible monoids, Theoretical Computer Science, v.409 n.3, p.537-548, December, 2008