Simple Representations of Certain Classes of Languages

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Simple Representations of Certain Classes of Languages

Full text

Pdf (674 KB)

Source

Journal of the ACM (JACM) archive
Volume 25 , Issue 1 (January 1978) table of contents

Pages: 23 - 31

Year of Publication: 1978

ISSN:0004-5411

Author

Ronald V. Book

Department of Mathematics and Computer Science Program, University of California, Santa Barbara, CA

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 25, Citation Count: 1

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/322047.322050 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	BAKER, B , ANO BOOK, R. Reversal-bounded multl-pushdown machmes J Comptr Syst Sci 8 (1974), 315-332
	2	BooK, R, Ar~O NIVAT, M Linear languages and intersections of classes of languages To appear in SIAM J Comptng
	3	BOOK, R, NIVAT, M, AND PATERSON, M Reversal-bounded acceptors and intersections of hnear languages SIAM J. Comptng 3 (1974), 283-295
	4	GINSnURG, S , AriD GREmACH, S Principal AFL J Comptr Syst Set 4 (1970), 308-338.
	5	GINSBURG, S , GREIBACH, S., AND HOPCROFr, S Pre-AFL Studtes tn Abstract Famlhes of Languages, Memoir No 87, Amer Math Soc, Providence, R I , 1969, pp 41-51
	6	GINSBURC, S , AND SPANtER, E Ftmte-term pushdown automata SlAM J Control 4 (1966), 429-453
	7	GINSBUR~, S , AND SPANIER, E AFL w~th the semdmear property. J Comptr Syst Sct 5 (1971), 365- 396
	8	GREmACI~, S Control sets on context-free grammar forms To appear m J Comptr Syst. Scz.
	9	GREmACH, S One-way fimte wslt automata To appear m Theoret. Comptr. Sct
	10	KLEENE, S lntroductton to Metamathemattcs Van Nostrand, Princeton, N J , 1952.
	11	KLINGENSTmN, K Structures of bounded languages m certain famd~es of languages To appear m Inform Control
	12	KLINGENSTEIN, K p-matrix languages To appear m Theoret Comptr Sct.
	13	Hartley Rogers, Jr., Theory of recursive functions and effective computability, MIT Press, Cambridge, MA, 1987
	14	STOCKMEYER, L The polynomml-tlme hierarchy Theoret Comptr Scz. 3 (1977), 1-224
	15	SUDBOROU6H, I H The complexity of the membership problem for some extenstons of context-free languages To appear m Int J. Comptr. Math
	16	WRATHALL, C Subrecurswe predicates and automata Ph D Diss , Harvard U , Cambridge, Mass, 1975.
	17	WRATHALL, C Complete sets and polynomml hterarchy Theoret Comptr. Sct 3 (1977), 23-33
	18	WRATHALL, C Characterizations of the Dyck sets To appear m Revue Francazse d'Automatlque, lnformattque , Recherche Operattonnelle 11 (1977)
	19	WRATrIALL, C Rudimentary predicates and relatwe computation To appear m SlAM J Comptng