{"id":{"repo_id":"aachen","oai_identifier":"oai:publications.rwth-aachen.de:52085"},"canonical_url":"https://search.dev.ndltd.org/etd/aachen/oai:publications.rwth-aachen.de:52085","repository":{"repo_id":"aachen","name":"RWTH Aachen University","base_url":"https://publications.rwth-aachen.de/oai2d"},"display":{"title":"Games on pushdown graphs and extensions","abstract":"Two player games are a standard model of reactive computation, where e.g. one player is the controller and the other is the environment. A game is won by a player if she has a winning strategy, ie, if she can win every play. Given a finite description of the game, our aim is to compute the winner and a winning strategy. For finite graphs these problems have been solved for a long time, although some complexity questions remain open. We consider several classes of infinite graphs, from transition graphs of pushdown automata up to graphs of the Caucal hierarchy, and we investigate different winning conditions: reachability, recurrence (Büchi), parity, and the a called Sigma_3-condition. Two kinds of techniques are developed: a symbolic approach based on finite automata recognizing infinite sets of configurations and a game simulation which reduces a given game into a simpler one and solves it. Different kinds of strategies are also constructed: either positional or based on pushdown stack memories.","abstract_html":"Two player games are a standard model of reactive computation, where e.g. one player is the controller and the other is the environment. A game is won by a player if she has a winning strategy, ie, if she can win every play. Given a finite description of the game, our aim is to compute the winner and a winning strategy. For finite graphs these problems have been solved for a long time, although some complexity questions remain open. We consider several classes of infinite graphs, from transition graphs of pushdown automata up to graphs of the Caucal hierarchy, and we investigate different winning conditions: reachability, recurrence (Büchi), parity, and the a called Sigma_3-condition. Two kinds of techniques are developed: a symbolic approach based on finite automata recognizing infinite sets of configurations and a game simulation which reduces a given game into a simpler one and solves it. Different kinds of strategies are also constructed: either positional or based on pushdown stack memories.","abstract_has_math":false,"creators":["Cachat, Thierry"],"institution":"Publikationsserver der RWTH Aachen University","degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":["Thomas, Wolfgang"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2003,"date_issued":"2003","date_published":"2003","updated_at":"2026-07-30T19:40:50Z","subjects":["info:eu-repo/classification/ddc/004","Zweipersonen-Nullsummenspiel","Unendliches Spiel","Unendlicher Graph","Berechnungskomplexität","Endlicher Automat","Informatik","infinite games","verification","pushdown graph"],"languages":["eng"],"rights":["info:eu-repo/semantics/openAccess"],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["https://publications.rwth-aachen.de/search?p=id:%22RWTH-CONV-114327%22"],"render_values":[{"text":"https://publications.rwth-aachen.de/search?p=id:%22RWTH-CONV-114327%22","href":"https://publications.rwth-aachen.de/search?p=id:%22RWTH-CONV-114327%22","code":true}]}]},"links":{"outbound_url":"https://publications.rwth-aachen.de/record/52085","outbound_label":"Repository record","outbound_source":"dc:identifier"},"source_record":{"url":"https://publications.rwth-aachen.de/oai2d?verb=GetRecord&metadataPrefix=oai_dc&identifier=oai%3Apublications.rwth-aachen.de%3A52085","prefix":"oai_dc"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Thomas, Wolfgang"]},{"key":"dc:creator","label":"Author","values":["Cachat, Thierry"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:coverage","label":"Dc Coverage","values":["DE"]},{"key":"dc:date","label":"Dc Date","values":["2003"]},{"key":"dc:publisher","label":"Institution","values":["Publikationsserver der RWTH Aachen University"]},{"key":"dc:relation","label":"Dc Relation","values":["info:eu-repo/semantics/altIdentifier/doi/10.18154/RWTH-CONV-114327","info:eu-repo/semantics/altIdentifier/urn/urn:nbn:de:hbz:82-opus-9576"]},{"key":"dc:type","label":"Dc Type","values":["info:eu-repo/semantics/doctoralThesis","info:eu-repo/semantics/publishedVersion"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["info:eu-repo/classification/ddc/004","Zweipersonen-Nullsummenspiel","Unendliches Spiel","Unendlicher Graph","Berechnungskomplexität","Endlicher Automat","Informatik","infinite games","verification","pushdown graph"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["info:eu-repo/semantics/openAccess"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://publications.rwth-aachen.de/record/52085","https://publications.rwth-aachen.de/search?p=id:%22RWTH-CONV-114327%22"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Two player games are a standard model of reactive computation, where e.g. one player is the controller and the other is the environment. A game is won by a player if she has a winning strategy, ie, if she can win every play. Given a finite description of the game, our aim is to compute the winner and a winning strategy. For finite graphs these problems have been solved for a long time, although some complexity questions remain open. We consider several classes of infinite graphs, from transition graphs of pushdown automata up to graphs of the Caucal hierarchy, and we investigate different winning conditions: reachability, recurrence (Büchi), parity, and the a called Sigma_3-condition. Two kinds of techniques are developed: a symbolic approach based on finite automata recognizing infinite sets of configurations and a game simulation which reduces a given game into a simpler one and solves it. Different kinds of strategies are also constructed: either positional or based on pushdown stack memories."]},{"key":"dc:source","label":"Dc Source","values":["Aachen : Publikationsserver der RWTH Aachen University X, 147 S. : graph. Darst. (2003). doi:10.18154/RWTH-CONV-114327 = Aachen, Techn. Hochsch., Diss., 2003"]},{"key":"dc:title","label":"Title","values":["Games on pushdown graphs and extensions"]}]}],"canonical_facts":{"dc:contributor":["Thomas, Wolfgang"],"dc:coverage":["DE"],"dc:creator":["Cachat, Thierry"],"dc:date":["2003"],"dc:description":["Two player games are a standard model of reactive computation, where e.g. one player is the controller and the other is the environment. A game is won by a player if she has a winning strategy, ie, if she can win every play. Given a finite description of the game, our aim is to compute the winner and a winning strategy. For finite graphs these problems have been solved for a long time, although some complexity questions remain open. We consider several classes of infinite graphs, from transition graphs of pushdown automata up to graphs of the Caucal hierarchy, and we investigate different winning conditions: reachability, recurrence (Büchi), parity, and the a called Sigma_3-condition. Two kinds of techniques are developed: a symbolic approach based on finite automata recognizing infinite sets of configurations and a game simulation which reduces a given game into a simpler one and solves it. Different kinds of strategies are also constructed: either positional or based on pushdown stack memories."],"dc:identifier":["https://publications.rwth-aachen.de/record/52085","https://publications.rwth-aachen.de/search?p=id:%22RWTH-CONV-114327%22"],"dc:language":["eng"],"dc:publisher":["Publikationsserver der RWTH Aachen University"],"dc:relation":["info:eu-repo/semantics/altIdentifier/doi/10.18154/RWTH-CONV-114327","info:eu-repo/semantics/altIdentifier/urn/urn:nbn:de:hbz:82-opus-9576"],"dc:rights":["info:eu-repo/semantics/openAccess"],"dc:source":["Aachen : Publikationsserver der RWTH Aachen University X, 147 S. : graph. Darst. (2003). doi:10.18154/RWTH-CONV-114327 = Aachen, Techn. Hochsch., Diss., 2003"],"dc:subject":["info:eu-repo/classification/ddc/004","Zweipersonen-Nullsummenspiel","Unendliches Spiel","Unendlicher Graph","Berechnungskomplexität","Endlicher Automat","Informatik","infinite games","verification","pushdown graph"],"dc:title":["Games on pushdown graphs and extensions"],"dc:type":["info:eu-repo/semantics/doctoralThesis","info:eu-repo/semantics/publishedVersion"]},"updated_at":"2026-07-30T19:40:50Z"}