Ricerc@Sapienza

Information Extraction (IE) is the task of automatically organizing in a structured form data extracted from free text documents. In several contexts, it is often desirable that extracted data are then organized according to an ontology, which provides a formal and conceptual representation of the domain of interest. Ontologies allow for a better data interpretation, as well as for their semantic integration with other information, as in Ontology-based Data Access (OBDA), a popular declarative framework for data management where an ontology is connected to a data layer through mappings.

Recently, due to the widespread diffusion of smart-phones, mobile puzzle games have experienced a huge increase in their popularity. A successful puzzle has to be both captivating and challenging, and it has been suggested that these features are somehow related to their computational complexity [6]. Indeed, many puzzle games – such as Mah-Jongg, Sokoban, Candy Crush, and 2048, to name a few – are known to be NP-hard [3,4,8,12]. In this paper we consider Trainyard: a popular mobile puzzle game whose goal is to get colored trains from their initial stations to suitable destination stations.

Undirected Vertex Geography (UVG) is an impartial two-person game played on a (undirected) graph G with a specified vertex u. Players, Alice and Bob, alternately choose a vertex that has not been chosen before and that is adjacent to the last chosen vertex. Alice plays first, choosing an adjacent vertex of u. The first player who is unable to choose a vertex loses. Determining whether Alice has a winning strategy in this game (the UVG problem) is known to be solvable in polynomial time.