On the Independence of Real-Time Definability and Certain Structural Properties of Context-Free Languages

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On the Independence of Real-Time Definability and Certain Structural Properties of Context-Free Languages

Full text

Pdf (480 KB)

Source

Journal of the ACM (JACM) archive
Volume 15 , Issue 4 (October 1968) table of contents

Pages: 672 - 679

Year of Publication: 1968

ISSN:0004-5411

Author

Arnold L. Rosenberg

IBM Watson Research Center, Yorktown Heights, New York

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 14, Citation Count: 3

Additional Information:

abstract 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/321479.321489 What is a DOI?

ABSTRACT

An operator precedence language which is not real-time definable by any multitple Turing machine is constructed. This strengthens previous results about the existence of unambiguous context-free languages (CFL's) which are not real-time definable. In contrast, a family of CFL's of increasing degree of inherent ambiguity, each real-time definable by a one-tape Turing machine, is exhibited. In fact, an unboundedly ambiguous CFL, also real-time definable by a one-tape Turing machine, is presented. These results are the basis for the assertion that real-time definability of a CFL is independent from each of the structural properties considered.

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	BAR-HILLEL, Y., PERLES, M., AND SHAMIR, E. On formal properties of simple phrase structure grammars. Z. Phonetik, Sprachwissen. Kommunikalionsforsch. 1 (1961), 143-172; reprinted in Bar-Hillel, Y., Language and Information, Addison-Wesley, Reading, Mass., 1965, Ch. 9, pp. 116--150.
	2	Robert W. Floyd, Syntactic Analysis and Operator Precedence, Journal of the ACM (JACM), v.10 n.3, p.316-333, July 1963 [doi>10.1145/321172.321179]
	3	GINSBUaO, S., AND GrmIBACH, S. Deterministic context free languages. Inform. Contr. 9 (1966), 620--648.
	4	Seymour Ginsburg , Joseph Ullian, Ambiguity in context free languages, Journal of the ACM (JACM), v.13 n.1, p.62-89, Jan. 1966 [doi>10.1145/321312.321318]
	5	HARVUANIS J., AND STEARNS, R. E. On the computational complexity of algorithms. Trans. Amer. Math. Soc. 117 (1965), 285---306.
	6	Arnold L. Rosenberg, Real-Time Definable Languages, Journal of the ACM (JACM), v.14 n.4, p.645-662, Oct. 1967 [doi>10.1145/321420.321423]
	7	Degrees of inherent ambiguity in context-free languages. IBM Res. Rep. RC-1878, 1967.

CITED BY 3

	Arnold L. Rosenberg, A Note on Ambiguity of Context-Free Languages and Presentations of Semilinear Sets, Journal of the ACM (JACM), v.17 n.1, p.44-50, Jan. 1970
	Sheila A. Greibach, Jump PDA's, deterministic context-free languages principal AFDLs and polynomial time recognition—(Extended Abstract), Proceedings of the fifth annual ACM symposium on Theory of computing, p.20-28, April 30-May 02, 1973, Austin, Texas, United States
	Victor Schneider, A system for designing fast programming language translators, Proceedings of the May 14-16, 1969, spring joint computer conference, May 14-16, 1969, Boston, Massachusetts