Compressed Membership in Automata with Compressed Labels View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2011

AUTHORS

Markus Lohrey , Christian Mathissen

ABSTRACT

The algorithmic problem of whether a compressed string is accepted by a (nondeterministic) finite state automaton with compressed transition labels is investigated. For string compression, straight-line programs (SLPs), i.e., context-free grammars that generate exactly one string, are used. Two algorithms for this problem are presented. The first one works in polynomial time, if all transition labels are nonperiodic strings (or more generally, the word length divided by the period is bounded polynomially in the input size). This answers a question of Plandowski and Rytter. The second (nondeterministic) algorithm is an NP-algorithm under the assumption that for each transition label the period is bounded polynomially in the input size. This generalizes the NP upper bound for the case of a unary alphabet, shown by Plandowski and Rytter. More... »

PAGES

275-288

Book

TITLE

Computer Science – Theory and Applications

ISBN

978-3-642-20711-2
978-3-642-20712-9

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-20712-9_21

DOI

http://dx.doi.org/10.1007/978-3-642-20712-9_21

DIMENSIONS

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


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"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Institut f\u00fcr Informatik, Universit\u00e4t Leipzig, Germany", 
          "id": "http://www.grid.ac/institutes/grid.9647.c", 
          "name": [
            "Institut f\u00fcr Informatik, Universit\u00e4t Leipzig, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Lohrey", 
        "givenName": "Markus", 
        "id": "sg:person.015611460437.34", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015611460437.34"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Institut f\u00fcr Informatik, Universit\u00e4t Leipzig, Germany", 
          "id": "http://www.grid.ac/institutes/grid.9647.c", 
          "name": [
            "Institut f\u00fcr Informatik, Universit\u00e4t Leipzig, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Mathissen", 
        "givenName": "Christian", 
        "id": "sg:person.014237551615.24", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014237551615.24"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2011", 
    "datePublishedReg": "2011-01-01", 
    "description": "The algorithmic problem of whether a compressed string is accepted by a (nondeterministic) finite state automaton with compressed transition labels is investigated. For string compression, straight-line programs (SLPs), i.e., context-free grammars that generate exactly one string, are used. Two algorithms for this problem are presented. The first one works in polynomial time, if all transition labels are nonperiodic strings (or more generally, the word length divided by the period is bounded polynomially in the input size). This answers a question of Plandowski and Rytter. The second (nondeterministic) algorithm is an NP-algorithm under the assumption that for each transition label the period is bounded polynomially in the input size. This generalizes the NP upper bound for the case of a unary alphabet, shown by Plandowski and Rytter.", 
    "editor": [
      {
        "familyName": "Kulikov", 
        "givenName": "Alexander", 
        "type": "Person"
      }, 
      {
        "familyName": "Vereshchagin", 
        "givenName": "Nikolay", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-20712-9_21", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-642-20711-2", 
        "978-3-642-20712-9"
      ], 
      "name": "Computer Science \u2013 Theory and Applications", 
      "type": "Book"
    }, 
    "keywords": [
      "straight-line programs", 
      "transition labels", 
      "finite state automata", 
      "string compression", 
      "context-free grammars", 
      "input size", 
      "polynomial time", 
      "second algorithm", 
      "algorithmic problems", 
      "state automata", 
      "NP upper", 
      "NP algorithm", 
      "algorithm", 
      "Plandowski", 
      "labels", 
      "automata", 
      "Rytter", 
      "string", 
      "alphabet", 
      "grammar", 
      "unary alphabet", 
      "compression", 
      "program", 
      "time", 
      "membership", 
      "assumption", 
      "upper", 
      "questions", 
      "size", 
      "cases", 
      "period", 
      "problem"
    ], 
    "name": "Compressed Membership in Automata with Compressed Labels", 
    "pagination": "275-288", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1012277274"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-20712-9_21"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-20712-9_21", 
      "https://app.dimensions.ai/details/publication/pub.1012277274"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-06-01T22:30", 
    "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_255.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-20712-9_21"
  }
]
 

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/978-3-642-20712-9_21'

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/978-3-642-20712-9_21'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-20712-9_21'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-20712-9_21'


 

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

104 TRIPLES      23 PREDICATES      58 URIs      51 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-20712-9_21 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N62e107b3f9cc446688a8c963ecdbd30a
4 schema:datePublished 2011
5 schema:datePublishedReg 2011-01-01
6 schema:description The algorithmic problem of whether a compressed string is accepted by a (nondeterministic) finite state automaton with compressed transition labels is investigated. For string compression, straight-line programs (SLPs), i.e., context-free grammars that generate exactly one string, are used. Two algorithms for this problem are presented. The first one works in polynomial time, if all transition labels are nonperiodic strings (or more generally, the word length divided by the period is bounded polynomially in the input size). This answers a question of Plandowski and Rytter. The second (nondeterministic) algorithm is an NP-algorithm under the assumption that for each transition label the period is bounded polynomially in the input size. This generalizes the NP upper bound for the case of a unary alphabet, shown by Plandowski and Rytter.
7 schema:editor N5079afb141364837b41a97a7b033d4ea
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf Nfd7c9e614ad64b7eae1aa34b9f91e8d7
12 schema:keywords NP algorithm
13 NP upper
14 Plandowski
15 Rytter
16 algorithm
17 algorithmic problems
18 alphabet
19 assumption
20 automata
21 cases
22 compression
23 context-free grammars
24 finite state automata
25 grammar
26 input size
27 labels
28 membership
29 period
30 polynomial time
31 problem
32 program
33 questions
34 second algorithm
35 size
36 state automata
37 straight-line programs
38 string
39 string compression
40 time
41 transition labels
42 unary alphabet
43 upper
44 schema:name Compressed Membership in Automata with Compressed Labels
45 schema:pagination 275-288
46 schema:productId N1d5682b469674228b1e278e5d0b06735
47 N372a7db0c389464aba67791a25cad915
48 schema:publisher N8f3d8c3fd7ec4aada743c4cb13d46eba
49 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012277274
50 https://doi.org/10.1007/978-3-642-20712-9_21
51 schema:sdDatePublished 2022-06-01T22:30
52 schema:sdLicense https://scigraph.springernature.com/explorer/license/
53 schema:sdPublisher N4839f5208934428a8eb513777bf15264
54 schema:url https://doi.org/10.1007/978-3-642-20712-9_21
55 sgo:license sg:explorer/license/
56 sgo:sdDataset chapters
57 rdf:type schema:Chapter
58 N1d5682b469674228b1e278e5d0b06735 schema:name doi
59 schema:value 10.1007/978-3-642-20712-9_21
60 rdf:type schema:PropertyValue
61 N3470821f7eee44b98691aeab690cf4b4 rdf:first sg:person.014237551615.24
62 rdf:rest rdf:nil
63 N372a7db0c389464aba67791a25cad915 schema:name dimensions_id
64 schema:value pub.1012277274
65 rdf:type schema:PropertyValue
66 N4839f5208934428a8eb513777bf15264 schema:name Springer Nature - SN SciGraph project
67 rdf:type schema:Organization
68 N4b0c4de099594b7e8aecb808442c3673 schema:familyName Vereshchagin
69 schema:givenName Nikolay
70 rdf:type schema:Person
71 N5079afb141364837b41a97a7b033d4ea rdf:first N5f237ba1b3b343faa91fc6a0f998a2ec
72 rdf:rest Nc61f25d9af7a4c419c4b0d61941b8e43
73 N5f237ba1b3b343faa91fc6a0f998a2ec schema:familyName Kulikov
74 schema:givenName Alexander
75 rdf:type schema:Person
76 N62e107b3f9cc446688a8c963ecdbd30a rdf:first sg:person.015611460437.34
77 rdf:rest N3470821f7eee44b98691aeab690cf4b4
78 N8f3d8c3fd7ec4aada743c4cb13d46eba schema:name Springer Nature
79 rdf:type schema:Organisation
80 Nc61f25d9af7a4c419c4b0d61941b8e43 rdf:first N4b0c4de099594b7e8aecb808442c3673
81 rdf:rest rdf:nil
82 Nfd7c9e614ad64b7eae1aa34b9f91e8d7 schema:isbn 978-3-642-20711-2
83 978-3-642-20712-9
84 schema:name Computer Science – Theory and Applications
85 rdf:type schema:Book
86 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
87 schema:name Information and Computing Sciences
88 rdf:type schema:DefinedTerm
89 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
90 schema:name Computation Theory and Mathematics
91 rdf:type schema:DefinedTerm
92 sg:person.014237551615.24 schema:affiliation grid-institutes:grid.9647.c
93 schema:familyName Mathissen
94 schema:givenName Christian
95 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014237551615.24
96 rdf:type schema:Person
97 sg:person.015611460437.34 schema:affiliation grid-institutes:grid.9647.c
98 schema:familyName Lohrey
99 schema:givenName Markus
100 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015611460437.34
101 rdf:type schema:Person
102 grid-institutes:grid.9647.c schema:alternateName Institut für Informatik, Universität Leipzig, Germany
103 schema:name Institut für Informatik, Universität Leipzig, Germany
104 rdf:type schema:Organization
 




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


...