Navegar

Colección

Datos Estadísticas

Conferencia

Rodriguez, N.; Braberman, V.; D'Ippolito, N.; Uchitel, S. "21/2-player generalized reactivity (1) games" (2016) 55th IEEE Conference on Decision and Control, CDC 2016:6996-7001
Estamos trabajando para incorporar este artículo al repositorio
Consulte el artículo en la página del editor

Abstract:

We introduce a new class of 21/2-player games, the 21/2-player GR(1) games, that allows for solving problems of stochastic nature by adding a probabilistic component to simple 2-player GR(1) games. Further, we present an efficient approach for solving qualitative 21/2-player GR(1) games with polynomial-time complexity. Our approach is based on a reduction from 21/2-player GR(1) games to 2-player GR(1) games that allows for solving the game and constructing, from a sure winning strategy for player □ (resp. L) in a 2-player GR(1) game, an almost-sure (resp. positively) winning strategy for its corresponding 21/2-player GR(1) game. Key to the effectiveness of the proposed approach is the fact that the reduction generates a 2-player game that is linearly larger than the original 21/2-player game, more precisely, it is linear with respect to the number of probabilistic states in the 21/2-player GR(1) game. © 2016 IEEE.

Registro:

Documento: Conferencia
Título:21/2-player generalized reactivity (1) games
Autor:Rodriguez, N.; Braberman, V.; D'Ippolito, N.; Uchitel, S.
Filiación:Departamento de Computación, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Argentina
Department of Computing Imperial College, London, United Kingdom
Año:2016
Página de inicio:6996
Página de fin:7001
DOI: http://dx.doi.org/10.1109/CDC.2016.7799347
Título revista:55th IEEE Conference on Decision and Control, CDC 2016
Título revista abreviado:IEEE Conf. Decis. Control, CDC 2016
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_97815090_v_n_p6996_Rodriguez

Referencias:

  • Alur, R., La Torre, S., Deterministic generators and games for LTL fragments (2004) ACM Trans. Comput. Logic, 5 (1), pp. 1-25. , Jan
  • Bloem, R., Cimatti, A., Greimel, K., Hofferek, G., Könighofer, R., Roveri, M., Schuppan, V., Seeber, R., Ratsy-a new requirements analysis tool with synthesis (2010) Procs, 22Nd Int. Conf. on Comp. Aided Verif., pp. 425-429. , CAV'10, Springer-Verlag
  • Bloem, R., Jobstmann, B., Piterman, N., Pnueli, A., Saar, Y., Synthesis of reactive(1) designs (2012) J. Comput. Syst. Sci, 78 (3), pp. 911-938
  • Bloem, R.P., Galler, S., Jobstmann, B., Piterman, N., Pnueli, A., Weiglhofer, M., Interactive presentation: Automatic hardware synthesis from specifications: A case study (2007) 2007 Design, Automation and Test in Europe Conf. and Exposition April 16-20, Nice, France
  • Braberman, V., D'Ippolito, N., Piterman, N., Sykes, D., Uchitel, S., Controller synthesis: From modelling to enactment (2013) Procs, of the 2013 Int. Conf. on Soft. Eng., pp. 1347-1350. , ICSE '13, IEEE Press, Piscataway, NJ, USA
  • Chatterjee, K., De Alfaro, L., Henzinger, T.A., (2005) The Complexity of Stochastic Rabin and Streett Games, pp. 878-890. , Springer
  • Chatterjee, K., Henzinger, T.A., A survey of stochastic !-regular games (2012) J. Comput. Syst. Sci, 78 (2), pp. 394-413. , Mar
  • Chatterjee, K., Jurdzínski, M., Henzinger, T.A., (2003) Simple Stochastic Parity Games, pp. 100-113. , Springer Berlin Heidelberg
  • Chatterjee, K., Jurdzínski, M., Henzinger, T.A., Quanzatitative stochastic parity games. In: Procs, of the fifteenth annual acm-siam symp. on discrete algorithms (2004) SODA '04, Society for Industrial and Applied Mathematics, pp. 121-130. , Philadelphia, PA, USA
  • Condon, A., The complexity of stochastic games (1992) Inf. Comput., 96 (2), pp. 203-224. , Feb
  • Conner, D.C., Kress-Gazit, H., Choset, H., Rizzi, A.A., Pappas, G.J., Valet parking without a valet (2007) 2007 IEEE/RSJ Int. Conf. on Intelligent Robots and Systems, pp. 572-577. , October 29-November 2, 2007, San Diego, USA. IEEE
  • Courcoubetis, C., Yannakakis, M., The complexity of probabilistic verification (1995) J. ACM, 42 (4), pp. 857-907. , Jul
  • De Alfaro, L., (1998) Formal Verification of Probabilistic Systems, , Ph.D. Thesis, Stanford, CA, USA, aAI9837082
  • D'Ippolito, N., Braberman, V., Piterman, N., Uchitel, S., Synthesis of live behaviour models for fallible domains (2011) Procs, of the 33rd Int. Conf. on Soft. Eng., 11, pp. 211-220. , ICSE ACM, USA
  • D'Ippolito, N., Braberman, V., Piterman, N., Uchitel, S., Synthesizing nonanomalous event-based controllers for liveness goals (2013) ACM Trans. Softw. Eng. Methodol, 22 (1), pp. 91-936. , Mar
  • D'Ippolito, N., Fischbein, D., Chechik, M., Uchitel, S., MTSA: The modal transition system analyser (2008) Procs, of the 2008 23rd IEEE/ACM Int. Conf. on Automated Soft. Eng. ASE '08, IEEE Comp. Society, Washington, DC, USA
  • Etessami, K., Yannakakis, M., Efficient qualitative analysis of classes of recursive markov decision processes and simple stochastic games (2006) Procs, of the 23rd Annual Conf. on Theoret. Aspects of Comp. Sci., pp. 634-645. , STACS'06, Springer-Verlag, Berlin, Heidelberg
  • Etessami, K., Yannakakis, M., Recursive concurrent stochastic games (2006) Procs, 33rd Int. Conf. on Automata, Lang. and Program.-Part II., pp. 324-335. , ICALP'06, Springer-Verlag
  • Gimbert, H., Horn, F., Simple stochastic games with few random vertices are easy to solve (2008) Procs, 11th Int. Conf. on Foundations of Soft. Sci. and Computational Structures., pp. 5-19. , FOSSACS' 08/ETAPS'08, Springer-Verlag, Berlin, Heidelberg
  • Jackson, M., The world and the machine (1995) Procs, of the 17th Int. Conf. on Soft. Eng., pp. 283-292. , ICSE '95, ACM, USA
  • Jing, G., Finucane, C., Raman, V., Kress-Gazit, H., Correct high-level robot control from structured englishRobotics (2012) Robotics and Automation (ICRA), 2012 IEEE Int. Conf. On., pp. 3543-3544. , May
  • Jobstmann, B., Galler, S., Weiglhofer, M., Bloem, R., Anzu: A tool for property synthesis (2007) Procs, of the 19th Int. Conf. on Comp. Aided Verification., pp. 258-262. , CAV'07, Springer-Verlag, Berlin, Heidelberg
  • Jurdzinski, M., Kupferman, O., Henzinger, T.A., Trading probability for fairness (2002) Procs, of the 16th Int. Workshop and 11th Annual Conf. of the EACSL on Comp. Sci. Logic., pp. 292-305. , CSL '02, Springer-Verlag, London, UK, UK
  • Kress-Gazit, H., Fainekos, G.E., Pappas, G.J., From structured english to robot motion 2007 IEEE/RSJ Int. Conf. on Intelligent Robots and Systems., pp. 2717-2722. , Oct 2007
  • Kress-Gazit, H., Fainekos, G.E., Pappas, G.J., Where's waldo sensorbased temporal logic motion planning (2007) 2007 IEEE Int. Conf. on Robotics and Automation, ICRA 10-14, pp. 3116-3121. , April 2007, Roma, Italy.IEEE
  • Kugler, H., Plock, C., Pnueli, A., Controller synthesis from lsc requirementsprocs (2009) Procs, of the 12th Int. Conf. on Fundamental Approaches to Soft. Eng.: Held As Part of the Joint European Conferences on Theory and Practice of Soft., Etaps, pp. 79-93. , FASE '09, Springer-Verlag, Berlin, Heidelberg
  • Kugler, H., Segall, I., Compositional synthesis of reactive systems from live sequence chart specifications (2009) Procs, 15th Int. Conf. on Tools and Algorithms for the Const. and Anal. of Sys., ETAPS 2009, pp. 77-91. , TACAS '09, Springer-Verlag, Berlin, Heidelberg
  • Kumar, R., Garg, V., Control of stochastic discrete event systems modeled by probabilistic languages (2001) IEEE Transactions on Automatic Control, 46 (4), pp. 593-606
  • Li, Y., Lin, F., Lin, Z.H., Supervisory control of probabilistic discreteevent systems with recovery (1999) IEEE Transactions on Automatic Control, 44 (10), pp. 1971-1975. , Oct
  • Maler, O., Pnueli, A., Sifakis, J., (1995) On the Synthesis of Discrete Controllers for Timed Systems, pp. 229-242. , Springer Berlin
  • Markovski, J., Su, R., Towards optimal supervisory controller synthesis of stochastic nondeterministic discrete-event systems (2013) Procs, of the 52nd IEEE Conf. on Decision and Control, CDC 2013, pp. 7615-7620. , December 10-13, 2013, Firenze, Italy.IEEE
  • Martin, D.A., The determinacy of blackwell games (1998) The Journal of Symbolic Logic, 63 (4), pp. 1565-1581
  • Neider, D., Rabinovich, R., Zimmermann, M., (2014) Down the Borel Hierarchy. Theor. Comput. Sci, 560 (P3), pp. 219-234. , Dec
  • Pantelic, V., Lawford, M., Postma, S.M., A framework for supervisory control of probabilistic discrete event systemsystems (2014) 12th Int. Workshop on Discrete Event Systems, WODES 2014, pp. 477-484. , May 14-16 Lesage, J., Faure, J., Cury, J.E.R., Lennartson, B. (Eds.), Cachan, FranceInt. Federation of Automatic Control
  • Piterman, N., Pnueli, A., Sa'Ar, Y., Synthesis of reactive(1) designs. In: Procs, of the 7th Int. Confon Verif (2006) Model Checking, and Abstract Interpretation., pp. 364-380. , VMCAI'06, Springer-Verlag
  • Pnueli, A., Rosner, R., On the synthesis of a reactive module (1989) Procs, of the 16th ACM SIGPLAN-SIGACT Symp. on Principles of Programming Languages., pp. 179-190. , POPL '89, ACM, USA
  • Pnueli, A., The temporal logic of programs (1977) Procs, of the 18th Annual Symp. on Foundations of Comp. Sci., pp. 46-57. , SFCS '77, IEEE Comp. Society, Washington, DC, USA
  • Pnueli, A., Sa'Ar, Y., Zuck, L.D., Jtlv A framework for developing verification algorithms (2010) Procs, of the 22Nd Int. Conf. on Comp. Aided Verification. CAV'10, , Springer-Verlag, Berlin, Heidelberg
  • Tripathi, R., Valkanova, E., Kumar, On strategy improvement algorithms for simple stochastic games (2010) Procs. of the 7th Int. Conf. on Algorithms and Complexity. CIAC'10, , Springer-Verlag S A.V
  • Wongpiromsarn, T., Topcu, U., Murray, R.M., Automatic synthesis of robust embedded control soft (2010) Embedded Reasoning, Papers from the 2010 AAAI Spring Symp., Technical Report SS-10-04, Stanford, California, USA, pp. 22-24. , March 2010. AAAI
  • Zielonka, W., Infinite games on finitely coloured graphs with applications to automata on infinite trees (1998) Theoret. Comp. Sci, 200 (1), pp. 135-183A4 -

Citas:

---------- APA ----------
Rodriguez, N., Braberman, V., D'Ippolito, N. & Uchitel, S. (2016) . 21/2-player generalized reactivity (1) games. 55th IEEE Conference on Decision and Control, CDC 2016, 6996-7001.
http://dx.doi.org/10.1109/CDC.2016.7799347
---------- CHICAGO ----------
Rodriguez, N., Braberman, V., D'Ippolito, N., Uchitel, S. "21/2-player generalized reactivity (1) games" . 55th IEEE Conference on Decision and Control, CDC 2016 (2016) : 6996-7001.
http://dx.doi.org/10.1109/CDC.2016.7799347
---------- MLA ----------
Rodriguez, N., Braberman, V., D'Ippolito, N., Uchitel, S. "21/2-player generalized reactivity (1) games" . 55th IEEE Conference on Decision and Control, CDC 2016, 2016, pp. 6996-7001.
http://dx.doi.org/10.1109/CDC.2016.7799347
---------- VANCOUVER ----------
Rodriguez, N., Braberman, V., D'Ippolito, N., Uchitel, S. 21/2-player generalized reactivity (1) games. IEEE Conf. Decis. Control, CDC 2016. 2016:6996-7001.
http://dx.doi.org/10.1109/CDC.2016.7799347