Ontology type: schema:ScholarlyArticle
2008-08-21
AUTHORS ABSTRACTIt has recently been proved (Jeż, DLT 2007) that conjunctive grammars (that is, context-free grammars augmented by conjunction) generate some non-regular languages over a one-letter alphabet. The present paper improves this result by constructing conjunctive grammars for a larger class of unary languages. The results imply undecidability of a number of decision problems of unary conjunctive grammars, as well as non-existence of a recursive function bounding the growth rate of the generated languages. An essential step of the argument is a simulation of a cellular automaton recognizing positional notation of numbers using language equations. More... »
PAGES27
http://scigraph.springernature.com/pub.10.1007/s00224-008-9139-5
DOIhttp://dx.doi.org/10.1007/s00224-008-9139-5
DIMENSIONShttps://app.dimensions.ai/details/publication/pub.1032338044
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": "Academy of Finland, Helsinki, Finland",
"id": "http://www.grid.ac/institutes/grid.15098.35",
"name": [
"Department of Mathematics, University of Turku, Turku, Finland",
"Academy of Finland, Helsinki, 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.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-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/11779148_38",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1033516850",
"https://doi.org/10.1007/11779148_38"
],
"type": "CreativeWork"
}
],
"datePublished": "2008-08-21",
"datePublishedReg": "2008-08-21",
"description": "It has recently been proved (Je\u017c, DLT 2007) that conjunctive grammars (that is, context-free grammars augmented by conjunction) generate some non-regular languages over a one-letter alphabet. The present paper improves this result by constructing conjunctive grammars for a larger class of unary languages. The results imply undecidability of a number of decision problems of unary conjunctive grammars, as well as non-existence of a recursive function bounding the growth rate of the generated languages. An essential step of the argument is a simulation of a cellular automaton recognizing positional notation of numbers using language equations.",
"genre": "article",
"id": "sg:pub.10.1007/s00224-008-9139-5",
"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": "1",
"type": "PublicationIssue"
},
{
"type": "PublicationVolume",
"volumeNumber": "46"
}
],
"keywords": [
"conjunctive grammars",
"non-regular languages",
"one-letter alphabet",
"unary languages",
"language equations",
"grammar",
"unary alphabet",
"language",
"alphabet",
"positional notation",
"undecidability",
"argument",
"recursive functions",
"present paper",
"notation",
"automata",
"class",
"paper",
"problem",
"number",
"decision problem",
"results",
"step",
"large class",
"essential step",
"unbounded growth",
"function",
"growth",
"cellular automata",
"rate",
"growth rate",
"simulations",
"equations"
],
"name": "Conjunctive Grammars over a Unary Alphabet: Undecidability and Unbounded Growth",
"pagination": "27",
"productId": [
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1032338044"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/s00224-008-9139-5"
]
}
],
"sameAs": [
"https://doi.org/10.1007/s00224-008-9139-5",
"https://app.dimensions.ai/details/publication/pub.1032338044"
],
"sdDataset": "articles",
"sdDatePublished": "2022-05-20T07:24",
"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_470.jsonl",
"type": "ScholarlyArticle",
"url": "https://doi.org/10.1007/s00224-008-9139-5"
}
]
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-008-9139-5'
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-008-9139-5'
Turtle is a human-readable linked data format.
curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00224-008-9139-5'
RDF/XML is a standard XML format for linked data.
curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00224-008-9139-5'
This table displays all metadata directly associated to this object as RDF triples.
126 TRIPLES
22 PREDICATES
64 URIs
50 LITERALS
6 BLANK NODES