Noncounting Context-Free Languages

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Noncounting Context-Free Languages

Full text

Pdf (600 KB)

Source

Journal of the ACM (JACM) archive
Volume 25 , Issue 4 (October 1978) table of contents

Pages: 571 - 580

Year of Publication: 1978

ISSN:0004-5411

Authors

S. Crespi-Reghizzi	Istituto di Scienza dell'Informazione, Università di Pisa, Pisa, Italy
G. Guida	Istituto di Elettrotecnica ed Elettronica, Politecnico di Milano, Piazza Leonardo da Vinci, 32, 20133 Milan, Italy
D. Mandrioli	Istituto di Elettrotecnica ed Elettronica, Politecnico di Milano, Piazza Leonardo da Vinci, 32, 20133 Milan, Italy

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 29, Citation Count: 5

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/322092.322098 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	ARBIB, M A, AND GIVE'ON. Y Algebra automata I lnfo and Contr 12 (1968), 331-345.
	2	BRZOZOWSKk J A Hierarchies of aperiodic languages R A 1 R O, Inform Theonque 10, 8 (1976). 33-49.
	3	CRESPI-REGHIZZI, S NonCountmg languages and learning In Computer Oriented Learning Processes, J C Simon, Ed, Nordhoff, Leyden, 1976
	4	CRESPI-REGHIZZ1, S Reduction of enumeration m grammar acqulsluon Proc 2nd Int Conf on ArUf intell, London, 1971, pp 546-552
	5	CRESPI-REGHIZZI, S, AND DELLA VIGNA, P Approximation of phrase markers by regular sets Proc. Syrup. on Automata, Languages and Programming, IRIA, Rocquencourt, France, i972, 367-376,
	6	CRESPI-REGHIZZI, S, GUIDA, G., AND MANDRIOLI, D. Non-Counting and k-distract and homogeneous context-free languages. Int. Pep. N.76-4, Ismuto dt EllettrotecMca ed Elettromca, Pohtecnico dt Mflano, 1976.
	7	CRESPI-REGHIZZI, S., GUIDA, G., AND MANDRIOLI, D The closure of non-countmg context-free languages with respect to Boolean operation Int Rep N 76-7, IstRuto dl Elettrotecnica ed Elettromca, Pohtecnico dl Mtlano, 1976.
	8	S. Crespi-Reghizzi , M. A. Melkanoff , L. Lichten, The use of grammatical inference for designing programming languages, Communications of the ACM, v.16 n.2, p.83-90, Feb. 1973 [doi>10.1145/361952.361958]
	9	EILENBERG, S, AND WRIGHT, G.B. Automata in general algebra Inform and Contr. 11 (1967), 457-470
	10	James N. Gray , Michael A. Harrison, On the Covering and Reduction Problems for Context-Free Grammars, Journal of the ACM (JACM), v.19 n.4, p.675-698, Oct. 1972 [doi>10.1145/321724.321732]
	11	KURODA, S Y A topological stud) of phrase-structure languages Inform. and Contr 30 (1976), 307-379
	12	MANDRIOLI, D. n-reconstructable context-flee grammars Inform Proc. Letters 5, 2 (1976), 78-80.
	13	MCNAUGHTON R Algebraic decision procedures for local testabihty Math. Syst Theory & 1 (1973), 60-76
	14	Robert McNaughton, Parenthesis Grammars, Journal of the ACM (JACM), v.14 n.3, p.490-500, July 1967 [doi>10.1145/321406.321411]
	15	Robert McNaughton , Seymour A. Papert, Counter-Free Automata (M.I.T. research monograph no. 65), The MIT Press, 1971
	16	SCHUTZENBERGER, M P On finite monoids having only trivial subgroups Inform and Contr 8 (1965), 190-194.
	17	SHYR, H.J, AND THmRRIN, G. Left non-counting languages. Int J Comptr and Inform Sct 4, 1 (1975), 95-102
	18	THATCHER, J.W Tree-automata an informal survey In Currents m the Theory of Computing, A V Aho, Ed, Prentice-Hall, Englewood Cliffs, N.J, 1973
	19	THATCHER, J W, AND WRIGHT, J B Generalized finite automata theory with an application to a decision problem of second-order logic. Math Syst Theory 2. 1 (1968), 57-81

CITED BY 5

	Robert Nix, Editing by example, Proceedings of the 11th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.186-195, January 15-18, 1984, Salt Lake City, Utah, United States
	Dana Angluin, Inference of Reversible Languages, Journal of the ACM (JACM), v.29 n.3, p.741-765, July 1982
	Dana Angluin , Carl H. Smith, Inductive Inference: Theory and Methods, ACM Computing Surveys (CSUR), v.15 n.3, p.237-269, Sept. 1983
	Henning Fernau, Identification of function distinguishable languages, Theoretical Computer Science, v.290 n.3, p.1679-1711, 3 January 2003
	Alessandra Cherubini , Stefano Crespi Reghizzi , Pierluigi San Pietro, Associative language descriptions, Theoretical Computer Science, v.270 n.1-2, p.463-491, January