Sensing versus nonsensing automata View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

1995

AUTHORS

Pavol ďuriš , Zvi Galil

ABSTRACT

It is shown that one way deterministic sensing two head finite automata are more powerful than one way deterministic two head finite automata. This result solves a 14 year old open problem [2]. The proof uses two new pumping lemmas.

PAGES

455-463

Book

TITLE

Automata, Languages and Programming

ISBN

978-3-540-60084-8
978-3-540-49425-6

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-60084-1_96

DOI

http://dx.doi.org/10.1007/3-540-60084-1_96

DIMENSIONS

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


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", 
    "author": [
      {
        "affiliation": {
          "alternateName": "Comenius University", 
          "id": "https://www.grid.ac/institutes/grid.7634.6", 
          "name": [
            "Department of Computer Science, Comenius University, 842 15\u00a0Bratislava, Slovakia"
          ], 
          "type": "Organization"
        }, 
        "familyName": "\u010furi\u0161", 
        "givenName": "Pavol", 
        "id": "sg:person.014444123227.40", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014444123227.40"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Columbia University", 
          "id": "https://www.grid.ac/institutes/grid.21729.3f", 
          "name": [
            "Department of Computer Science, Columbia University, 10027\u00a0New York, NY"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Galil", 
        "givenName": "Zvi", 
        "id": "sg:person.0675716504.71", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0675716504.71"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "1995", 
    "datePublishedReg": "1995-01-01", 
    "description": "It is shown that one way deterministic sensing two head finite automata are more powerful than one way deterministic two head finite automata. This result solves a 14 year old open problem [2]. The proof uses two new pumping lemmas.", 
    "editor": [
      {
        "familyName": "F\u00fcl\u00f6p", 
        "givenName": "Zolt\u00e1n", 
        "type": "Person"
      }, 
      {
        "familyName": "G\u00e9cseg", 
        "givenName": "Ferenc", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-60084-1_96", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isFundedItemOf": [
      {
        "id": "sg:grant.3388542", 
        "type": "MonetaryGrant"
      }, 
      {
        "id": "sg:grant.3417312", 
        "type": "MonetaryGrant"
      }
    ], 
    "isPartOf": {
      "isbn": [
        "978-3-540-60084-8", 
        "978-3-540-49425-6"
      ], 
      "name": "Automata, Languages and Programming", 
      "type": "Book"
    }, 
    "name": "Sensing versus nonsensing automata", 
    "pagination": "455-463", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-60084-1_96"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "48cfd3c2ee71ea0b8936a090879f1d56c3f63e52cd402bb06bff3038ed0ae4e9"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1015282115"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-60084-1_96", 
      "https://app.dimensions.ai/details/publication/pub.1015282115"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-15T16:59", 
    "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_8678_00000026.jsonl", 
    "type": "Chapter", 
    "url": "http://link.springer.com/10.1007/3-540-60084-1_96"
  }
]
 

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/3-540-60084-1_96'

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/3-540-60084-1_96'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-60084-1_96'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/3-540-60084-1_96'


 

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

76 TRIPLES      21 PREDICATES      25 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-60084-1_96 schema:author N5a291bfa8d4740d5b768e7ce2f68b1af
2 schema:datePublished 1995
3 schema:datePublishedReg 1995-01-01
4 schema:description It is shown that one way deterministic sensing two head finite automata are more powerful than one way deterministic two head finite automata. This result solves a 14 year old open problem [2]. The proof uses two new pumping lemmas.
5 schema:editor Ne5fc522bf06c4524947c0ad5aea82870
6 schema:genre chapter
7 schema:inLanguage en
8 schema:isAccessibleForFree false
9 schema:isPartOf N9617c846a86a4ed5a7bc6c8600fa5104
10 schema:name Sensing versus nonsensing automata
11 schema:pagination 455-463
12 schema:productId N1c8e9a460d7a446287da4d850d556ffd
13 N6294c363749749f1b5cc73a6079b415e
14 Nee7217ddc5bf4795bdb6a47841929a2a
15 schema:publisher Nec13eef49f8a45afb6ec7ce3c0f9463a
16 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015282115
17 https://doi.org/10.1007/3-540-60084-1_96
18 schema:sdDatePublished 2019-04-15T16:59
19 schema:sdLicense https://scigraph.springernature.com/explorer/license/
20 schema:sdPublisher N6b343e35136e4ceabe23d3425b17df58
21 schema:url http://link.springer.com/10.1007/3-540-60084-1_96
22 sgo:license sg:explorer/license/
23 sgo:sdDataset chapters
24 rdf:type schema:Chapter
25 N09c5cb319b0c4fc487141ef9dda43fb7 rdf:first sg:person.0675716504.71
26 rdf:rest rdf:nil
27 N1c8e9a460d7a446287da4d850d556ffd schema:name dimensions_id
28 schema:value pub.1015282115
29 rdf:type schema:PropertyValue
30 N5a291bfa8d4740d5b768e7ce2f68b1af rdf:first sg:person.014444123227.40
31 rdf:rest N09c5cb319b0c4fc487141ef9dda43fb7
32 N6294c363749749f1b5cc73a6079b415e schema:name readcube_id
33 schema:value 48cfd3c2ee71ea0b8936a090879f1d56c3f63e52cd402bb06bff3038ed0ae4e9
34 rdf:type schema:PropertyValue
35 N6b343e35136e4ceabe23d3425b17df58 schema:name Springer Nature - SN SciGraph project
36 rdf:type schema:Organization
37 N77a7964a745643d08afdb250497691b1 schema:familyName Gécseg
38 schema:givenName Ferenc
39 rdf:type schema:Person
40 N9617c846a86a4ed5a7bc6c8600fa5104 schema:isbn 978-3-540-49425-6
41 978-3-540-60084-8
42 schema:name Automata, Languages and Programming
43 rdf:type schema:Book
44 Nad2e9b83f2ff44eb9b311a5dab7f660f schema:familyName Fülöp
45 schema:givenName Zoltán
46 rdf:type schema:Person
47 Nb05559aea4cb4353a7f47ce027770227 rdf:first N77a7964a745643d08afdb250497691b1
48 rdf:rest rdf:nil
49 Ne5fc522bf06c4524947c0ad5aea82870 rdf:first Nad2e9b83f2ff44eb9b311a5dab7f660f
50 rdf:rest Nb05559aea4cb4353a7f47ce027770227
51 Nec13eef49f8a45afb6ec7ce3c0f9463a schema:location Berlin, Heidelberg
52 schema:name Springer Berlin Heidelberg
53 rdf:type schema:Organisation
54 Nee7217ddc5bf4795bdb6a47841929a2a schema:name doi
55 schema:value 10.1007/3-540-60084-1_96
56 rdf:type schema:PropertyValue
57 sg:grant.3388542 http://pending.schema.org/fundedItem sg:pub.10.1007/3-540-60084-1_96
58 rdf:type schema:MonetaryGrant
59 sg:grant.3417312 http://pending.schema.org/fundedItem sg:pub.10.1007/3-540-60084-1_96
60 rdf:type schema:MonetaryGrant
61 sg:person.014444123227.40 schema:affiliation https://www.grid.ac/institutes/grid.7634.6
62 schema:familyName ďuriš
63 schema:givenName Pavol
64 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014444123227.40
65 rdf:type schema:Person
66 sg:person.0675716504.71 schema:affiliation https://www.grid.ac/institutes/grid.21729.3f
67 schema:familyName Galil
68 schema:givenName Zvi
69 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0675716504.71
70 rdf:type schema:Person
71 https://www.grid.ac/institutes/grid.21729.3f schema:alternateName Columbia University
72 schema:name Department of Computer Science, Columbia University, 10027 New York, NY
73 rdf:type schema:Organization
74 https://www.grid.ac/institutes/grid.7634.6 schema:alternateName Comenius University
75 schema:name Department of Computer Science, Comenius University, 842 15 Bratislava, Slovakia
76 rdf:type schema:Organization
 




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


...