08/07/2020

Good-for-games ω-Pushdown Automata

Karoliina Lehtinen and Martin Zimmermann

Keywords: Good-for-games Automata, Pushdown Automata, Infinite Games, Contextfree languages

Abstract Paper Similar Papers

Abstract: We introduce good-for-games ω-pushdown automata (ω-GFG-PDA). These are automata whose nondeterminism can be resolved based on the run constructed thus far. Good-for-gameness enables automata to be composed with games, trees, and other automata, applications which otherwise require deterministic automata. Our main results are that ω-GFG-PDA are more expressive than deterministic ω-pushdown automata and that solving infinite games with winning conditions specified by ω-GFG-PDA is EXPTIME-complete. Thus, we have identified a new class of ω-contextfree winning conditions for which solving games is decidable. It follows that the universality problem for ω-GFG-PDA is in EXPTIME as well. Moreover, we study closure properties of the class of languages recognized by ω-GFG-PDA and decidability of good-for-gameness of ω-pushdown automata and languages.

 0
 0
 0
 0
  Share    
This is an embedded video. Talk and the respective paper are published at ICALP 2020 virtual conference. If you are one of the authors of the paper and want to manage your upload, see the question "My papertalk has been externally embedded..." in the FAQ section.

Comments

Post Comment
no comments yet
code of conduct: tbd Characters remaining: 140

Similar Papers

 0
 0
 0
 0
 14:40 
 0
 0
 0
 0
 15:16 
 0
 0
 0
 0
 17:43 
 0
 0
 0
 0
 15:01 
 0
 0
 0
 0
 11:52 
 0
 0
 0
 0
 16:16 
 0
 0
 0
 0
 14:22 
 0
 0
 0
 0
 14:28 
 0
 0
 0
 0
 18:07 
 1
 0
 0
 0
 14:01 
 0
 0
 0
 0
 5:36 
 0
 0
 0
 0
 17:09 
 0
 0
 0
 0
 14:59 
 0
 0
 0
 0
 5:20 
 1
 1
 0
 0
 3:29 
 0
 0
 0
 0
 15:21 
 0
 0
 0
 0
 15:35 
 0
 0
 0
 0
 5:12 
 0
 0
 0
 0
 17:06 
 0
 0
 0
 0
 23:42 
 0
 0
 0
 0
 15:52 
 0
 0
 0
 0
 15:13 
 0
 0
 0
 0
 15:05 
 0
 0
 0
 0
 4:49 
 0
 0
 0
 0
 25:15 
 0
 0
 0
 0
 15:00 
 0
 0
 0
 0
 14:11 
 0
 0
 0
 0
 4:49 
 0
 0
 0
 0
 18:49 
 0
 0
 0
 0
 17:04 
 0
 0
 0
 0
 14:29 
 0
 0
 0
 0
 16:33 
 0
 0
 0
 0
 13:57 
 0
 0
 0
 0
 16:35 
 0
 0
 0
 0
 14:51 
 0
 0
 0
 0
 3:26 
 0
 0
 0
 0
 20:14 
 0
 0
 0
 0
 17:38 
 0
 0
 0
 0
 18:18 
 0
 0
 0
 0
 16:33