Ontology type: schema:ScholarlyArticle Open Access: True
2013-01-18
AUTHORS ABSTRACTIn this paper, a compressed membership problem for finite automata, both deterministic (DFAs) and non-deterministic (NFAs), with compressed transition labels is studied. The compression is represented by straight-line programs (SLPs), i.e. context-free grammars generating exactly one string. A novel technique of dealing with SLPs is employed: the SLPs are recompressed, so that substrings of the input word are encoded in SLPs labelling the transitions of the NFA (DFA) in the same way, as in the SLP representing the input text. To this end, the SLPs are locally decompressed and then recompressed in a uniform way. Furthermore, in order to reflect the recompression in the NFA, we need to modify it only a little, in particular its size stays polynomial in the input size.Using this technique it is shown that the compressed membership for NFA with compressed labels is in NP, thus confirming the conjecture of Plandowski and Rytter (Jewels Are Forever, pp. 262–272, Springer, Berlin, 1999) and extending the partial result of Lohrey and Mathissen (in CSR, LNCS, vol. 6651, pp. 275–288, Springer, Berlin, 2011); as this problem is known to be NP-hard (in Plandowski and Rytter, Jewels Are Forever, pp. 262–272, Springer, Berlin, 1999), we settle its exact computational complexity. Moreover, the same technique applied to the compressed membership for DFA with compressed labels yields that this problem is in P, and this problem is known to be P-hard (in Markey and Schnoebelen, Inf. Process. Lett. 90(1):3–6, 2004; Beaudry et al., SIAM J. Comput. 26(1):138–152, 1997). More... »
PAGES685-718
http://scigraph.springernature.com/pub.10.1007/s00224-013-9443-6
DOIhttp://dx.doi.org/10.1007/s00224-013-9443-6
DIMENSIONShttps://app.dimensions.ai/details/publication/pub.1049189041
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": "Institute of Computer Science, University of Wroc\u0142aw, ul. Joliot-Curie 15, 50-383, Wroc\u0142aw, Poland",
"id": "http://www.grid.ac/institutes/grid.8505.8",
"name": [
"Max Planck Institute f\u00fcr Informatik, Campus E1 4, 66123, Saarbr\u00fccken, Germany",
"Institute of Computer Science, University of Wroc\u0142aw, ul. Joliot-Curie 15, 50-383, Wroc\u0142aw, Poland"
],
"type": "Organization"
},
"familyName": "Je\u017c",
"givenName": "Artur",
"id": "sg:person.015252371751.76",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015252371751.76"
],
"type": "Person"
}
],
"citation": [
{
"id": "sg:pub.10.1007/bfb0049431",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1036904640",
"https://doi.org/10.1007/bfb0049431"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-642-20712-9_21",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1012277274",
"https://doi.org/10.1007/978-3-642-20712-9_21"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/s00224-007-9054-1",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1028694588",
"https://doi.org/10.1007/s00224-007-9054-1"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/11821069_56",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1016750099",
"https://doi.org/10.1007/11821069_56"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-540-74510-5_26",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1031210348",
"https://doi.org/10.1007/978-3-540-74510-5_26"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/3-540-61258-0_3",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1034452299",
"https://doi.org/10.1007/3-540-61258-0_3"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/3-540-61422-2_148",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1003581531",
"https://doi.org/10.1007/3-540-61422-2_148"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-642-31594-7_45",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1026589735",
"https://doi.org/10.1007/978-3-642-31594-7_45"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/3-540-60692-0_60",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1035086190",
"https://doi.org/10.1007/3-540-60692-0_60"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-642-23719-5_36",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1038685053",
"https://doi.org/10.1007/978-3-642-23719-5_36"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/bf02522825",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1007699916",
"https://doi.org/10.1007/bf02522825"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/bfb0055097",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1026190890",
"https://doi.org/10.1007/bfb0055097"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-642-60207-8_23",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1050084589",
"https://doi.org/10.1007/978-3-642-60207-8_23"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/11821069_59",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1020993578",
"https://doi.org/10.1007/11821069_59"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/s00224-011-9319-6",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1047527460",
"https://doi.org/10.1007/s00224-011-9319-6"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-642-31265-6_19",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1002667067",
"https://doi.org/10.1007/978-3-642-31265-6_19"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/s00224-009-9246-y",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1003872386",
"https://doi.org/10.1007/s00224-009-9246-y"
],
"type": "CreativeWork"
}
],
"datePublished": "2013-01-18",
"datePublishedReg": "2013-01-18",
"description": "In this paper, a compressed membership problem for finite automata, both deterministic (DFAs) and non-deterministic (NFAs), with compressed transition labels is studied. The compression is represented by straight-line programs (SLPs), i.e. context-free grammars generating exactly one string. A\u00a0novel technique of dealing with SLPs is employed: the SLPs are recompressed, so that substrings of the input word are encoded in SLPs labelling the transitions of the NFA (DFA) in the same way, as in the SLP representing the input text. To this end, the SLPs are locally decompressed and then recompressed in a uniform way. Furthermore, in order to reflect the recompression in the NFA, we need to modify it only a little, in particular its size stays polynomial in the input size.Using this technique it is shown that the compressed membership for NFA with compressed labels is in NP, thus confirming the conjecture of Plandowski and Rytter (Jewels Are Forever, pp. 262\u2013272, Springer, Berlin, 1999) and extending the partial result of Lohrey and Mathissen (in CSR, LNCS, vol. 6651, pp.\u00a0275\u2013288, Springer, Berlin, 2011); as this problem is known to be NP-hard (in Plandowski and Rytter, Jewels Are Forever, pp.\u00a0262\u2013272, Springer, Berlin, 1999), we settle its exact computational complexity. Moreover, the same technique applied to the compressed membership for DFA with compressed labels yields that this problem is in P, and this problem is known to be P-hard (in Markey and Schnoebelen, Inf. Process. Lett. 90(1):3\u20136, 2004; Beaudry et\u00a0al., SIAM J. Comput. 26(1):138\u2013152, 1997).",
"genre": "article",
"id": "sg:pub.10.1007/s00224-013-9443-6",
"inLanguage": "en",
"isAccessibleForFree": true,
"isPartOf": [
{
"id": "sg:journal.1052098",
"issn": [
"1432-4350",
"1433-0490"
],
"name": "Theory of Computing Systems",
"publisher": "Springer Nature",
"type": "Periodical"
},
{
"issueNumber": "4",
"type": "PublicationIssue"
},
{
"type": "PublicationVolume",
"volumeNumber": "55"
}
],
"keywords": [
"straight-line programs",
"exact computational complexity",
"finite automata",
"context-free grammars",
"input text",
"computational complexity",
"input size",
"membership problem",
"uniform way",
"input word",
"transition labels",
"automata",
"partial results",
"complexity",
"novel technique",
"NPs",
"labels",
"NFA",
"substrings",
"Lohrey",
"technique",
"Plandowski",
"Rytter",
"way",
"text",
"grammar",
"compression",
"strings",
"same way",
"recompression",
"words",
"same technique",
"DFA",
"membership",
"order",
"program",
"end",
"size",
"results",
"conjecture",
"transition",
"yield",
"problem",
"paper"
],
"name": "The Complexity of Compressed Membership Problems for Finite Automata",
"pagination": "685-718",
"productId": [
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1049189041"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/s00224-013-9443-6"
]
}
],
"sameAs": [
"https://doi.org/10.1007/s00224-013-9443-6",
"https://app.dimensions.ai/details/publication/pub.1049189041"
],
"sdDataset": "articles",
"sdDatePublished": "2022-05-10T10:06",
"sdLicense": "https://scigraph.springernature.com/explorer/license/",
"sdPublisher": {
"name": "Springer Nature - SN SciGraph project",
"type": "Organization"
},
"sdSource": "s3://com-springernature-scigraph/baseset/20220509/entities/gbq_results/article/article_606.jsonl",
"type": "ScholarlyArticle",
"url": "https://doi.org/10.1007/s00224-013-9443-6"
}
]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/s00224-013-9443-6'
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/s00224-013-9443-6'
Turtle is a human-readable linked data format.
curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00224-013-9443-6'
RDF/XML is a standard XML format for linked data.
curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00224-013-9443-6'
This table displays all metadata directly associated to this object as RDF triples.
171 TRIPLES
22 PREDICATES
86 URIs
61 LITERALS
6 BLANK NODES