Ontology type: schema:Chapter Open Access: True
2011
AUTHORSMarkus Lohrey , Christian Mathissen
ABSTRACTThe 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... »
PAGES275-288
Computer Science – Theory and Applications
ISBN
978-3-642-20711-2
978-3-642-20712-9
http://scigraph.springernature.com/pub.10.1007/978-3-642-20712-9_21
DOIhttp://dx.doi.org/10.1007/978-3-642-20712-9_21
DIMENSIONShttps://app.dimensions.ai/details/publication/pub.1012277274
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
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