In this paper, we show how Ehrenfeucht-Fraïssé games can be successfully exploited to compare (finite) strings. More precisely, we give necessary and sufficient conditions for Spoiler/Duplicator to win games played on finite structures with a limited order relation, that lies in between the successor relation and the usual (linear) order relation, and a finite number of unary predicates. On the basis of such conditions, we outline a polynomial (in the size of the input strings) algorithm to compute the "remoteness" of a game and to determine the optimal strategies/moves for both players.

Games on Strings with a Limited Order Relation

DE MARIA, Elisabetta;MONTANARI, Angelo;VITACOLONNA, Nicola
2009-01-01

Abstract

In this paper, we show how Ehrenfeucht-Fraïssé games can be successfully exploited to compare (finite) strings. More precisely, we give necessary and sufficient conditions for Spoiler/Duplicator to win games played on finite structures with a limited order relation, that lies in between the successor relation and the usual (linear) order relation, and a finite number of unary predicates. On the basis of such conditions, we outline a polynomial (in the size of the input strings) algorithm to compute the "remoteness" of a game and to determine the optimal strategies/moves for both players.
9783540926863
File in questo prodotto:
File Dimensione Formato  
54070164.pdf

non disponibili

Tipologia: Documento in Pre-print
Licenza: Non pubblico
Dimensione 621.42 kB
Formato Adobe PDF
621.42 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11390/881575
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? ND
social impact