Time optimal left to right construction of position trees View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1987-08

AUTHORS

M. Kempf, R. Bayer, U. Güntzer

ABSTRACT

In the following paper we are presenting a new algorithm for the on-line construction of position trees. Reading a given input string from left to right we are generating its position tree with the aid of the general concept of infix trees. An additional chain structure within the trees, called tail node connection, enables us to construct the tree within the best possible time (proportional to the number of nodes). More... »

PAGES

461-474

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/bf00292114

DOI

http://dx.doi.org/10.1007/bf00292114

DIMENSIONS

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


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/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0803", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computer Software", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0804", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Data Format", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Institut f\u00fcr Informatik, Technische Universit\u00e4t M\u00fcnchen, Postfach 202420, D-8000, M\u00fcnchen, Federal Republic of Germany", 
          "id": "http://www.grid.ac/institutes/grid.6936.a", 
          "name": [
            "Institut f\u00fcr Informatik, Technische Universit\u00e4t M\u00fcnchen, Postfach 202420, D-8000, M\u00fcnchen, Federal Republic of Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Kempf", 
        "givenName": "M.", 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Institut f\u00fcr Informatik, Technische Universit\u00e4t M\u00fcnchen, Postfach 202420, D-8000, M\u00fcnchen, Federal Republic of Germany", 
          "id": "http://www.grid.ac/institutes/grid.6936.a", 
          "name": [
            "Institut f\u00fcr Informatik, Technische Universit\u00e4t M\u00fcnchen, Postfach 202420, D-8000, M\u00fcnchen, Federal Republic of Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Bayer", 
        "givenName": "R.", 
        "id": "sg:person.010052470746.96", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010052470746.96"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Institut f\u00fcr Informatik, Technische Universit\u00e4t M\u00fcnchen, Postfach 202420, D-8000, M\u00fcnchen, Federal Republic of Germany", 
          "id": "http://www.grid.ac/institutes/grid.6936.a", 
          "name": [
            "Institut f\u00fcr Informatik, Technische Universit\u00e4t M\u00fcnchen, Postfach 202420, D-8000, M\u00fcnchen, Federal Republic of Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "G\u00fcntzer", 
        "givenName": "U.", 
        "id": "sg:person.013324511711.75", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013324511711.75"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "1987-08", 
    "datePublishedReg": "1987-08-01", 
    "description": "In the following paper we are presenting a new algorithm for the on-line construction of position trees. Reading a given input string from left to right we are generating its position tree with the aid of the general concept of infix trees. An additional chain structure within the trees, called tail node connection, enables us to construct the tree within the best possible time (proportional to the number of nodes).", 
    "genre": "article", 
    "id": "sg:pub.10.1007/bf00292114", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1133515", 
        "issn": [
          "0001-5903", 
          "1432-0525"
        ], 
        "name": "Acta Informatica", 
        "publisher": "Springer Nature", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "4", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "24"
      }
    ], 
    "keywords": [
      "best possible time", 
      "possible time", 
      "time", 
      "aid", 
      "general concept", 
      "connection", 
      "concept", 
      "trees", 
      "structure", 
      "Time Optimal", 
      "optimal", 
      "paper", 
      "construction", 
      "algorithm", 
      "line construction", 
      "strings", 
      "chain structure", 
      "node connections", 
      "new algorithm", 
      "input string", 
      "position trees", 
      "infix trees", 
      "additional chain structure", 
      "tail node connection", 
      "right construction"
    ], 
    "name": "Time optimal left to right construction of position trees", 
    "pagination": "461-474", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1024511249"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/bf00292114"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/bf00292114", 
      "https://app.dimensions.ai/details/publication/pub.1024511249"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2022-01-01T18:04", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220101/entities/gbq_results/article/article_215.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://doi.org/10.1007/bf00292114"
  }
]
 

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/bf00292114'

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/bf00292114'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/bf00292114'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/bf00292114'


 

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

104 TRIPLES      21 PREDICATES      53 URIs      43 LITERALS      6 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/bf00292114 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 anzsrc-for:0803
4 anzsrc-for:0804
5 schema:author N57b989f94c3a4566ba14d96f494ed3e6
6 schema:datePublished 1987-08
7 schema:datePublishedReg 1987-08-01
8 schema:description In the following paper we are presenting a new algorithm for the on-line construction of position trees. Reading a given input string from left to right we are generating its position tree with the aid of the general concept of infix trees. An additional chain structure within the trees, called tail node connection, enables us to construct the tree within the best possible time (proportional to the number of nodes).
9 schema:genre article
10 schema:inLanguage en
11 schema:isAccessibleForFree false
12 schema:isPartOf N37fc5cb7787d45cf98c8309eceeee4b6
13 N91c84d922a6b478fbb58604c9ad188aa
14 sg:journal.1133515
15 schema:keywords Time Optimal
16 additional chain structure
17 aid
18 algorithm
19 best possible time
20 chain structure
21 concept
22 connection
23 construction
24 general concept
25 infix trees
26 input string
27 line construction
28 new algorithm
29 node connections
30 optimal
31 paper
32 position trees
33 possible time
34 right construction
35 strings
36 structure
37 tail node connection
38 time
39 trees
40 schema:name Time optimal left to right construction of position trees
41 schema:pagination 461-474
42 schema:productId N9d71d1223ac64cc59e71e317292234a0
43 Nb794c52494454651835dd9981537972b
44 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024511249
45 https://doi.org/10.1007/bf00292114
46 schema:sdDatePublished 2022-01-01T18:04
47 schema:sdLicense https://scigraph.springernature.com/explorer/license/
48 schema:sdPublisher N4ec9915f74c445f0af31a2509317e574
49 schema:url https://doi.org/10.1007/bf00292114
50 sgo:license sg:explorer/license/
51 sgo:sdDataset articles
52 rdf:type schema:ScholarlyArticle
53 N26e2154da92d47e3b5072f4b4f1260e0 rdf:first sg:person.013324511711.75
54 rdf:rest rdf:nil
55 N319e8f1ee2d1423b988f614de7ddc620 rdf:first sg:person.010052470746.96
56 rdf:rest N26e2154da92d47e3b5072f4b4f1260e0
57 N37fc5cb7787d45cf98c8309eceeee4b6 schema:volumeNumber 24
58 rdf:type schema:PublicationVolume
59 N4ec9915f74c445f0af31a2509317e574 schema:name Springer Nature - SN SciGraph project
60 rdf:type schema:Organization
61 N57b989f94c3a4566ba14d96f494ed3e6 rdf:first Ncaabe99ed08049049bff7a9c0e05b3da
62 rdf:rest N319e8f1ee2d1423b988f614de7ddc620
63 N91c84d922a6b478fbb58604c9ad188aa schema:issueNumber 4
64 rdf:type schema:PublicationIssue
65 N9d71d1223ac64cc59e71e317292234a0 schema:name dimensions_id
66 schema:value pub.1024511249
67 rdf:type schema:PropertyValue
68 Nb794c52494454651835dd9981537972b schema:name doi
69 schema:value 10.1007/bf00292114
70 rdf:type schema:PropertyValue
71 Ncaabe99ed08049049bff7a9c0e05b3da schema:affiliation grid-institutes:grid.6936.a
72 schema:familyName Kempf
73 schema:givenName M.
74 rdf:type schema:Person
75 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
76 schema:name Information and Computing Sciences
77 rdf:type schema:DefinedTerm
78 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
79 schema:name Computation Theory and Mathematics
80 rdf:type schema:DefinedTerm
81 anzsrc-for:0803 schema:inDefinedTermSet anzsrc-for:
82 schema:name Computer Software
83 rdf:type schema:DefinedTerm
84 anzsrc-for:0804 schema:inDefinedTermSet anzsrc-for:
85 schema:name Data Format
86 rdf:type schema:DefinedTerm
87 sg:journal.1133515 schema:issn 0001-5903
88 1432-0525
89 schema:name Acta Informatica
90 schema:publisher Springer Nature
91 rdf:type schema:Periodical
92 sg:person.010052470746.96 schema:affiliation grid-institutes:grid.6936.a
93 schema:familyName Bayer
94 schema:givenName R.
95 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010052470746.96
96 rdf:type schema:Person
97 sg:person.013324511711.75 schema:affiliation grid-institutes:grid.6936.a
98 schema:familyName Güntzer
99 schema:givenName U.
100 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013324511711.75
101 rdf:type schema:Person
102 grid-institutes:grid.6936.a schema:alternateName Institut für Informatik, Technische Universität München, Postfach 202420, D-8000, München, Federal Republic of Germany
103 schema:name Institut für Informatik, Technische Universität München, Postfach 202420, D-8000, München, Federal Republic of Germany
104 rdf:type schema:Organization
 




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


...