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/20", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Language, Communication and Culture", 
        "type": "DefinedTerm"
      }, 
      {
        "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/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/2004", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Linguistics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Instytut Informatyki, Uniwersytet Warszawski, Banacha 2, 02-097, Warszawa, Poland", 
          "id": "http://www.grid.ac/institutes/grid.12847.38", 
          "name": [
            "Instytut Informatyki, Uniwersytet Warszawski, Banacha 2, 02-097, Warszawa, Poland"
          ], 
          "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": "1999", 
    "datePublishedReg": "1999-01-01", 
    "description": "The compressed recognition problem consists in checking if an input word w is in a given language L, when we are only given a compressed representation of w. We present several new results related to language recognition problems for compressed texts. These problems are solvable in polynomial time for uncompressed words and some of them become NP-hard for compressed words.Two types of compression are considered: Lempel-Ziv compress and compression in terms of straight-line programs (or sequences of recurrencem, or context-free grammars generating single texts). These compreassions are polynomically related and most of our results apply to both of them.Denote by LZ(w) (SLP(w)) the version of a string w produced by Lempel-Ziv encoding (straight-line program). The complexity of the following problem is considered:given a compressed version (LZ(w) or SLP(w)) of the input word w, test the membership w \u2208 L, where L is a formal language.The complexity depends on the type and description of the language L. Surprisingly the proofs of NP-hardness are in this area usually easier than the proof that a problem in NP.The membership problem is in DSPACE(n2) for general context-free sets L and in NSPACE(n) for linear languages. We show that for unary languages compressed recognition of context-free languages is NP-complete.We also briefly discuss some known results related to the membership problem for the string-matching languages and for languages related to string-matching: square-free wordsm, squares, palindromes, and primitive words.", 
    "editor": [
      {
        "familyName": "Karhum\u00e4ki", 
        "givenName": "Juhani", 
        "type": "Person"
      }, 
      {
        "familyName": "Maurer", 
        "givenName": "Hermann", 
        "type": "Person"
      }, 
      {
        "familyName": "P\u0103un", 
        "givenName": "Gheorghe", 
        "type": "Person"
      }, 
      {
        "familyName": "Rozenberg", 
        "givenName": "Grzegorz", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-60207-8_23", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-642-64304-0", 
        "978-3-642-60207-8"
      ], 
      "name": "Jewels are Forever", 
      "type": "Book"
    }, 
    "keywords": [
      "language recognition problem", 
      "recognition problem", 
      "context-free languages", 
      "word w", 
      "straight-line programs", 
      "Lempel-Ziv", 
      "NP-hardness", 
      "formal language", 
      "membership problem", 
      "polynomial time", 
      "language L", 
      "unary languages", 
      "linear languages", 
      "type of compression", 
      "primitive words", 
      "language", 
      "words", 
      "complexity", 
      "NPs", 
      "sets L", 
      "string w", 
      "text", 
      "proof", 
      "compression", 
      "version", 
      "recognition", 
      "representation", 
      "compress", 
      "results", 
      "description", 
      "terms", 
      "program", 
      "time", 
      "types", 
      "new results", 
      "squares", 
      "palindrome", 
      "problem", 
      "area", 
      "Surprisingly"
    ], 
    "name": "Complexity of Language Recognition Problems for Compressed Words", 
    "pagination": "262-272", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1050084589"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-60207-8_23"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-60207-8_23", 
      "https://app.dimensions.ai/details/publication/pub.1050084589"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-06-01T22:32", 
    "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_303.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-60207-8_23"
  }
]

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.

138 TRIPLES      23 PREDICATES      69 URIs      59 LITERALS      7 BLANK NODES