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


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2008-08-21

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

PAGES

27

References to SciGraph publications

  • 1997. Context-Free Languages and Pushdown Automata in HANDBOOK OF FORMAL LANGUAGES
  • 2006. Language Equations with Complementation in DEVELOPMENTS IN LANGUAGE THEORY
  • 2002-09. Conjunctive Grammars and Systems of Language Equations in PROGRAMMING AND COMPUTER SOFTWARE
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s00224-008-9139-5

    DOI

    http://dx.doi.org/10.1007/s00224-008-9139-5

    DIMENSIONS

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


    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/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.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"
          }, 
          {
            "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"
          }
        ], 
        "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-06-01T22:06", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-springernature-scigraph/baseset/20220601/entities/gbq_results/article/article_476.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

    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/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

    Subject Predicate Object
    1 sg:pub.10.1007/s00224-008-9139-5 schema:about anzsrc-for:01
    2 anzsrc-for:0102
    3 anzsrc-for:08
    4 anzsrc-for:0802
    5 anzsrc-for:0805
    6 schema:author N40d5283c945c4f64b6d3fa7f09f6448e
    7 schema:citation sg:pub.10.1007/11779148_38
    8 sg:pub.10.1007/978-3-642-59136-5_3
    9 sg:pub.10.1023/a:1020213411126
    10 schema:datePublished 2008-08-21
    11 schema:datePublishedReg 2008-08-21
    12 schema:description It 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.
    13 schema:genre article
    14 schema:inLanguage en
    15 schema:isAccessibleForFree false
    16 schema:isPartOf Nb0b301390edf4e13b506fb5d66e4c2ca
    17 Nde62a88157c2496d9ef993055528b3f1
    18 sg:journal.1052098
    19 schema:keywords alphabet
    20 argument
    21 automata
    22 cellular automata
    23 class
    24 conjunctive grammars
    25 decision problem
    26 equations
    27 essential step
    28 function
    29 grammar
    30 growth
    31 growth rate
    32 language
    33 language equations
    34 large class
    35 non-regular languages
    36 notation
    37 number
    38 one-letter alphabet
    39 paper
    40 positional notation
    41 present paper
    42 problem
    43 rate
    44 recursive functions
    45 results
    46 simulations
    47 step
    48 unary alphabet
    49 unary languages
    50 unbounded growth
    51 undecidability
    52 schema:name Conjunctive Grammars over a Unary Alphabet: Undecidability and Unbounded Growth
    53 schema:pagination 27
    54 schema:productId Ne125e9b34e7843039608f6af6c1b0248
    55 Nf632c458908b4fc696f13fceed44f27a
    56 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032338044
    57 https://doi.org/10.1007/s00224-008-9139-5
    58 schema:sdDatePublished 2022-06-01T22:06
    59 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    60 schema:sdPublisher N265ae46bf0164828b0dfc6cf3a3c8ec2
    61 schema:url https://doi.org/10.1007/s00224-008-9139-5
    62 sgo:license sg:explorer/license/
    63 sgo:sdDataset articles
    64 rdf:type schema:ScholarlyArticle
    65 N265ae46bf0164828b0dfc6cf3a3c8ec2 schema:name Springer Nature - SN SciGraph project
    66 rdf:type schema:Organization
    67 N2c0641fb8e5d436cbcba942ffa8fda66 rdf:first sg:person.012144356031.48
    68 rdf:rest rdf:nil
    69 N40d5283c945c4f64b6d3fa7f09f6448e rdf:first sg:person.015252371751.76
    70 rdf:rest N2c0641fb8e5d436cbcba942ffa8fda66
    71 Nb0b301390edf4e13b506fb5d66e4c2ca schema:volumeNumber 46
    72 rdf:type schema:PublicationVolume
    73 Nde62a88157c2496d9ef993055528b3f1 schema:issueNumber 1
    74 rdf:type schema:PublicationIssue
    75 Ne125e9b34e7843039608f6af6c1b0248 schema:name dimensions_id
    76 schema:value pub.1032338044
    77 rdf:type schema:PropertyValue
    78 Nf632c458908b4fc696f13fceed44f27a schema:name doi
    79 schema:value 10.1007/s00224-008-9139-5
    80 rdf:type schema:PropertyValue
    81 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
    82 schema:name Mathematical Sciences
    83 rdf:type schema:DefinedTerm
    84 anzsrc-for:0102 schema:inDefinedTermSet anzsrc-for:
    85 schema:name Applied Mathematics
    86 rdf:type schema:DefinedTerm
    87 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    88 schema:name Information and Computing Sciences
    89 rdf:type schema:DefinedTerm
    90 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    91 schema:name Computation Theory and Mathematics
    92 rdf:type schema:DefinedTerm
    93 anzsrc-for:0805 schema:inDefinedTermSet anzsrc-for:
    94 schema:name Distributed Computing
    95 rdf:type schema:DefinedTerm
    96 sg:journal.1052098 schema:issn 1432-4350
    97 1433-0490
    98 schema:name Theory of Computing Systems
    99 schema:publisher Springer Nature
    100 rdf:type schema:Periodical
    101 sg:person.012144356031.48 schema:affiliation grid-institutes:grid.15098.35
    102 schema:familyName Okhotin
    103 schema:givenName Alexander
    104 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012144356031.48
    105 rdf:type schema:Person
    106 sg:person.015252371751.76 schema:affiliation grid-institutes:grid.8505.8
    107 schema:familyName Jeż
    108 schema:givenName Artur
    109 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015252371751.76
    110 rdf:type schema:Person
    111 sg:pub.10.1007/11779148_38 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033516850
    112 https://doi.org/10.1007/11779148_38
    113 rdf:type schema:CreativeWork
    114 sg:pub.10.1007/978-3-642-59136-5_3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012827682
    115 https://doi.org/10.1007/978-3-642-59136-5_3
    116 rdf:type schema:CreativeWork
    117 sg:pub.10.1023/a:1020213411126 schema:sameAs https://app.dimensions.ai/details/publication/pub.1029601870
    118 https://doi.org/10.1023/a:1020213411126
    119 rdf:type schema:CreativeWork
    120 grid-institutes:grid.15098.35 schema:alternateName Academy of Finland, Helsinki, Finland
    121 schema:name Academy of Finland, Helsinki, Finland
    122 Department of Mathematics, University of Turku, Turku, Finland
    123 rdf:type schema:Organization
    124 grid-institutes:grid.8505.8 schema:alternateName Institute of Computer Science, University of Wrocław, Wrocław, Poland
    125 schema:name Institute of Computer Science, University of Wrocław, Wrocław, Poland
    126 rdf:type schema:Organization
     




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


    ...