Winning strategies for streaming rewriting games
Context-free games on strings are two-player rewriting games based on a set of production rules and a regular target language. In each round, the first player selects a position of the current string; then the second player replaces the symbol at that position according to one of the production rule...
| Main Authors: | , , |
|---|---|
| Format: | Conference item |
| Language: | English |
| Published: |
Springer
2019
|
| _version_ | 1826309546327408640 |
|---|---|
| author | Coester, Christian Schwentick, T Schuster, M |
| author_facet | Coester, Christian Schwentick, T Schuster, M |
| author_sort | Coester, Christian |
| collection | OXFORD |
| description | Context-free games on strings are two-player rewriting games based on a set of production rules and a regular target language. In each round, the first player selects a position of the current string; then the second player replaces the symbol at that position according to one of the production rules. The first player wins as soon as the current string belongs to the target language. In this paper the one-pass setting for context-free games is studied, where the knowledge of the first player is incomplete: She selects positions in a left-to-right fashion and only sees the current symbol and the symbols from previous rounds. The paper studies conditions under which dominant and undominated strategies exist for the first player, and when they can be chosen from restricted types of strategies that can be computed efficiently. |
| first_indexed | 2024-03-07T07:37:20Z |
| format | Conference item |
| id | oxford-uuid:09991532-12fb-4989-b5b0-17b39dd00461 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T07:37:20Z |
| publishDate | 2019 |
| publisher | Springer |
| record_format | dspace |
| spelling | oxford-uuid:09991532-12fb-4989-b5b0-17b39dd004612023-03-30T15:05:40ZWinning strategies for streaming rewriting gamesConference itemhttp://purl.org/coar/resource_type/c_5794uuid:09991532-12fb-4989-b5b0-17b39dd00461EnglishSymplectic ElementsSpringer2019Coester, ChristianSchwentick, TSchuster, MContext-free games on strings are two-player rewriting games based on a set of production rules and a regular target language. In each round, the first player selects a position of the current string; then the second player replaces the symbol at that position according to one of the production rules. The first player wins as soon as the current string belongs to the target language. In this paper the one-pass setting for context-free games is studied, where the knowledge of the first player is incomplete: She selects positions in a left-to-right fashion and only sees the current symbol and the symbols from previous rounds. The paper studies conditions under which dominant and undominated strategies exist for the first player, and when they can be chosen from restricted types of strategies that can be computed efficiently. |
| spellingShingle | Coester, Christian Schwentick, T Schuster, M Winning strategies for streaming rewriting games |
| title | Winning strategies for streaming rewriting games |
| title_full | Winning strategies for streaming rewriting games |
| title_fullStr | Winning strategies for streaming rewriting games |
| title_full_unstemmed | Winning strategies for streaming rewriting games |
| title_short | Winning strategies for streaming rewriting games |
| title_sort | winning strategies for streaming rewriting games |
| work_keys_str_mv | AT coesterchristian winningstrategiesforstreamingrewritinggames AT schwentickt winningstrategiesforstreamingrewritinggames AT schusterm winningstrategiesforstreamingrewritinggames |