Active Context-Free Games - Laboratoire d'Informatique Algorithmique, Fondements et Applications Access content directly
Journal Articles Theory of Computing Systems Year : 2006

Active Context-Free Games

Abstract

An Active Context-Free Game is a game with two players (Romeo and Juliet) on strings over a finite alphabet. In each move, Juliet selects a position of the current word and Romeo rewrites the corresponding letter according to a rule of a context-free grammar. Juliet wins if a string of the regular target language is reached. The complexity of deciding the existence of winning strategies for Juliet is investigated, depending on properties of the grammar, of the target language, and on restrictions on the strategy.

Domains

Other [cs.OH]
Fichier principal
Vignette du fichier
journal (1).pdf (393.97 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-00306333 , version 1 (10-05-2022)

Identifiers

  • HAL Id : hal-00306333 , version 1

Cite

Anca Muscholl, Thomas Schwentick, Luc Segoufin. Active Context-Free Games. Theory of Computing Systems, 2006, 39 (1), pp.237--276. ⟨hal-00306333⟩
130 View
32 Download

Share

Gmail Facebook X LinkedIn More