Conjunctive Grammars over a Unary Alphabet: Undecidability and Unbounded Growth View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2007-01-01

AUTHORS

Artur Jeż , Alexander Okhotin

ABSTRACT

It 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... »

PAGES

168-181

Book

TITLE

Computer Science – Theory and Applications

ISBN

978-3-540-74509-9
978-3-540-74510-5

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-540-74510-5_19

DOI

http://dx.doi.org/10.1007/978-3-540-74510-5_19

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1001931609


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

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

HOW TO GET THIS DATA PROGRAMMATICALLY:

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

Subject Predicate Object
1 sg:pub.10.1007/978-3-540-74510-5_19 schema:about anzsrc-for:20
2 anzsrc-for:2004
3 schema:author N3463d2937ee44dfba6275c9bc1ecd816
4 schema:datePublished 2007-01-01
5 schema:datePublishedReg 2007-01-01
6 schema:description It 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.
7 schema:editor Na25158594c374a3ab69c01bf256ca14c
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N31f73047996a4ae691e15c9eb7eccef5
12 schema:keywords alphabet
13 argument
14 automata
15 cellular automata
16 class
17 conjunctive grammars
18 decision problem
19 equations
20 essential step
21 grammar
22 growth
23 growth rate
24 language
25 language equations
26 large class
27 nonexistence
28 nonregular languages
29 notation
30 number
31 one-letter alphabet
32 paper
33 positional notation
34 present paper
35 problem
36 rate
37 results
38 simulations
39 step
40 unary alphabet
41 unary languages
42 unbounded growth
43 undecidability
44 schema:name Conjunctive Grammars over a Unary Alphabet: Undecidability and Unbounded Growth
45 schema:pagination 168-181
46 schema:productId N28362e00acb842f7a73f7af27f600714
47 Nd84eb6a4b0a0413b9ac7b01fe2db45b5
48 schema:publisher Nf09c0c5a4696438c9061ad3cdca2f59e
49 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001931609
50 https://doi.org/10.1007/978-3-540-74510-5_19
51 schema:sdDatePublished 2022-05-10T10:47
52 schema:sdLicense https://scigraph.springernature.com/explorer/license/
53 schema:sdPublisher N438401e3655a4cb8824bc200d35cee64
54 schema:url https://doi.org/10.1007/978-3-540-74510-5_19
55 sgo:license sg:explorer/license/
56 sgo:sdDataset chapters
57 rdf:type schema:Chapter
58 N28362e00acb842f7a73f7af27f600714 schema:name doi
59 schema:value 10.1007/978-3-540-74510-5_19
60 rdf:type schema:PropertyValue
61 N31f73047996a4ae691e15c9eb7eccef5 schema:isbn 978-3-540-74509-9
62 978-3-540-74510-5
63 schema:name Computer Science – Theory and Applications
64 rdf:type schema:Book
65 N3463d2937ee44dfba6275c9bc1ecd816 rdf:first sg:person.015252371751.76
66 rdf:rest Nf0aa2a610b75414aad82762938d9e0b5
67 N438401e3655a4cb8824bc200d35cee64 schema:name Springer Nature - SN SciGraph project
68 rdf:type schema:Organization
69 N6222240bf2154c069efc44550ac9adcb rdf:first Nf34eb4d942c144e0a4f837a89861a0b9
70 rdf:rest rdf:nil
71 Na25158594c374a3ab69c01bf256ca14c rdf:first Nec386bead0cd4f2aa577e917dba00d04
72 rdf:rest Nff8ddddf73264ec681b17d7a7530f8b3
73 Naad624ea665c4f2f8224e6118f72380e schema:familyName Volkov
74 schema:givenName Mikhail V.
75 rdf:type schema:Person
76 Nd84eb6a4b0a0413b9ac7b01fe2db45b5 schema:name dimensions_id
77 schema:value pub.1001931609
78 rdf:type schema:PropertyValue
79 Nec386bead0cd4f2aa577e917dba00d04 schema:familyName Diekert
80 schema:givenName Volker
81 rdf:type schema:Person
82 Nf09c0c5a4696438c9061ad3cdca2f59e schema:name Springer Nature
83 rdf:type schema:Organisation
84 Nf0aa2a610b75414aad82762938d9e0b5 rdf:first sg:person.012144356031.48
85 rdf:rest rdf:nil
86 Nf34eb4d942c144e0a4f837a89861a0b9 schema:familyName Voronkov
87 schema:givenName Andrei
88 rdf:type schema:Person
89 Nff8ddddf73264ec681b17d7a7530f8b3 rdf:first Naad624ea665c4f2f8224e6118f72380e
90 rdf:rest N6222240bf2154c069efc44550ac9adcb
91 anzsrc-for:20 schema:inDefinedTermSet anzsrc-for:
92 schema:name Language, Communication and Culture
93 rdf:type schema:DefinedTerm
94 anzsrc-for:2004 schema:inDefinedTermSet anzsrc-for:
95 schema:name Linguistics
96 rdf:type schema:DefinedTerm
97 sg:person.012144356031.48 schema:affiliation grid-institutes:grid.1374.1
98 schema:familyName Okhotin
99 schema:givenName Alexander
100 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012144356031.48
101 rdf:type schema:Person
102 sg:person.015252371751.76 schema:affiliation grid-institutes:grid.8505.8
103 schema:familyName Jeż
104 schema:givenName Artur
105 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015252371751.76
106 rdf:type schema:Person
107 grid-institutes:grid.1374.1 schema:alternateName Department of Mathematics, University of Turku, Finland
108 schema:name Academy of, Finland
109 Department of Mathematics, University of Turku, Finland
110 rdf:type schema:Organization
111 grid-institutes:grid.8505.8 schema:alternateName Institute of Computer Science, University of Wrocław, Poland
112 schema:name Institute of Computer Science, University of Wrocław, Poland
113 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...