Half positionality is the property of a language of infinite words to admit positional winning strategies, when interpreted as the goal of a two-player game on a graph. Such problem applies to the automatic synthesis of controllers, where positional strategies represent efficient controllers. As our main result, we describe a novel sufficient condition for half positionality, more general than what was previously known. Moreover, we compare our proposed condition with several others, proposed in the recent literature, outlining an intricate network of relationships, where only few combinations are sufficient for half positionality.
Exploring the Boundary of Half Positionality / Bianco, Alessandro; Faella, Marco; Mogavero, Fabio; Murano, Aniello. - STAMPA. - 6245:(2010), pp. 171-185. (Intervento presentato al convegno 11th International Workshop on Computational Logic in Multi-Agent Systems, CLIMA-XI 2010 tenutosi a Lisbona, Portogallo nel Agosto, 2010) [10.1007/978-3-642-14977-1_14].
Exploring the Boundary of Half Positionality
BIANCO, ALESSANDRO;FAELLA, MARCO;MOGAVERO, FABIO;MURANO, ANIELLO
2010
Abstract
Half positionality is the property of a language of infinite words to admit positional winning strategies, when interpreted as the goal of a two-player game on a graph. Such problem applies to the automatic synthesis of controllers, where positional strategies represent efficient controllers. As our main result, we describe a novel sufficient condition for half positionality, more general than what was previously known. Moreover, we compare our proposed condition with several others, proposed in the recent literature, outlining an intricate network of relationships, where only few combinations are sufficient for half positionality.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
