Lower bounds on algebraic random access machines View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

1995

AUTHORS

Amir M. Ben-Amram , Zvi Galil

ABSTRACT

We prove general lower bounds for set recognition on random access machines (RAMs) that operate on real numbers with algebraic operations {+, −, ×, /}, as well as RAMs that use the operations {+, −, ×, ⌈ ⌋}. We do it by extending a technique formerly used with respect to algebraic computation trees. In the case of algebraic computation trees, the complexity was related to the number of connected components of the set W to be recognized. For RAMs, two similar results apply to the number of connected components of Wo, the topological interior of W. Other results use (¯W)o, the interior of the topological closure of W. We present theorems that can be applied to a variety of problems and obtain lower bounds, many of them tight, for the following models: More... »

PAGES

360-371

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_88

DOI

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

DIMENSIONS

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


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/0101", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Pure 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": {
          "name": [
            "DIKU, University of Copenhagen, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Ben-Amram", 
        "givenName": "Amir M.", 
        "id": "sg:person.016032444537.11", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016032444537.11"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "name": [
            "Tel-Aviv University, USA"
          ], 
          "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": "We prove general lower bounds for set recognition on random access machines (RAMs) that operate on real numbers with algebraic operations {+, \u2212, \u00d7, /}, as well as RAMs that use the operations {+, \u2212, \u00d7, \u2308 \u230b}. We do it by extending a technique formerly used with respect to algebraic computation trees. In the case of algebraic computation trees, the complexity was related to the number of connected components of the set W to be recognized. For RAMs, two similar results apply to the number of connected components of Wo, the topological interior of W. Other results use (\u00afW)o, the interior of the topological closure of W. We present theorems that can be applied to a variety of problems and obtain lower bounds, many of them tight, for the following models: ", 
    "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_88", 
    "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": "Lower bounds on algebraic random access machines", 
    "pagination": "360-371", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-60084-1_88"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "c58d0d3d2386dc8fc45cbf11f28816ebec19ea74923ecaa077d1aafda7783db9"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1041469932"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-60084-1_88", 
      "https://app.dimensions.ai/details/publication/pub.1041469932"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-15T16:05", 
    "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_8675_00000071.jsonl", 
    "type": "Chapter", 
    "url": "http://link.springer.com/10.1007/3-540-60084-1_88"
  }
]
 

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_88'

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_88'

Turtle is a human-readable linked data format.

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

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_88'


 

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

82 TRIPLES      22 PREDICATES      27 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-60084-1_88 schema:about anzsrc-for:01
2 anzsrc-for:0101
3 schema:author N7ea34e37eebf495fa6a83a177da64d26
4 schema:datePublished 1995
5 schema:datePublishedReg 1995-01-01
6 schema:description We prove general lower bounds for set recognition on random access machines (RAMs) that operate on real numbers with algebraic operations {+, −, ×, /}, as well as RAMs that use the operations {+, −, ×, ⌈ ⌋}. We do it by extending a technique formerly used with respect to algebraic computation trees. In the case of algebraic computation trees, the complexity was related to the number of connected components of the set W to be recognized. For RAMs, two similar results apply to the number of connected components of Wo, the topological interior of W. Other results use (¯W)o, the interior of the topological closure of W. We present theorems that can be applied to a variety of problems and obtain lower bounds, many of them tight, for the following models:
7 schema:editor Nfc7129bb76414e0d8fbc7e861bbb6ee0
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N21a1c23bbcdb46a58c847ec71a35ecd4
12 schema:name Lower bounds on algebraic random access machines
13 schema:pagination 360-371
14 schema:productId N3ff1ae826a094237bf42459057c00a23
15 N75ee95020d4f4afb89999aea347092ee
16 N9111b7c557244325aa3353878ea93e5b
17 schema:publisher Na0ca0e9b7e9a4bacadd962b8f4df98ed
18 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041469932
19 https://doi.org/10.1007/3-540-60084-1_88
20 schema:sdDatePublished 2019-04-15T16:05
21 schema:sdLicense https://scigraph.springernature.com/explorer/license/
22 schema:sdPublisher Nf325f8ee67bb4db09485915727b4cb39
23 schema:url http://link.springer.com/10.1007/3-540-60084-1_88
24 sgo:license sg:explorer/license/
25 sgo:sdDataset chapters
26 rdf:type schema:Chapter
27 N043f4ab657dc4527b16c111daca64fd0 rdf:first sg:person.0675716504.71
28 rdf:rest rdf:nil
29 N0e116b18a99f457cb84097aa821aa759 schema:familyName Gécseg
30 schema:givenName Ferenc
31 rdf:type schema:Person
32 N21a1c23bbcdb46a58c847ec71a35ecd4 schema:isbn 978-3-540-49425-6
33 978-3-540-60084-8
34 schema:name Automata, Languages and Programming
35 rdf:type schema:Book
36 N3ff1ae826a094237bf42459057c00a23 schema:name doi
37 schema:value 10.1007/3-540-60084-1_88
38 rdf:type schema:PropertyValue
39 N742e3fa0b1f74655a44cc679a993b0ab rdf:first N0e116b18a99f457cb84097aa821aa759
40 rdf:rest rdf:nil
41 N75ee95020d4f4afb89999aea347092ee schema:name readcube_id
42 schema:value c58d0d3d2386dc8fc45cbf11f28816ebec19ea74923ecaa077d1aafda7783db9
43 rdf:type schema:PropertyValue
44 N7ea34e37eebf495fa6a83a177da64d26 rdf:first sg:person.016032444537.11
45 rdf:rest N043f4ab657dc4527b16c111daca64fd0
46 N9111b7c557244325aa3353878ea93e5b schema:name dimensions_id
47 schema:value pub.1041469932
48 rdf:type schema:PropertyValue
49 N9acdc6b4f48648afb7f51f07ed9db338 schema:name Tel-Aviv University, USA
50 rdf:type schema:Organization
51 Na0ca0e9b7e9a4bacadd962b8f4df98ed schema:location Berlin, Heidelberg
52 schema:name Springer Berlin Heidelberg
53 rdf:type schema:Organisation
54 Na547515312624665bc0284a578a55407 schema:name DIKU, University of Copenhagen, USA
55 rdf:type schema:Organization
56 Nefb37ad113054d878198d9ee31d2c0c5 schema:familyName Fülöp
57 schema:givenName Zoltán
58 rdf:type schema:Person
59 Nf325f8ee67bb4db09485915727b4cb39 schema:name Springer Nature - SN SciGraph project
60 rdf:type schema:Organization
61 Nfc7129bb76414e0d8fbc7e861bbb6ee0 rdf:first Nefb37ad113054d878198d9ee31d2c0c5
62 rdf:rest N742e3fa0b1f74655a44cc679a993b0ab
63 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
64 schema:name Mathematical Sciences
65 rdf:type schema:DefinedTerm
66 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
67 schema:name Pure Mathematics
68 rdf:type schema:DefinedTerm
69 sg:grant.3388542 http://pending.schema.org/fundedItem sg:pub.10.1007/3-540-60084-1_88
70 rdf:type schema:MonetaryGrant
71 sg:grant.3417312 http://pending.schema.org/fundedItem sg:pub.10.1007/3-540-60084-1_88
72 rdf:type schema:MonetaryGrant
73 sg:person.016032444537.11 schema:affiliation Na547515312624665bc0284a578a55407
74 schema:familyName Ben-Amram
75 schema:givenName Amir M.
76 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016032444537.11
77 rdf:type schema:Person
78 sg:person.0675716504.71 schema:affiliation N9acdc6b4f48648afb7f51f07ed9db338
79 schema:familyName Galil
80 schema:givenName Zvi
81 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0675716504.71
82 rdf:type schema:Person
 




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


...