Learning two-tape automata from queries and counterexamples

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Learning two-tape automata from queries and counterexamples

Full text

Pdf (774 KB)

Source

Annual Workshop on Computational Learning Theory archive
Proceedings of the sixth annual conference on Computational learning theory table of contents

Santa Cruz, California, United States

Pages: 228 - 235

Year of Publication: 1993

ISBN:0-89791-611-5

Author

Takashi Yokomori

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGART: ACM Special Interest Group on Artificial Intelligence

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 22, Citation Count: 0

Additional Information:

references index terms collaborative colleagues

Tools and Actions:	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/168304.168338 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	V. Amar and G. Putzolu. Generalizations of regulax events. Information and Control, 8:56-63, 1965.
	2	D. Angluin. Learning k-bounded context-free grammars. Res. Rep. 557, Dept. of Comput. Sci., YALE Univ, 1987.
	3	Dana Angluin, Learning regular sets from queries and counterexamples, Information and Computation, v.75 n.2, p.87-106, November 1, 1987 [doi>10.1016/0890-5401(87)90052-6]
	4	D: Angluin and D.N. Hoover. Regular prefix relations. Mathem~ticdl Systems Theory, 17:167-191, 1984.
	5	P. Berman and R. Roo6. Learning one-counter languages in polynomial time. In 2Sth IEEE Syrup. on FOC$, pages 61-67, 1987.
	6	W Brauer , K-J Lange, Non-deterministic two-tape automata are more powerful than deterministic ones, Proceedings on STACS 85 2nd annual symposium on theoretical aspects of computer science, p.71-79, December 1985, Saarbru:9Aicken, Germany
	7	S. Eilenberg, C.C. Elgot and J.C. Shepherdson. Sets recognized by n-tape automata. J. of Algebra, 13:447-464, 1969.
	8	C.C. Elgot and J.E. Mezei. On relation defined by generalized finite automata. IBM J. Research and Development, 9:47-68, 1965.
	9	Seymour Ginsburg, Algebraic and Automata-Theoretic Properties of Formal Languages, Elsevier Science Inc., New York, NY, 1975
	10	S.A. Goldman, R.L. Rivest, and R.E.Schapire. Learning binary relations and total orders. In 30th IEEE Syrup. on FOCS, pages 46-51, 1989.
	11	J.N. Gray and M.A. Harrison. The theory of sequential relations. Informatzon and Control, 9:435- 468, 1966.
	12	M.A. A. Harrison , M. A. Harrison, Introduction to Formal Language Theory, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1978
	13	Hiroki Ishizaka, Polynomial Time Learnability of Simple Deterministic Languages, Machine Learning, v.5 n.2, p.151-164, Jun. 1990 [doi>10.1023/A:1022644732619]
	14	M. Rabin and D. Scott. Finite automata and their decision problem. IBM J. Research and Development, 3:114-125, 1959.
	15	A.L. Rozenberg. A machine realization of the linear context-free languages. Informatwn and Control, 10:175-188, 1967.
	16	E. Shapiro. Inductive inference of theories from facts. PLea. Pep. 192, Dept. of Comput. Sci., YALE Univ, 1981.
	17	H. Shirakawa and T. Yokomori. Polynomialtime MAT learning of C-deterministic context-free grammars. Transactwns of Informatzon Processing Soczety of Japan, 34(3):380-390, 1993.
	18	Yuji Takada, Grammatical interface for even linear languages based on control sets, Information Processing Letters, v.28 n.4, p.193-199, July 29, 1988 [doi>10.1016/0020-0190(88)90208-6]
	19	T. Yokomori. Learning non-determinisitc finite automata from queries and eounterexamples. (to appear). In Machine Intellifence Vol. 13 (Furukawa, Michie and Muggleton, Eds.), 1993.