Ontology type: schema:Chapter Open Access: True
2014
AUTHORS ABSTRACTWe show that positional winning strategies in pushdown reachability games can be implemented by deterministic finite state automata of exponential size. Such automata read the stack and control state of a given pushdown configuration and output the set of winning moves playable from that position. This result can originally be attributed to Kupferman, Piterman and Vardi using an approach based on two-way tree automata. We present a more direct approach that builds upon the popular saturation technique. Saturation for analysing pushdown systems has been successfully implemented by Moped and WALi. Thus, our approach has the potential for practical applications to controller-synthesis problems. More... »
PAGES58-71
Reachability Problems
ISBN
978-3-319-11438-5
978-3-319-11439-2
http://scigraph.springernature.com/pub.10.1007/978-3-319-11439-2_5
DOIhttp://dx.doi.org/10.1007/978-3-319-11439-2_5
DIMENSIONShttps://app.dimensions.ai/details/publication/pub.1041180584
JSON-LD is the canonical representation for SciGraph data.
TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT
[
{
"@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json",
"about": [
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0102",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Applied Mathematics",
"type": "DefinedTerm"
},
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Mathematical Sciences",
"type": "DefinedTerm"
}
],
"author": [
{
"affiliation": {
"alternateName": "Laboratoire d'Informatique Gaspard-Monge",
"id": "https://www.grid.ac/institutes/grid.462940.d",
"name": [
"LIGM, Universit\u00e9 Paris-Est & CNRS, France"
],
"type": "Organization"
},
"familyName": "Carayol",
"givenName": "A.",
"id": "sg:person.013525060217.03",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013525060217.03"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Laboratoire d'Informatique Gaspard-Monge",
"id": "https://www.grid.ac/institutes/grid.462940.d",
"name": [
"LIGM, Universit\u00e9 Paris-Est & CNRS, France"
],
"type": "Organization"
},
"familyName": "Hague",
"givenName": "M.",
"id": "sg:person.016660553175.13",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016660553175.13"
],
"type": "Person"
}
],
"citation": [
{
"id": "sg:pub.10.1007/978-3-540-73368-3_19",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1004333980",
"https://doi.org/10.1007/978-3-540-73368-3_19"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-540-73368-3_19",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1004333980",
"https://doi.org/10.1007/978-3-540-73368-3_19"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/s0020-0190(02)00445-3",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1006664702"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/s0020-0190(02)00445-3",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1006664702"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/3-540-63141-0_10",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1010116324",
"https://doi.org/10.1007/3-540-63141-0_10"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-540-31980-1_35",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1010847598",
"https://doi.org/10.1007/978-3-540-31980-1_35"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-540-31980-1_35",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1010847598",
"https://doi.org/10.1007/978-3-540-31980-1_35"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/s1571-0661(05)80426-8",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1013019919"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1145/1965724.1965743",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1013619846"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/11901914_13",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1020025047",
"https://doi.org/10.1007/11901914_13"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/11901914_13",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1020025047",
"https://doi.org/10.1007/11901914_13"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/10722468_7",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1022478436",
"https://doi.org/10.1007/10722468_7"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/10722468_7",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1022478436",
"https://doi.org/10.1007/10722468_7"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1145/322003.322016",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1025248688"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-540-27813-9_30",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1029403862",
"https://doi.org/10.1007/978-3-540-27813-9_30"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-540-27813-9_30",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1029403862",
"https://doi.org/10.1007/978-3-540-27813-9_30"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/3-540-44585-4_30",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1035132527",
"https://doi.org/10.1007/3-540-44585-4_30"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-642-04081-8_26",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1036262322",
"https://doi.org/10.1007/978-3-642-04081-8_26"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/3-540-45465-9_60",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1044531535",
"https://doi.org/10.1007/3-540-45465-9_60"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1006/inco.2000.2894",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1046428528"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-642-13754-9_11",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1047560029",
"https://doi.org/10.1007/978-3-642-13754-9_11"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-642-13754-9_11",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1047560029",
"https://doi.org/10.1007/978-3-642-13754-9_11"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/s0304-3975(98)00009-7",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1051504708"
],
"type": "CreativeWork"
}
],
"datePublished": "2014",
"datePublishedReg": "2014-01-01",
"description": "We show that positional winning strategies in pushdown reachability games can be implemented by deterministic finite state automata of exponential size. Such automata read the stack and control state of a given pushdown configuration and output the set of winning moves playable from that position. This result can originally be attributed to Kupferman, Piterman and Vardi using an approach based on two-way tree automata. We present a more direct approach that builds upon the popular saturation technique. Saturation for analysing pushdown systems has been successfully implemented by Moped and WALi. Thus, our approach has the potential for practical applications to controller-synthesis problems.",
"editor": [
{
"familyName": "Ouaknine",
"givenName": "Jo\u00ebl",
"type": "Person"
},
{
"familyName": "Potapov",
"givenName": "Igor",
"type": "Person"
},
{
"familyName": "Worrell",
"givenName": "James",
"type": "Person"
}
],
"genre": "chapter",
"id": "sg:pub.10.1007/978-3-319-11439-2_5",
"inLanguage": [
"en"
],
"isAccessibleForFree": true,
"isPartOf": {
"isbn": [
"978-3-319-11438-5",
"978-3-319-11439-2"
],
"name": "Reachability Problems",
"type": "Book"
},
"name": "Regular Strategies in Pushdown Reachability Games",
"pagination": "58-71",
"productId": [
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/978-3-319-11439-2_5"
]
},
{
"name": "readcube_id",
"type": "PropertyValue",
"value": [
"c42bff1e9c71d84de5b51bd43fa37691f97c9322bf9ca1d42a7b1c01e23636bc"
]
},
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1041180584"
]
}
],
"publisher": {
"location": "Cham",
"name": "Springer International Publishing",
"type": "Organisation"
},
"sameAs": [
"https://doi.org/10.1007/978-3-319-11439-2_5",
"https://app.dimensions.ai/details/publication/pub.1041180584"
],
"sdDataset": "chapters",
"sdDatePublished": "2019-04-15T19:43",
"sdLicense": "https://scigraph.springernature.com/explorer/license/",
"sdPublisher": {
"name": "Springer Nature - SN SciGraph project",
"type": "Organization"
},
"sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000001_0000000264/records_8684_00000561.jsonl",
"type": "Chapter",
"url": "http://link.springer.com/10.1007/978-3-319-11439-2_5"
}
]Download the RDF metadata as: json-ld nt turtle xml License info
JSON-LD is a popular format for linked data which is fully compatible with JSON.
curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-11439-2_5'
N-Triples is a line-based linked data format ideal for batch operations.
curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-11439-2_5'
Turtle is a human-readable linked data format.
curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-11439-2_5'
RDF/XML is a standard XML format for linked data.
curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-11439-2_5'
This table displays all metadata directly associated to this object as RDF triples.
140 TRIPLES
23 PREDICATES
43 URIs
20 LITERALS
8 BLANK NODES