Ontology type: schema:Chapter Open Access: True
2012
AUTHORSChris Broadbent , Arnaud Carayol , Matthew Hague , Olivier Serre
ABSTRACTWe introduce a natural extension of collapsible pushdown systems called annotated pushdown systems that replaces collapse links with stack annotations. We believe this new model has many advantages. We present a saturation method for global backwards reachability analysis of these models that can also be used to analyse collapsible pushdown systems. Beginning with an automaton representing a set of configurations, we build an automaton accepting all configurations that can reach this set. We also improve upon previous saturation techniques for higher-order pushdown systems by significantly reducing the size of the automaton constructed and simplifying the algorithm and proofs. More... »
PAGES165-176
Automata, Languages, and Programming
ISBN
978-3-642-31584-8
978-3-642-31585-5
http://scigraph.springernature.com/pub.10.1007/978-3-642-31585-5_18
DOIhttp://dx.doi.org/10.1007/978-3-642-31585-5_18
DIMENSIONShttps://app.dimensions.ai/details/publication/pub.1029869669
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/0801",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Artificial Intelligence and Image Processing",
"type": "DefinedTerm"
},
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Information and Computing Sciences",
"type": "DefinedTerm"
}
],
"author": [
{
"affiliation": {
"alternateName": "Laboratoire d'Informatique Algorithmique: Fondements et Applications",
"id": "https://www.grid.ac/institutes/grid.462842.e",
"name": [
"LIAFA, Universit\u00e9 Paris Diderot \u2013 Paris 7 & CNRS, France"
],
"type": "Organization"
},
"familyName": "Broadbent",
"givenName": "Chris",
"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": "Carayol",
"givenName": "Arnaud",
"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 Algorithmique: Fondements et Applications",
"id": "https://www.grid.ac/institutes/grid.462842.e",
"name": [
"LIAFA, Universit\u00e9 Paris Diderot \u2013 Paris 7 & CNRS, France"
],
"type": "Organization"
},
"familyName": "Hague",
"givenName": "Matthew",
"id": "sg:person.016660553175.13",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016660553175.13"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Laboratoire d'Informatique Algorithmique: Fondements et Applications",
"id": "https://www.grid.ac/institutes/grid.462842.e",
"name": [
"LIAFA, Universit\u00e9 Paris Diderot \u2013 Paris 7 & CNRS, France"
],
"type": "Organization"
},
"familyName": "Serre",
"givenName": "Olivier",
"id": "sg:person.012501632212.04",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012501632212.04"
],
"type": "Person"
}
],
"citation": [
{
"id": "https://doi.org/10.1016/0304-3975(82)90009-3",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1003269055"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/10722167_20",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1005270786",
"https://doi.org/10.1007/10722167_20"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/10722167_20",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1005270786",
"https://doi.org/10.1007/10722167_20"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-642-04420-5_19",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1009168920",
"https://doi.org/10.1007/978-3-642-04420-5_19"
],
"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-642-19805-2_18",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1012560765",
"https://doi.org/10.1007/978-3-642-19805-2_18"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-642-19805-2_18",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1012560765",
"https://doi.org/10.1007/978-3-642-19805-2_18"
],
"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.1016/j.scico.2005.02.009",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1014742386"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/j.scico.2005.02.009",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1014742386"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-540-30538-5_12",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1016246348",
"https://doi.org/10.1007/978-3-540-30538-5_12"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-540-30538-5_12",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1016246348",
"https://doi.org/10.1007/978-3-540-30538-5_12"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/j.ic.2010.12.004",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1018707872"
],
"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": "https://doi.org/10.1145/322234.322243",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1021206590"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/11523468_117",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1030050029",
"https://doi.org/10.1007/11523468_117"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/11523468_117",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1030050029",
"https://doi.org/10.1007/11523468_117"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/3-540-45931-6_15",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1034404222",
"https://doi.org/10.1007/3-540-45931-6_15"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-642-16164-3_14",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1034942019",
"https://doi.org/10.1007/978-3-642-16164-3_14"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-642-16164-3_14",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1034942019",
"https://doi.org/10.1007/978-3-642-16164-3_14"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-642-32589-2_50",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1041573106",
"https://doi.org/10.1007/978-3-642-32589-2_50"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-540-85114-1_19",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1042310044",
"https://doi.org/10.1007/978-3-540-85114-1_19"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-642-22012-8_12",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1043315929",
"https://doi.org/10.1007/978-3-642-22012-8_12"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-642-22012-8_12",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1043315929",
"https://doi.org/10.1007/978-3-642-22012-8_12"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/11549345_16",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1043318960",
"https://doi.org/10.1007/11549345_16"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/11549345_16",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1043318960",
"https://doi.org/10.1007/11549345_16"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/11549345_16",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1043318960",
"https://doi.org/10.1007/11549345_16"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-540-71389-0_16",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1044061119",
"https://doi.org/10.1007/978-3-540-71389-0_16"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1145/503272.503274",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1051268205"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-540-24597-1_10",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1052767423",
"https://doi.org/10.1007/978-3-540-24597-1_10"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-540-24597-1_10",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1052767423",
"https://doi.org/10.1007/978-3-540-24597-1_10"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1109/lics.2008.34",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1094035074"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1109/lics.2011.15",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1095750847"
],
"type": "CreativeWork"
}
],
"datePublished": "2012",
"datePublishedReg": "2012-01-01",
"description": "We introduce a natural extension of collapsible pushdown systems called annotated pushdown systems that replaces collapse links with stack annotations. We believe this new model has many advantages. We present a saturation method for global backwards reachability analysis of these models that can also be used to analyse collapsible pushdown systems. Beginning with an automaton representing a set of configurations, we build an automaton accepting all configurations that can reach this set. We also improve upon previous saturation techniques for higher-order pushdown systems by significantly reducing the size of the automaton constructed and simplifying the algorithm and proofs.",
"editor": [
{
"familyName": "Czumaj",
"givenName": "Artur",
"type": "Person"
},
{
"familyName": "Mehlhorn",
"givenName": "Kurt",
"type": "Person"
},
{
"familyName": "Pitts",
"givenName": "Andrew",
"type": "Person"
},
{
"familyName": "Wattenhofer",
"givenName": "Roger",
"type": "Person"
}
],
"genre": "chapter",
"id": "sg:pub.10.1007/978-3-642-31585-5_18",
"inLanguage": [
"en"
],
"isAccessibleForFree": true,
"isPartOf": {
"isbn": [
"978-3-642-31584-8",
"978-3-642-31585-5"
],
"name": "Automata, Languages, and Programming",
"type": "Book"
},
"name": "A Saturation Method for Collapsible Pushdown Systems",
"pagination": "165-176",
"productId": [
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/978-3-642-31585-5_18"
]
},
{
"name": "readcube_id",
"type": "PropertyValue",
"value": [
"8e4c2343aa5d08e94264288df2a7d56e192f1d1a3d10bba5b2de1626084536d9"
]
},
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1029869669"
]
}
],
"publisher": {
"location": "Berlin, Heidelberg",
"name": "Springer Berlin Heidelberg",
"type": "Organisation"
},
"sameAs": [
"https://doi.org/10.1007/978-3-642-31585-5_18",
"https://app.dimensions.ai/details/publication/pub.1029869669"
],
"sdDataset": "chapters",
"sdDatePublished": "2019-04-15T19:09",
"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_00000261.jsonl",
"type": "Chapter",
"url": "http://link.springer.com/10.1007/978-3-642-31585-5_18"
}
]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-642-31585-5_18'
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-642-31585-5_18'
Turtle is a human-readable linked data format.
curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-31585-5_18'
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-642-31585-5_18'
This table displays all metadata directly associated to this object as RDF triples.
187 TRIPLES
23 PREDICATES
50 URIs
20 LITERALS
8 BLANK NODES