About: Regularity in PDA Games Revisited

Facets (new session)
Description
Metadata
Settings
- owl:sameAs
- Inference Rule:

About: Regularity in PDA Games Revisited Goto Sponge NotDistinct Permalink

An Entity of Type : http://linked.opendata.cz/ontology/domain/vavai/Vysledek, within Data Space : linked.opendata.cz associated with source document(s)

Attributes	Values
rdf:type	skos:Concept http://linked.opendata.cz/ontology/domain/vavai/Vysledek
Description	We study the regularity of sets of winning configurations in countable-state stochastic games played on transition graphs of pushdown automata (PDA games) with reachability objectives. Our main result is proving the regularity of the sets of winning configurations for qualitative reachability objectives. This completes the classification partially given in a previous paper on this topic. We also improve the upper bounds on the regular representation in cases already solved. We further mention a problem which has also been studied recently: determining the \emph{value} of a reachability game. Using our methods we prove the regularity of the set of configurations with value 1 and 0. Our work is related to recent results for stochastic games on countable graphs and sheds more light on some open problems in this area. We study the regularity of sets of winning configurations in countable-state stochastic games played on transition graphs of pushdown automata (PDA games) with reachability objectives. Our main result is proving the regularity of the sets of winning configurations for qualitative reachability objectives. This completes the classification partially given in a previous paper on this topic. We also improve the upper bounds on the regular representation in cases already solved. We further mention a problem which has also been studied recently: determining the \emph{value} of a reachability game. Using our methods we prove the regularity of the set of configurations with value 1 and 0. Our work is related to recent results for stochastic games on countable graphs and sheds more light on some open problems in this area. (en)
Title	Regularity in PDA Games Revisited Regularity in PDA Games Revisited (en)
skos:prefLabel	Regularity in PDA Games Revisited Regularity in PDA Games Revisited (en)
skos:notation	RIV/00216224:14330/08:00026782!RIV10-MSM-14330___
http://linked.open...avai/riv/aktivita	P Z
http://linked.open...avai/riv/aktivity	P(1M0545), Z(MSM0021622419)
http://linked.open...vai/riv/dodaniDat	2010
http://linked.open...aciTvurceVysledku	Brožek, Václav
http://linked.open.../riv/druhVysledku	D - Článek ve sborníku
http://linked.open...iv/duvernostUdaju	S - Úplné a pravdivé údaje nepodléhající ochraně podle zvláštních právních předpisů
http://linked.open...titaPredkladatele	Masarykova univerzita / Fakulta informatiky
http://linked.open...dnocenehoVysledku	392050
http://linked.open...ai/riv/idVysledku	RIV/00216224:14330/08:00026782
http://linked.open...riv/jazykVysledku	eng - angličtina
http://linked.open.../riv/klicovaSlova	regular languages; probabilistic pushdown games; reachability (en)
http://linked.open.../riv/klicoveSlovo	regular languages reachability probabilistic pushdown games
http://linked.open...ontrolniKodProRIV	[75EF34179014]
http://linked.open...v/mistoKonaniAkce	Znojmo
http://linked.open...i/riv/mistoVydani	Brno
http://linked.open...i/riv/nazevZdroje	MEMICS 2008 proceedings
http://linked.open...in/vavai/riv/obor	IN
http://linked.open...ichTvurcuVysledku	1 (xsd:int)
http://linked.open...cetTvurcuVysledku	1 (xsd:int)
http://linked.open...vavai/riv/projekt	Institute for Theoretical Computer Science
http://linked.open...UplatneniVysledku	2008
http://linked.open...iv/tvurceVysledku	Brožek, Václav
http://linked.open...vavai/riv/typAkce	WRD - Světová
http://linked.open.../riv/zahajeniAkce	2008-01-01 (xsd:date)
http://linked.open...n/vavai/riv/zamer	Highly Parallel and Distributed Computing Systems
number of pages	8 (xsd:int)
http://purl.org/ne...btex#hasPublisher	L. Matyska, D. Antoš, M. Češka, Z. Kotásek, T. Vojnar, M. Křetínský (Eds.)
https://schema.org/isbn	978-80-7355-082-0
http://localhost/t...ganizacniJednotka	14330

Faceted Search & Find service v1.16.118 as of Jun 21 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3240 as of Jun 21 2024, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (126 GB total memory, 47 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software