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 Nc031ddc5fc814a698efb44b5145da514
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 Nbb23a534793644c29b8829ef03906944
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N61d8173ef5694c8396471cb1fe19431e
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 N0e8284f1711f42dca3bae76c87e7078b
47 N470911712d314ffc8e370675744bc306
48 schema:publisher Nb4bc9a5e69f747ae90c9c17cfb181213
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 N29ac948ea7924748b70ff9e64c9930da
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 N0e8284f1711f42dca3bae76c87e7078b schema:name doi
59 schema:value 10.1007/978-3-642-20712-9_21
60 rdf:type schema:PropertyValue
61 N29ac948ea7924748b70ff9e64c9930da schema:name Springer Nature - SN SciGraph project
62 rdf:type schema:Organization
63 N470911712d314ffc8e370675744bc306 schema:name dimensions_id
64 schema:value pub.1012277274
65 rdf:type schema:PropertyValue
66 N61d8173ef5694c8396471cb1fe19431e schema:isbn 978-3-642-20711-2
67 978-3-642-20712-9
68 schema:name Computer Science – Theory and Applications
69 rdf:type schema:Book
70 N7a81164c2ce6482e85bcd3edb7859ba9 rdf:first Nd4ad42dd4d19438daeef2f3c4afbed03
71 rdf:rest rdf:nil
72 Nb4bc9a5e69f747ae90c9c17cfb181213 schema:name Springer Nature
73 rdf:type schema:Organisation
74 Nbb23a534793644c29b8829ef03906944 rdf:first Ncd6ed0a5d05140bd8d72b9bb6ca79e7d
75 rdf:rest N7a81164c2ce6482e85bcd3edb7859ba9
76 Nc031ddc5fc814a698efb44b5145da514 rdf:first sg:person.015611460437.34
77 rdf:rest Nc98393d8ed0944fbb714b0a693e4af82
78 Nc98393d8ed0944fbb714b0a693e4af82 rdf:first sg:person.014237551615.24
79 rdf:rest rdf:nil
80 Ncd6ed0a5d05140bd8d72b9bb6ca79e7d schema:familyName Kulikov
81 schema:givenName Alexander
82 rdf:type schema:Person
83 Nd4ad42dd4d19438daeef2f3c4afbed03 schema:familyName Vereshchagin
84 schema:givenName Nikolay
85 rdf:type schema:Person
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)


...