Pushdown Automata View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2004

AUTHORS

Hendrik Jan Hoogeboom , Joost Engelfriet

ABSTRACT

Recursive functions in a computer program can be modelled by suitable grammatical rules. As an example, cf. Figure 6.1, the recursive function Hanoi, moving n disks from pin s to pin t using additional pin v can be represented by productions like H stv (n) → H svt (n−1) m st H vts (n−1) and H stv (0) → λ—with terminal symbols m xy , x,y ∈ {s,t,v}. Of course, context-free grammars do not have attributes to their nonterminals and we could abstract from them by writing H stv → H svt m st H vts , H stv → λ. More... »

PAGES

117-138

References to SciGraph publications

  • 1964-04. Regular canonical systems in ARCHIV FÜR MATHEMATISCHE LOGIK UND GRUNDLAGENFORSCHUNG
  • Book

    TITLE

    Formal Languages and Applications

    ISBN

    978-3-642-53554-3
    978-3-540-39886-8

    Author Affiliations

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/978-3-540-39886-8_6

    DOI

    http://dx.doi.org/10.1007/978-3-540-39886-8_6

    DIMENSIONS

    https://app.dimensions.ai/details/publication/pub.1011281587


    Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
    Incoming Citations Browse incoming citations for this publication using opencitations.net

    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": "Leiden University", 
              "id": "https://www.grid.ac/institutes/grid.5132.5", 
              "name": [
                "Institute for Advanced Computer Science, Leiden University, Niels Bohrweg 1, 2333 CA\u00a0Leiden, the Netherlands"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Hoogeboom", 
            "givenName": "Hendrik Jan", 
            "id": "sg:person.013762305654.52", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013762305654.52"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Leiden University", 
              "id": "https://www.grid.ac/institutes/grid.5132.5", 
              "name": [
                "Institute for Advanced Computer Science, Leiden University, Niels Bohrweg 1, 2333 CA\u00a0Leiden, the Netherlands"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Engelfriet", 
            "givenName": "Joost", 
            "id": "sg:person.014574236321.39", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014574236321.39"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "https://doi.org/10.1016/0304-3975(78)90020-8", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1002211017"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1090/s0002-9939-1967-0209086-1", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1013161731"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01969548", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1014080380", 
              "https://doi.org/10.1007/bf01969548"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0019-9958(63)90306-1", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1023323978"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0304-3975(02)00027-0", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1027255660"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0304-3975(86)90052-6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1036837367"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0304-3975(86)90052-6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1036837367"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0890-5401(91)90015-t", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1044969549"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0890-5401(87)90014-9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1046201475"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0019-9958(65)90426-2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1047428673"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/0213010", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062841744"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2004", 
        "datePublishedReg": "2004-01-01", 
        "description": "Recursive functions in a computer program can be modelled by suitable grammatical rules. As an example, cf. Figure 6.1, the recursive function Hanoi, moving n disks from pin s to pin t using additional pin v can be represented by productions like H stv (n) \u2192 H svt (n\u22121) m st H vts (n\u22121) and H stv (0) \u2192 \u03bb\u2014with terminal symbols m xy , x,y \u2208 {s,t,v}. Of course, context-free grammars do not have attributes to their nonterminals and we could abstract from them by writing H stv \u2192 H svt m st H vts , H stv \u2192 \u03bb.", 
        "editor": [
          {
            "familyName": "Mart\u00edn-Vide", 
            "givenName": "Carlos", 
            "type": "Person"
          }, 
          {
            "familyName": "Mitrana", 
            "givenName": "Victor", 
            "type": "Person"
          }, 
          {
            "familyName": "P\u0103un", 
            "givenName": "Gheorghe", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/978-3-540-39886-8_6", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": {
          "isbn": [
            "978-3-642-53554-3", 
            "978-3-540-39886-8"
          ], 
          "name": "Formal Languages and Applications", 
          "type": "Book"
        }, 
        "name": "Pushdown Automata", 
        "pagination": "117-138", 
        "productId": [
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/978-3-540-39886-8_6"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "35c03cb3fee8508a0f5a38dfa6075d317883ababb54d2380c9cb0ebceb4359f9"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1011281587"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/978-3-540-39886-8_6", 
          "https://app.dimensions.ai/details/publication/pub.1011281587"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-15T13:26", 
        "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_8664_00000250.jsonl", 
        "type": "Chapter", 
        "url": "http://link.springer.com/10.1007/978-3-540-39886-8_6"
      }
    ]
     

    Download the RDF metadata as:  json-ld nt turtle xml License info

    HOW TO GET THIS DATA PROGRAMMATICALLY:

    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-540-39886-8_6'

    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-540-39886-8_6'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-39886-8_6'

    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-540-39886-8_6'


     

    This table displays all metadata directly associated to this object as RDF triples.

    113 TRIPLES      23 PREDICATES      37 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/978-3-540-39886-8_6 schema:about anzsrc-for:08
    2 anzsrc-for:0801
    3 schema:author Nc5b19ffd96024204a94a7f27169dd99e
    4 schema:citation sg:pub.10.1007/bf01969548
    5 https://doi.org/10.1016/0304-3975(78)90020-8
    6 https://doi.org/10.1016/0304-3975(86)90052-6
    7 https://doi.org/10.1016/0890-5401(87)90014-9
    8 https://doi.org/10.1016/0890-5401(91)90015-t
    9 https://doi.org/10.1016/s0019-9958(63)90306-1
    10 https://doi.org/10.1016/s0019-9958(65)90426-2
    11 https://doi.org/10.1016/s0304-3975(02)00027-0
    12 https://doi.org/10.1090/s0002-9939-1967-0209086-1
    13 https://doi.org/10.1137/0213010
    14 schema:datePublished 2004
    15 schema:datePublishedReg 2004-01-01
    16 schema:description Recursive functions in a computer program can be modelled by suitable grammatical rules. As an example, cf. Figure 6.1, the recursive function Hanoi, moving n disks from pin s to pin t using additional pin v can be represented by productions like H stv (n) → H svt (n−1) m st H vts (n−1) and H stv (0) → λ—with terminal symbols m xy , x,y ∈ {s,t,v}. Of course, context-free grammars do not have attributes to their nonterminals and we could abstract from them by writing H stv → H svt m st H vts , H stv → λ.
    17 schema:editor N9a12c7a0ded14d59a587c470a9ac767e
    18 schema:genre chapter
    19 schema:inLanguage en
    20 schema:isAccessibleForFree false
    21 schema:isPartOf N6c6e17674c8a471e986fffe4a3475ba8
    22 schema:name Pushdown Automata
    23 schema:pagination 117-138
    24 schema:productId N46fb3324755c440daeddcf0d21bbd8fc
    25 Nb562524f7576412492de6a89381d0506
    26 Ncfa929c34d5749b0a8cd88411b630374
    27 schema:publisher Naeb59f52944d4d6d9caa806e3edeb4f4
    28 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011281587
    29 https://doi.org/10.1007/978-3-540-39886-8_6
    30 schema:sdDatePublished 2019-04-15T13:26
    31 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    32 schema:sdPublisher N1de5119bde1e443bad86ffadad371c53
    33 schema:url http://link.springer.com/10.1007/978-3-540-39886-8_6
    34 sgo:license sg:explorer/license/
    35 sgo:sdDataset chapters
    36 rdf:type schema:Chapter
    37 N088a0d3d7b7f4a898825527cdd057b1e rdf:first sg:person.014574236321.39
    38 rdf:rest rdf:nil
    39 N1de5119bde1e443bad86ffadad371c53 schema:name Springer Nature - SN SciGraph project
    40 rdf:type schema:Organization
    41 N362cba13135d45aca8f7e1c7c5b328e6 rdf:first Ne5a18625179c447699b0700722107ad3
    42 rdf:rest rdf:nil
    43 N46fb3324755c440daeddcf0d21bbd8fc schema:name dimensions_id
    44 schema:value pub.1011281587
    45 rdf:type schema:PropertyValue
    46 N4b753fa7d74e4315a75f7541c523f5ca rdf:first N78849a16609c4ebf9bfeeff7f77a3882
    47 rdf:rest N362cba13135d45aca8f7e1c7c5b328e6
    48 N6c6e17674c8a471e986fffe4a3475ba8 schema:isbn 978-3-540-39886-8
    49 978-3-642-53554-3
    50 schema:name Formal Languages and Applications
    51 rdf:type schema:Book
    52 N78849a16609c4ebf9bfeeff7f77a3882 schema:familyName Mitrana
    53 schema:givenName Victor
    54 rdf:type schema:Person
    55 N9a12c7a0ded14d59a587c470a9ac767e rdf:first Na54b0c65f3514c5ea7d731c9d2c48beb
    56 rdf:rest N4b753fa7d74e4315a75f7541c523f5ca
    57 Na54b0c65f3514c5ea7d731c9d2c48beb schema:familyName Martín-Vide
    58 schema:givenName Carlos
    59 rdf:type schema:Person
    60 Naeb59f52944d4d6d9caa806e3edeb4f4 schema:location Berlin, Heidelberg
    61 schema:name Springer Berlin Heidelberg
    62 rdf:type schema:Organisation
    63 Nb562524f7576412492de6a89381d0506 schema:name doi
    64 schema:value 10.1007/978-3-540-39886-8_6
    65 rdf:type schema:PropertyValue
    66 Nc5b19ffd96024204a94a7f27169dd99e rdf:first sg:person.013762305654.52
    67 rdf:rest N088a0d3d7b7f4a898825527cdd057b1e
    68 Ncfa929c34d5749b0a8cd88411b630374 schema:name readcube_id
    69 schema:value 35c03cb3fee8508a0f5a38dfa6075d317883ababb54d2380c9cb0ebceb4359f9
    70 rdf:type schema:PropertyValue
    71 Ne5a18625179c447699b0700722107ad3 schema:familyName Păun
    72 schema:givenName Gheorghe
    73 rdf:type schema:Person
    74 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    75 schema:name Information and Computing Sciences
    76 rdf:type schema:DefinedTerm
    77 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
    78 schema:name Artificial Intelligence and Image Processing
    79 rdf:type schema:DefinedTerm
    80 sg:person.013762305654.52 schema:affiliation https://www.grid.ac/institutes/grid.5132.5
    81 schema:familyName Hoogeboom
    82 schema:givenName Hendrik Jan
    83 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013762305654.52
    84 rdf:type schema:Person
    85 sg:person.014574236321.39 schema:affiliation https://www.grid.ac/institutes/grid.5132.5
    86 schema:familyName Engelfriet
    87 schema:givenName Joost
    88 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014574236321.39
    89 rdf:type schema:Person
    90 sg:pub.10.1007/bf01969548 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014080380
    91 https://doi.org/10.1007/bf01969548
    92 rdf:type schema:CreativeWork
    93 https://doi.org/10.1016/0304-3975(78)90020-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1002211017
    94 rdf:type schema:CreativeWork
    95 https://doi.org/10.1016/0304-3975(86)90052-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036837367
    96 rdf:type schema:CreativeWork
    97 https://doi.org/10.1016/0890-5401(87)90014-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1046201475
    98 rdf:type schema:CreativeWork
    99 https://doi.org/10.1016/0890-5401(91)90015-t schema:sameAs https://app.dimensions.ai/details/publication/pub.1044969549
    100 rdf:type schema:CreativeWork
    101 https://doi.org/10.1016/s0019-9958(63)90306-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1023323978
    102 rdf:type schema:CreativeWork
    103 https://doi.org/10.1016/s0019-9958(65)90426-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047428673
    104 rdf:type schema:CreativeWork
    105 https://doi.org/10.1016/s0304-3975(02)00027-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027255660
    106 rdf:type schema:CreativeWork
    107 https://doi.org/10.1090/s0002-9939-1967-0209086-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013161731
    108 rdf:type schema:CreativeWork
    109 https://doi.org/10.1137/0213010 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062841744
    110 rdf:type schema:CreativeWork
    111 https://www.grid.ac/institutes/grid.5132.5 schema:alternateName Leiden University
    112 schema:name Institute for Advanced Computer Science, Leiden University, Niels Bohrweg 1, 2333 CA Leiden, the Netherlands
    113 rdf:type schema:Organization
     




    Preview window. Press ESC to close (or click here)


    ...