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/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "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"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Turku Centre for Computer Science and Department of Mathematics, Turku University, 20 014, Turku, Finland", 
          "id": "http://www.grid.ac/institutes/grid.1374.1", 
          "name": [
            "Turku Centre for Computer Science and Department of Mathematics, Turku University, 20 014, Turku, Finland"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Plandowski", 
        "givenName": "Wojciech", 
        "id": "sg:person.010207617143.19", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010207617143.19"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, University of Liverpool, UK", 
          "id": "http://www.grid.ac/institutes/grid.10025.36", 
          "name": [
            "Instytut Informatyki, Uniwersytet Warszawski, Banacha 2, 02-097, Warszawa, Poland", 
            "Department of Computer Science, University of Liverpool, UK"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Rytter", 
        "givenName": "Wojciech", 
        "id": "sg:person.013534566577.61", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013534566577.61"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "1998", 
    "datePublishedReg": "1998-01-01", 
    "description": "One of the most intricate algorithms related to words is Makanin's algorithm solving word equations. The algorithm is very complicated and the complexity of the problem of solving word equations is not well understood. Word equations can be used to define various properties of strings, e.g. general versions of pattern-matching with variables. This paper is devoted to introduce a new approach and to study relations between Lempel-Ziv compressions and word equations. Instead of dealing with very long solutions we propose to deal with their Lempel-Ziv encodings. As our first main result we prove that each minimal solution of a word equation is highly compressible (exponentially compressible for long solutions) in terms of Lempel-Ziv encoding. A simple algorithm for solving word equations is derived. If the length of minimal solution is bounded by a singly exponential function (which is believed to be always true) then LZ encoding of each minimal solution is of a polynomial size (though the solution can be exponentially long) and solvability can be checked in nondeterministic polynomial time. As our second main result we prove that the solvability can be tested in polynomial deterministic time if the lengths of all variables are given in binary. We show also that lexicographically first solution for given lengths of variables is highly compressible in terms of Lempel-Ziv encodings.", 
    "editor": [
      {
        "familyName": "Larsen", 
        "givenName": "Kim G.", 
        "type": "Person"
      }, 
      {
        "familyName": "Skyum", 
        "givenName": "Sven", 
        "type": "Person"
      }, 
      {
        "familyName": "Winskel", 
        "givenName": "Glynn", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/bfb0055097", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-64781-2", 
        "978-3-540-68681-1"
      ], 
      "name": "Automata, Languages and Programming", 
      "type": "Book"
    }, 
    "keywords": [
      "word equations", 
      "minimal solutions", 
      "Makanin's algorithm", 
      "first main result", 
      "second main result", 
      "properties of strings", 
      "nondeterministic polynomial time", 
      "long solutions", 
      "main results", 
      "equations", 
      "general version", 
      "deterministic time", 
      "solvability", 
      "polynomial time", 
      "simple algorithm", 
      "length of variables", 
      "first solution", 
      "polynomial size", 
      "intricate algorithms", 
      "algorithm", 
      "exponential function", 
      "solution", 
      "new approach", 
      "variables", 
      "Lempel-Ziv compression", 
      "terms", 
      "strings", 
      "problem", 
      "complexity", 
      "LZ", 
      "binaries", 
      "version", 
      "properties", 
      "applications", 
      "length", 
      "approach", 
      "results", 
      "function", 
      "encoding", 
      "time", 
      "size", 
      "relation", 
      "compression", 
      "words", 
      "paper"
    ], 
    "name": "Application of Lempel-Ziv encodings to the solution of word equations", 
    "pagination": "731-742", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1026190890"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/bfb0055097"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/bfb0055097", 
      "https://app.dimensions.ai/details/publication/pub.1026190890"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-06-01T22:28", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220601/entities/gbq_results/chapter/chapter_165.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/bfb0055097"
  }
]

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

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

126 TRIPLES      23 PREDICATES      71 URIs      64 LITERALS      7 BLANK NODES