Ontology type: schema:Chapter
2007-01-01
AUTHORS ABSTRACTIt has recently been proved (Jeż, DLT 2007) that conjunctive grammars (that is, context-free grammars augmented by conjunction) generate some nonregular 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 nonexistence of an r.e. bound on the growth rate of generated languages. An essential step of the argument is a simulation of a cellular automaton recognizing positional notation of numbers using language equations. More... »
PAGES168-181
Computer Science – Theory and Applications
ISBN
978-3-540-74509-9
978-3-540-74510-5
http://scigraph.springernature.com/pub.10.1007/978-3-540-74510-5_19
DOIhttp://dx.doi.org/10.1007/978-3-540-74510-5_19
DIMENSIONShttps://app.dimensions.ai/details/publication/pub.1001931609
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/20",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Language, Communication and Culture",
"type": "DefinedTerm"
},
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/2004",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Linguistics",
"type": "DefinedTerm"
}
],
"author": [
{
"affiliation": {
"alternateName": "Institute of Computer Science, University of Wroc\u0142aw, Poland",
"id": "http://www.grid.ac/institutes/grid.8505.8",
"name": [
"Institute of Computer Science, University of 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, Finland",
"id": "http://www.grid.ac/institutes/grid.1374.1",
"name": [
"Academy of, Finland",
"Department of Mathematics, University of 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"
}
],
"datePublished": "2007-01-01",
"datePublishedReg": "2007-01-01",
"description": "It has recently been proved (Je\u017c, DLT 2007) that conjunctive grammars (that is, context-free grammars augmented by conjunction) generate some nonregular 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 nonexistence of an r.e. bound on the growth rate of generated languages. An essential step of the argument is a simulation of a cellular automaton recognizing positional notation of numbers using language equations.",
"editor": [
{
"familyName": "Diekert",
"givenName": "Volker",
"type": "Person"
},
{
"familyName": "Volkov",
"givenName": "Mikhail V.",
"type": "Person"
},
{
"familyName": "Voronkov",
"givenName": "Andrei",
"type": "Person"
}
],
"genre": "chapter",
"id": "sg:pub.10.1007/978-3-540-74510-5_19",
"inLanguage": "en",
"isAccessibleForFree": false,
"isPartOf": {
"isbn": [
"978-3-540-74509-9",
"978-3-540-74510-5"
],
"name": "Computer Science \u2013 Theory and Applications",
"type": "Book"
},
"keywords": [
"conjunctive grammars",
"one-letter alphabet",
"grammar",
"nonregular languages",
"unary languages",
"language equations",
"unary alphabet",
"language",
"alphabet",
"positional notation",
"undecidability",
"argument",
"present paper",
"notation",
"automata",
"class",
"paper",
"number",
"problem",
"decision problem",
"nonexistence",
"results",
"large class",
"essential step",
"step",
"unbounded growth",
"growth",
"cellular automata",
"growth rate",
"rate",
"simulations",
"equations"
],
"name": "Conjunctive Grammars over a Unary Alphabet: Undecidability and Unbounded Growth",
"pagination": "168-181",
"productId": [
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1001931609"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/978-3-540-74510-5_19"
]
}
],
"publisher": {
"name": "Springer Nature",
"type": "Organisation"
},
"sameAs": [
"https://doi.org/10.1007/978-3-540-74510-5_19",
"https://app.dimensions.ai/details/publication/pub.1001931609"
],
"sdDataset": "chapters",
"sdDatePublished": "2022-05-10T10:47",
"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/chapter/chapter_334.jsonl",
"type": "Chapter",
"url": "https://doi.org/10.1007/978-3-540-74510-5_19"
}
]
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-540-74510-5_19'
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-540-74510-5_19'
Turtle is a human-readable linked data format.
curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-74510-5_19'
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-540-74510-5_19'
This table displays all metadata directly associated to this object as RDF triples.
113 TRIPLES
23 PREDICATES
57 URIs
50 LITERALS
7 BLANK NODES