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 Nf0492d13bcc54d6593c40237c58ddc77
    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 N01d25e8518d14f87bd8f69f9b0ef2e1c
    18 schema:genre chapter
    19 schema:inLanguage en
    20 schema:isAccessibleForFree false
    21 schema:isPartOf Nf4bc61df75874b6eb104a001e5afc605
    22 schema:name Pushdown Automata
    23 schema:pagination 117-138
    24 schema:productId N4234ac05b91e48049b2d9bcc46866508
    25 N461eaa28111a4c38b041b2b8bfe96e51
    26 N6d4f345577d24e6daf6ee01752927515
    27 schema:publisher N9cf06f3f4a9547e5b6ff57bbe6b7133d
    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 N46a498317ec14bcbb8bd095bff1a2b5b
    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 N01d25e8518d14f87bd8f69f9b0ef2e1c rdf:first N10eae09af1bd45208c7d63e506f269bb
    38 rdf:rest N9d25ec020cef4379ada447d6dc05eba6
    39 N10eae09af1bd45208c7d63e506f269bb schema:familyName Martín-Vide
    40 schema:givenName Carlos
    41 rdf:type schema:Person
    42 N3ddcda8f8ae64f6dbba13267eb74ea44 rdf:first sg:person.014574236321.39
    43 rdf:rest rdf:nil
    44 N4234ac05b91e48049b2d9bcc46866508 schema:name doi
    45 schema:value 10.1007/978-3-540-39886-8_6
    46 rdf:type schema:PropertyValue
    47 N461eaa28111a4c38b041b2b8bfe96e51 schema:name dimensions_id
    48 schema:value pub.1011281587
    49 rdf:type schema:PropertyValue
    50 N46a498317ec14bcbb8bd095bff1a2b5b schema:name Springer Nature - SN SciGraph project
    51 rdf:type schema:Organization
    52 N592be48e81b641bfb9e0b67707a8b58d schema:familyName Mitrana
    53 schema:givenName Victor
    54 rdf:type schema:Person
    55 N68c3a69998ee412eac086d37615f3536 rdf:first N6a5d8930d0ca4e9483720d6aef480ff4
    56 rdf:rest rdf:nil
    57 N6a5d8930d0ca4e9483720d6aef480ff4 schema:familyName Păun
    58 schema:givenName Gheorghe
    59 rdf:type schema:Person
    60 N6d4f345577d24e6daf6ee01752927515 schema:name readcube_id
    61 schema:value 35c03cb3fee8508a0f5a38dfa6075d317883ababb54d2380c9cb0ebceb4359f9
    62 rdf:type schema:PropertyValue
    63 N9cf06f3f4a9547e5b6ff57bbe6b7133d schema:location Berlin, Heidelberg
    64 schema:name Springer Berlin Heidelberg
    65 rdf:type schema:Organisation
    66 N9d25ec020cef4379ada447d6dc05eba6 rdf:first N592be48e81b641bfb9e0b67707a8b58d
    67 rdf:rest N68c3a69998ee412eac086d37615f3536
    68 Nf0492d13bcc54d6593c40237c58ddc77 rdf:first sg:person.013762305654.52
    69 rdf:rest N3ddcda8f8ae64f6dbba13267eb74ea44
    70 Nf4bc61df75874b6eb104a001e5afc605 schema:isbn 978-3-540-39886-8
    71 978-3-642-53554-3
    72 schema:name Formal Languages and Applications
    73 rdf:type schema:Book
    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)


    ...