Ontology type: schema:ScholarlyArticle
2011-03-10
AUTHORS ABSTRACTConjunctive grammars over an alphabet Σ={a} are studied, with the focus on the special case with a unique nonterminal symbol. Such a grammar is equivalent to an equation X=ϕ(X) over sets of natural numbers, using union, intersection and addition. It is shown that every grammar with multiple nonterminals can be encoded into a grammar with a single nonterminal, with a slight modification of the language. Based on this construction, the compressed membership problem for one-nonterminal conjunctive grammars over {a} is proved to be EXPTIME-complete; the same problem for the context-free grammars is decidable in NLOGSPACE, but becomes NP-complete if the grammar is compressed as well. The equivalence problem for these grammars is shown to be co-r.e.-complete, both finiteness and co-finiteness are r.e.-complete, while equivalence to a fixed unary language with a regular positional notation is decidable. More... »
PAGES319-342
http://scigraph.springernature.com/pub.10.1007/s00224-011-9319-6
DOIhttp://dx.doi.org/10.1007/s00224-011-9319-6
DIMENSIONShttps://app.dimensions.ai/details/publication/pub.1047527460
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/01",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Mathematical Sciences",
"type": "DefinedTerm"
},
{
"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/0102",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Applied Mathematics",
"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/0805",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Distributed Computing",
"type": "DefinedTerm"
}
],
"author": [
{
"affiliation": {
"alternateName": "Institute of Computer Science, University of Wroc\u0142aw, Wroc\u0142aw, Poland",
"id": "http://www.grid.ac/institutes/grid.8505.8",
"name": [
"Institute of Computer Science, University of Wroc\u0142aw, 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"
},
{
"affiliation": {
"alternateName": "Department of Mathematics, University of Turku, Turku, Finland",
"id": "http://www.grid.ac/institutes/grid.1374.1",
"name": [
"Department of Mathematics, University of Turku, Turku, Finland"
],
"type": "Organization"
},
"familyName": "Okhotin",
"givenName": "Alexander",
"id": "sg:person.012144356031.48",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012144356031.48"
],
"type": "Person"
}
],
"citation": [
{
"id": "sg:pub.10.1007/978-3-540-73208-2_3",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1021196966",
"https://doi.org/10.1007/978-3-540-73208-2_3"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-642-14455-4_27",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1036694593",
"https://doi.org/10.1007/978-3-642-14455-4_27"
],
"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"
},
{
"id": "sg:pub.10.1007/978-3-642-14455-4_31",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1038831194",
"https://doi.org/10.1007/978-3-642-14455-4_31"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1023/a:1020213411126",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1029601870",
"https://doi.org/10.1023/a:1020213411126"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-0-387-09680-3_15",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1032518557",
"https://doi.org/10.1007/978-0-387-09680-3_15"
],
"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/s00236-007-0045-0",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1013565946",
"https://doi.org/10.1007/s00236-007-0045-0"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/s00224-008-9139-5",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1032338044",
"https://doi.org/10.1007/s00224-008-9139-5"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-642-59136-5_3",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1012827682",
"https://doi.org/10.1007/978-3-642-59136-5_3"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/s00037-007-0229-6",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1001544925",
"https://doi.org/10.1007/s00037-007-0229-6"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-540-70583-3_6",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1009467480",
"https://doi.org/10.1007/978-3-540-70583-3_6"
],
"type": "CreativeWork"
}
],
"datePublished": "2011-03-10",
"datePublishedReg": "2011-03-10",
"description": "Conjunctive grammars over an alphabet \u03a3={a} are studied, with the focus on the special case with a unique nonterminal symbol. Such a grammar is equivalent to an equation X=\u03d5(X) over sets of natural numbers, using union, intersection and addition. It is shown that every grammar with multiple nonterminals can be encoded into a grammar with a single nonterminal, with a slight modification of the language. Based on this construction, the compressed membership problem for one-nonterminal conjunctive grammars over {a} is proved to be EXPTIME-complete; the same problem for the context-free grammars is decidable in NLOGSPACE, but becomes NP-complete if the grammar is compressed as well. The equivalence problem for these grammars is shown to be co-r.e.-complete, both finiteness and co-finiteness are r.e.-complete, while equivalence to a fixed unary language with a regular positional notation is decidable.",
"genre": "article",
"id": "sg:pub.10.1007/s00224-011-9319-6",
"inLanguage": "en",
"isAccessibleForFree": false,
"isPartOf": [
{
"id": "sg:journal.1052098",
"issn": [
"1432-4350",
"1433-0490"
],
"name": "Theory of Computing Systems",
"publisher": "Springer Nature",
"type": "Periodical"
},
{
"issueNumber": "2",
"type": "PublicationIssue"
},
{
"type": "PublicationVolume",
"volumeNumber": "49"
}
],
"keywords": [
"conjunctive grammars",
"grammar",
"context-free grammars",
"unary languages",
"unary alphabet",
"nonterminal symbols",
"nonterminals",
"language",
"alphabet",
"membership problem",
"positional notation",
"equivalence problem",
"symbols",
"intersection",
"NLOGSPACE",
"construction",
"focus",
"same problem",
"notation",
"Union",
"NPs",
"finiteness",
"equivalence",
"special case",
"set",
"natural numbers",
"slight modification",
"problem",
"number",
"cases",
"addition",
"modification",
"equations"
],
"name": "One-Nonterminal Conjunctive Grammars over a Unary Alphabet",
"pagination": "319-342",
"productId": [
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1047527460"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/s00224-011-9319-6"
]
}
],
"sameAs": [
"https://doi.org/10.1007/s00224-011-9319-6",
"https://app.dimensions.ai/details/publication/pub.1047527460"
],
"sdDataset": "articles",
"sdDatePublished": "2022-05-20T07:26",
"sdLicense": "https://scigraph.springernature.com/explorer/license/",
"sdPublisher": {
"name": "Springer Nature - SN SciGraph project",
"type": "Organization"
},
"sdSource": "s3://com-springernature-scigraph/baseset/20220519/entities/gbq_results/article/article_528.jsonl",
"type": "ScholarlyArticle",
"url": "https://doi.org/10.1007/s00224-011-9319-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-011-9319-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-011-9319-6'
Turtle is a human-readable linked data format.
curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00224-011-9319-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-011-9319-6'
This table displays all metadata directly associated to this object as RDF triples.
161 TRIPLES
22 PREDICATES
73 URIs
50 LITERALS
6 BLANK NODES