Learning branches and learning to win closed games

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Learning branches and learning to win closed games

Full text

Pdf (1.16 MB)

Source

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

Desenzano del Garda, Italy

Pages: 280 - 291

Year of Publication: 1996

ISBN:0-89791-811-8

Authors

Martin Kummer	Institut für Logik, Komplexität und Deduktionssysteme, Universität Karlsruhe, D-76128 Karlsruhe, Germany
Matthias Ott	Institut für Logik, Komplexität und Deduktionssysteme, Universität Karlsruhe, D-76128 Karlsruhe, Germany

Sponsors

Univ degli Studi de Milano : Universite degli Studi de Milano
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): 14, Downloads (12 Months): 25, Citation Count: 2

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/238061.238119 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	Baruch Awerbuch , Margrit Betke , Ronald L. Rivest , Mona Singh, Piecemeal graph exploration by a mobile robot (extended abstract), Proceedings of the eighth annual conference on Computational learning theory, p.321-328, July 05-08, 1995, Santa Cruz, California, United States [doi>10.1145/225298.225337]
	2	A. Blum and P. Chalasani. An on-line algorithm for improving performance in navigation. In 34th Annual Symposium on Foundations of Computer Science, pages 2-11, Palo Alto, California, 3-5 Nov. 1993. IEEE.
	3	J. R. Btichi and L. H. Landweber. Solving sequential conditions by finite-state strategies. Transactions of the American Mathematical Society, 138:295-311, 1969.
	4	John Case , Susanne Kaufmann , Efim B. Kinber , Martin Kummer, Learning recursive functions from approximations, Proceedings of the Second European Conference on Computational Learning Theory, p.140-153, March 13-15, 1995
	5	L. Fortnow, W. Gasarch, S. Jain, E. Kinber, M. Kummet, S. Kurtz, M. Pleszkoch, T. Slaman, R. Solovay, and F. Stephan. Extremes in the degrees of inferability. Annals of Pure andApplied Logic, 66:21-276, 1994.
	6	Lance Fortnow , Duke Whang, Optimality and domination in repeated games with bounded players, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.741-749, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195448]
	7	Y. Freund , M. Kearns , Y. Mansour , D. Ron , R. Rubinfeld , R. E. Schapire, Efficient algorithms for learning to play repeated games against computationally bounded adversaries, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.332, October 23-25, 1995
	8	C. G. Jockusch and R. I. Soare. II~ Classes and Degrees of Theories. Transactions of the American Mathematical Society, 173:33-56, 1972.
	9	Susanne Kaufmann , Martin Kummer, On a Quantitative Notion of Uniformity, Proceedings of the 20th International Symposium on Mathematical Foundations of Computer Science, p.169-178, August 28-September 01, 1995
	10	Martin Kummer , Matthias Ott, Effective Strategies for Enumeration Games, Selected Papers from the9th International Workshop on Computer Science Logic, p.368-387, September 22-29, 1995
	11	A. H. Lachlan. On some games which are relevant to the theory of recursively enumerable sets. Annals of Mathematics, 91(2):291-310, 1970.
	12	O. Maler, A. Pnueli, and J. Sifakis. On the synthesis of discrete controllers for timed systems. In STACS 95, volume 900 of LNCS, pages 229-242. Springer-Verlag, 1995.
	13	E. Martin, D. Luzeaux, and B. Zavidovique. Learning and control from a recursive viewpoint. In IEEE International Symposium on Intelligent Control, Glasgow, Ecosse, 1992.
	14	R. McNaughton. Infinite games played on finite graphs. Annals of Pure and Applied Logic, 65:149-184, 1993.
	15	P. Odifreddi. Classical Recursion Theory. North- Holland, Amsterdam, 1989.
	16	P. Odifreddi. Classical Recursion Theory (Volume II). North-Holland Publishing Co., Amsterdam, To Appear.
	17	Christos H. Papadimitriou , Mihalis Yannakakis, Shortest paths without a map, Theoretical Computer Science, v.84 n.1, p.127-150, July 22, 1991 [doi>10.1016/0304-3975(91)90263-2]
	18	Ronald L. Rivest , Robert E. Schapire, Inference of finite automata using homing sequences, Information and Computation, v.103 n.2, p.299-347, April 1993 [doi>10.1006/inco.1993.1021]
	19	J. G. Thistle , W. M. Wonham, Control of Infinite Behavior of Finite Automata, SIAM Journal on Control and Optimization, v.32 n.4, p.1075-1097, July 1994 [doi>10.1137/S0363012991217536]
	20	Wolfgang Thomas, Automata on infinite objects, Handbook of theoretical computer science (vol. B): formal models and semantics, MIT Press, Cambridge, MA, 1991
	21	W. Thomas. On the synthesis of strategies in infinite games. In STACS 95, volume 900 of LNCS, pages 1- 13. Springer-Verlag, 1995.
	22	Wolfgang Thomas , Helmut Lescow, Logical Specifications of Infinite Computations, A Decade of Concurrency, Reflections and Perspectives, REX School/Symposium, p.583-621, June 01-04, 1993

CITED BY 2

	Learning to win process-control games watching game-masters, Information and Computation, v.174 n.1, p.1-19, April 10, 2002
	John Case , Sanjay Jain , Franco Montagna , Giulia Simi , Andrea Sorbi, On learning to coordinate: random bits help, insightful normal forms, and competency isomorphisms, Journal of Computer and System Sciences, v.71 n.3, p.308-332, October 2005