Trading monotonicity demands versus mind changes

• Angluin, D. (1980), Inductive inference of formal languages from positive data, Information and Control, 45 (1980), 117–135.

  Google Scholar 

• Barzdin, Ya.M., and Freivalds, R.V. (1972), On the prediction of general recursive functions, Sov. Math. Dokl. 13, 1224–1228.

  Google Scholar 

• Barzdin, Ya.M., Kinber, E.B., and Podnieks, K.M. (1974), Об ускорении синтеза и прогнозирования φункций, in “Теория Алгоритмов и Программ,” Vol. 1 (Ya.M. Barzdin, Ed.) Latvian State University, Riga, pp. 117–128.

  Google Scholar 

• Case, J., and Smith, C.H. (1983), Comparison of identification criteria for machine inductive inference, Theoretical Computer Science25, 193–220.

  Google Scholar 

• Gasarch, W.I., and Velauthapillai, M. (1992), Asking questions versus verifiability, in “Proceedings 3rd International Workshop on Analogical and Inductive Inference,” (K.P. Jantke, ed.) Lecture Notes in Artificial Intelligence Vol. 642, pp. 197–213, Springer-Verlag, Berlin.

  Google Scholar 

• Gold, M.E. (1967), Language identification in the limit, Information and Control10, 447–474.

  Google Scholar 

• Hopcroft, J.E., and Ullman, J.D. (1969), “Formal Languages and their Relation to Automata,” Addison-Wesley, Reading, Massachusetts.

  Google Scholar 

• Jantke, K.P. (1991), Monotonic and non-monotonic inductive inference, New Generation Computing8, 349–360.

  Google Scholar 

• Kapur, S., and Bilardi, G. (1992), Language learning without overgeneralization, in “Proceedings 9th Annual Symposium on Theoretical Aspects of Computer Science,” (A. Finkel and M. Jantzen, Eds.), Lecture Notes in Computer Science Vol. 577, pp. 245–256, Springer-Verlag, Berlin.

  Google Scholar 

• Kinber, E.B. (1994), Monotonicity versus efficiency for learning languages from texts, in “Proceedings 5th Workshop on Algorithmic Learning Theory,” (S. Arikawa and K.P. Jantke, Eds.), Lecture Notes in Artificial Intelligence Vol. 872, pp. 395–406.

  Google Scholar 

• Lange, S. (1994), The representation of recursive languages and its impact on the efficiency of learning, in “Proceedings 7th Annual ACM Conference on Computational Learning Theory, New Brunswick, July 1994,” pp. 256–267, ACM Press, New York.

  Google Scholar 

• Lange, S., and Zeugmann, T. (1993a), Monotonic versus non-monotonic language learning, in “Proceedings 2nd International Workshop on Non-monotonic and Inductive Logic, December 1991, Reinhardsbrunn,” (G. Brewka, K.P. Jantke and P.H. Schmitt, Eds.), Lecture Notes in Artificial Intelligence Vol. 659, pp. 254–269, Springer-Verlag, Berlin.

  Google Scholar 

• Lange, S., and Zeugmann, T. (1993b), Learning recursive languages with bounded mind changes, International Journal of Foundations of Computer Science4, 157–178.

  Google Scholar 

• Lange, S., and Zeugmann, T. (1993c), Language learning in dependence on the space of hypotheses, in “Proceedings 6th Annual ACM Conference on Computational Learning Theory,” pp. 127–136, ACM Press, New York.

  Google Scholar 

• Lange, S., and Zeugmann, T. (1994), Trading monotonicity demands versus efficiency, Bulletin of Informatics and Cybernetics, to appear.

  Google Scholar 

• Lange, S., Zeugmann, T., and Kapur, S. (1994), Monotonic and dual-monotonic language learning, Theoretical Computer Science, to appear.

  Google Scholar 

• Machtey, M., and Young, P. (1978), “An Introduction to the General Theory of Algorithms,” North-Holland, New York.

  Google Scholar 

• Mukouchi, Y. (1992), Inductive inference with bounded mind changes, in “Proceedings 3rd Workshop on Algorithmic Learning Theory,” Tokyo, Japan, JSAI, pp. 125–134.

  Google Scholar 

• Mukouchi, Y. (1994), Inductive inference of recursive concepts, Ph.D. Thesis, R1FIS, Kyushu University 33, RIFIS-TR-CS-82, March 25th.

  Google Scholar 

• Osherson, D., Stob, M., and Weinstein, S. (1986), “Systems that Learn, An Introduction to Learning Theory for Cognitive and Computer Scientists,” MIT-Press, Cambridge, Massachusetts.

  Google Scholar 

• Shinohara, T. (1990), Inductive Inference from Positive Data is Powerful, in “Proc. 3rd Annual Workshop on Computational Learning Theory,” pp. 97–110, Morgan Kaufmann Publishers Inc.

  Google Scholar 

• Wiehagen, R. (1991), A thesis in inductive inference, in “Proceedings First International Workshop on Nonmonotonic and Inductive Logic,” (J. Dix, K.P. Jantke and P.H. Schmitt, Eds.), Lecture Notes in Artificial Intelligence 543, pp. 184–207, Springer-Verlag, Berlin.

  Google Scholar 

• Wiehagen, R., and Zeugmann, T. (1994), Ignoring data may be the only way to learn efficiently, Journal Experimental and Theoretical Artificial Intelligence6, 131–144.

  Google Scholar 

Download references