One-Nonterminal Conjunctive Grammars over a Unary Alphabet View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2011-03-10

AUTHORS

Artur Jeż, Alexander Okhotin

ABSTRACT

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

PAGES

319-342

References to SciGraph publications

  • 2007-10-05. The Complexity of Membership Problems for Circuits Over Sets of Natural Numbers in COMPUTATIONAL COMPLEXITY
  • 2002-09. Conjunctive Grammars and Systems of Language Equations in PROGRAMMING AND COMPUTER SOFTWARE
  • 2009-12-23. Complexity of Equations over Sets of Natural Numbers in THEORY OF COMPUTING SYSTEMS
  • 1997. Context-Free Languages and Pushdown Automata in HANDBOOK OF FORMAL LANGUAGES
  • 2010. On Language Equations XXK = XXL and XM = N over a Unary Alphabet in DEVELOPMENTS IN LANGUAGE THEORY
  • 2010. Fast Parsing for Boolean Grammars: A Generalization of Valiant’s Algorithm in DEVELOPMENTS IN LANGUAGE THEORY
  • 2007-04-27. Recursive descent parsing for Boolean grammars in ACTA INFORMATICA
  • 2008-01-01. On the expressive power of univariate equations over sets of natural numbers in FIFTH IFIP INTERNATIONAL CONFERENCE ON THEORETICAL COMPUTER SCIENCE – TCS 2008
  • 2008-08-21. Conjunctive Grammars over a Unary Alphabet: Undecidability and Unbounded Growth in THEORY OF COMPUTING SYSTEMS
  • 2007-01-01. What Do We Know About Language Equations? in DEVELOPMENTS IN LANGUAGE THEORY
  • 1999. Complexity of Language Recognition Problems for Compressed Words in JEWELS ARE FOREVER
  • 2008-01-01. On the Computational Completeness of Equations over Sets of Natural Numbers in AUTOMATA, LANGUAGES AND PROGRAMMING
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s00224-011-9319-6

    DOI

    http://dx.doi.org/10.1007/s00224-011-9319-6

    DIMENSIONS

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


    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": "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

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

    Subject Predicate Object
    1 sg:pub.10.1007/s00224-011-9319-6 schema:about anzsrc-for:01
    2 anzsrc-for:0102
    3 anzsrc-for:08
    4 anzsrc-for:0802
    5 anzsrc-for:0805
    6 schema:author N798ae3a2e167481eb0bd7c2257b4e6c6
    7 schema:citation sg:pub.10.1007/978-0-387-09680-3_15
    8 sg:pub.10.1007/978-3-540-70583-3_6
    9 sg:pub.10.1007/978-3-540-73208-2_3
    10 sg:pub.10.1007/978-3-642-14455-4_27
    11 sg:pub.10.1007/978-3-642-14455-4_31
    12 sg:pub.10.1007/978-3-642-59136-5_3
    13 sg:pub.10.1007/978-3-642-60207-8_23
    14 sg:pub.10.1007/s00037-007-0229-6
    15 sg:pub.10.1007/s00224-008-9139-5
    16 sg:pub.10.1007/s00224-009-9246-y
    17 sg:pub.10.1007/s00236-007-0045-0
    18 sg:pub.10.1023/a:1020213411126
    19 schema:datePublished 2011-03-10
    20 schema:datePublishedReg 2011-03-10
    21 schema:description Conjunctive 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.
    22 schema:genre article
    23 schema:inLanguage en
    24 schema:isAccessibleForFree false
    25 schema:isPartOf N533cba1edd60442c83b6aaf7ec94b277
    26 N75c9704b3a7a4a058fed1ec9ab25c8c0
    27 sg:journal.1052098
    28 schema:keywords NLOGSPACE
    29 NPs
    30 Union
    31 addition
    32 alphabet
    33 cases
    34 conjunctive grammars
    35 construction
    36 context-free grammars
    37 equations
    38 equivalence
    39 equivalence problem
    40 finiteness
    41 focus
    42 grammar
    43 intersection
    44 language
    45 membership problem
    46 modification
    47 natural numbers
    48 nonterminal symbols
    49 nonterminals
    50 notation
    51 number
    52 positional notation
    53 problem
    54 same problem
    55 set
    56 slight modification
    57 special case
    58 symbols
    59 unary alphabet
    60 unary languages
    61 schema:name One-Nonterminal Conjunctive Grammars over a Unary Alphabet
    62 schema:pagination 319-342
    63 schema:productId N5aefc7f7d7ac409ca0a694b2d6c50148
    64 Naae021f787bc4a7d960864c3d6a3d378
    65 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047527460
    66 https://doi.org/10.1007/s00224-011-9319-6
    67 schema:sdDatePublished 2022-05-20T07:26
    68 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    69 schema:sdPublisher Neb8ead1afd444a6da7554c69f9f243d3
    70 schema:url https://doi.org/10.1007/s00224-011-9319-6
    71 sgo:license sg:explorer/license/
    72 sgo:sdDataset articles
    73 rdf:type schema:ScholarlyArticle
    74 N533cba1edd60442c83b6aaf7ec94b277 schema:volumeNumber 49
    75 rdf:type schema:PublicationVolume
    76 N5aefc7f7d7ac409ca0a694b2d6c50148 schema:name doi
    77 schema:value 10.1007/s00224-011-9319-6
    78 rdf:type schema:PropertyValue
    79 N75c9704b3a7a4a058fed1ec9ab25c8c0 schema:issueNumber 2
    80 rdf:type schema:PublicationIssue
    81 N798ae3a2e167481eb0bd7c2257b4e6c6 rdf:first sg:person.015252371751.76
    82 rdf:rest N7b0ec12718744b6bba6dac201798a971
    83 N7b0ec12718744b6bba6dac201798a971 rdf:first sg:person.012144356031.48
    84 rdf:rest rdf:nil
    85 Naae021f787bc4a7d960864c3d6a3d378 schema:name dimensions_id
    86 schema:value pub.1047527460
    87 rdf:type schema:PropertyValue
    88 Neb8ead1afd444a6da7554c69f9f243d3 schema:name Springer Nature - SN SciGraph project
    89 rdf:type schema:Organization
    90 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
    91 schema:name Mathematical Sciences
    92 rdf:type schema:DefinedTerm
    93 anzsrc-for:0102 schema:inDefinedTermSet anzsrc-for:
    94 schema:name Applied Mathematics
    95 rdf:type schema:DefinedTerm
    96 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    97 schema:name Information and Computing Sciences
    98 rdf:type schema:DefinedTerm
    99 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    100 schema:name Computation Theory and Mathematics
    101 rdf:type schema:DefinedTerm
    102 anzsrc-for:0805 schema:inDefinedTermSet anzsrc-for:
    103 schema:name Distributed Computing
    104 rdf:type schema:DefinedTerm
    105 sg:journal.1052098 schema:issn 1432-4350
    106 1433-0490
    107 schema:name Theory of Computing Systems
    108 schema:publisher Springer Nature
    109 rdf:type schema:Periodical
    110 sg:person.012144356031.48 schema:affiliation grid-institutes:grid.1374.1
    111 schema:familyName Okhotin
    112 schema:givenName Alexander
    113 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012144356031.48
    114 rdf:type schema:Person
    115 sg:person.015252371751.76 schema:affiliation grid-institutes:grid.8505.8
    116 schema:familyName Jeż
    117 schema:givenName Artur
    118 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015252371751.76
    119 rdf:type schema:Person
    120 sg:pub.10.1007/978-0-387-09680-3_15 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032518557
    121 https://doi.org/10.1007/978-0-387-09680-3_15
    122 rdf:type schema:CreativeWork
    123 sg:pub.10.1007/978-3-540-70583-3_6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009467480
    124 https://doi.org/10.1007/978-3-540-70583-3_6
    125 rdf:type schema:CreativeWork
    126 sg:pub.10.1007/978-3-540-73208-2_3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021196966
    127 https://doi.org/10.1007/978-3-540-73208-2_3
    128 rdf:type schema:CreativeWork
    129 sg:pub.10.1007/978-3-642-14455-4_27 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036694593
    130 https://doi.org/10.1007/978-3-642-14455-4_27
    131 rdf:type schema:CreativeWork
    132 sg:pub.10.1007/978-3-642-14455-4_31 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038831194
    133 https://doi.org/10.1007/978-3-642-14455-4_31
    134 rdf:type schema:CreativeWork
    135 sg:pub.10.1007/978-3-642-59136-5_3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012827682
    136 https://doi.org/10.1007/978-3-642-59136-5_3
    137 rdf:type schema:CreativeWork
    138 sg:pub.10.1007/978-3-642-60207-8_23 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050084589
    139 https://doi.org/10.1007/978-3-642-60207-8_23
    140 rdf:type schema:CreativeWork
    141 sg:pub.10.1007/s00037-007-0229-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001544925
    142 https://doi.org/10.1007/s00037-007-0229-6
    143 rdf:type schema:CreativeWork
    144 sg:pub.10.1007/s00224-008-9139-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032338044
    145 https://doi.org/10.1007/s00224-008-9139-5
    146 rdf:type schema:CreativeWork
    147 sg:pub.10.1007/s00224-009-9246-y schema:sameAs https://app.dimensions.ai/details/publication/pub.1003872386
    148 https://doi.org/10.1007/s00224-009-9246-y
    149 rdf:type schema:CreativeWork
    150 sg:pub.10.1007/s00236-007-0045-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013565946
    151 https://doi.org/10.1007/s00236-007-0045-0
    152 rdf:type schema:CreativeWork
    153 sg:pub.10.1023/a:1020213411126 schema:sameAs https://app.dimensions.ai/details/publication/pub.1029601870
    154 https://doi.org/10.1023/a:1020213411126
    155 rdf:type schema:CreativeWork
    156 grid-institutes:grid.1374.1 schema:alternateName Department of Mathematics, University of Turku, Turku, Finland
    157 schema:name Department of Mathematics, University of Turku, Turku, Finland
    158 rdf:type schema:Organization
    159 grid-institutes:grid.8505.8 schema:alternateName Institute of Computer Science, University of Wrocław, Wrocław, Poland
    160 schema:name Institute of Computer Science, University of Wrocław, Wrocław, Poland
    161 rdf:type schema:Organization
     




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


    ...