On the Number of Nonterminal Symbols in Unambiguous Conjunctive Grammars View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2012

AUTHORS

Artur Jeż , Alexander Okhotin

ABSTRACT

It is demonstrated that the family of languages generated by unambiguous conjunctive grammars with 1 nonterminal symbol is strictly included in the languages generated by 2-nonterminal grammars, which is in turn a proper subset of the family generated using 3 or more nonterminal symbols. This hierarchy is established by considering grammars over a one-letter alphabet, for which it is shown that 1-nonterminal grammars generate only regular languages, 2-nonterminal grammars generate some non-regular languages, but all of them have upper density zero, while 3-nonterminal grammars may generate some non-regular languages of non-zero density. It is also shown that the equivalence problem for 2-nonterminal grammars is undecidable. More... »

PAGES

183-195

Book

TITLE

Descriptional Complexity of Formal Systems

ISBN

978-3-642-31622-7
978-3-642-31623-4

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-31623-4_14

DOI

http://dx.doi.org/10.1007/978-3-642-31623-4_14

DIMENSIONS

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


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": [
            "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": "2012", 
    "datePublishedReg": "2012-01-01", 
    "description": "It is demonstrated that the family of languages generated by unambiguous conjunctive grammars with 1 nonterminal symbol is strictly included in the languages generated by 2-nonterminal grammars, which is in turn a proper subset of the family generated using 3 or more nonterminal symbols. This hierarchy is established by considering grammars over a one-letter alphabet, for which it is shown that 1-nonterminal grammars generate only regular languages, 2-nonterminal grammars generate some non-regular languages, but all of them have upper density zero, while 3-nonterminal grammars may generate some non-regular languages of non-zero density. It is also shown that the equivalence problem for 2-nonterminal grammars is undecidable.", 
    "editor": [
      {
        "familyName": "Kutrib", 
        "givenName": "Martin", 
        "type": "Person"
      }, 
      {
        "familyName": "Moreira", 
        "givenName": "Nelma", 
        "type": "Person"
      }, 
      {
        "familyName": "Reis", 
        "givenName": "Rog\u00e9rio", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-31623-4_14", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-642-31622-7", 
        "978-3-642-31623-4"
      ], 
      "name": "Descriptional Complexity of Formal Systems", 
      "type": "Book"
    }, 
    "keywords": [
      "non-regular languages", 
      "nonterminal symbols", 
      "conjunctive grammars", 
      "family of languages", 
      "one-letter alphabet", 
      "regular languages", 
      "grammar", 
      "language", 
      "symbols", 
      "equivalence problem", 
      "alphabet", 
      "hierarchy", 
      "proper subset", 
      "turn", 
      "family", 
      "problem", 
      "number", 
      "subset", 
      "zeros", 
      "density", 
      "density zero"
    ], 
    "name": "On the Number of Nonterminal Symbols in Unambiguous Conjunctive Grammars", 
    "pagination": "183-195", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1017627177"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-31623-4_14"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-31623-4_14", 
      "https://app.dimensions.ai/details/publication/pub.1017627177"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-20T07:47", 
    "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/chapter/chapter_390.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-31623-4_14"
  }
]
 

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-642-31623-4_14'

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-642-31623-4_14'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-31623-4_14'

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-642-31623-4_14'


 

This table displays all metadata directly associated to this object as RDF triples.

101 TRIPLES      23 PREDICATES      47 URIs      40 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-31623-4_14 schema:about anzsrc-for:20
2 anzsrc-for:2004
3 schema:author N858c485dbfca4db886a947c97752ba87
4 schema:datePublished 2012
5 schema:datePublishedReg 2012-01-01
6 schema:description It is demonstrated that the family of languages generated by unambiguous conjunctive grammars with 1 nonterminal symbol is strictly included in the languages generated by 2-nonterminal grammars, which is in turn a proper subset of the family generated using 3 or more nonterminal symbols. This hierarchy is established by considering grammars over a one-letter alphabet, for which it is shown that 1-nonterminal grammars generate only regular languages, 2-nonterminal grammars generate some non-regular languages, but all of them have upper density zero, while 3-nonterminal grammars may generate some non-regular languages of non-zero density. It is also shown that the equivalence problem for 2-nonterminal grammars is undecidable.
7 schema:editor N39016f3bbebd44be96c3d20a9151f0b2
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N194276ca2a6a4ad690ab4b119c342616
12 schema:keywords alphabet
13 conjunctive grammars
14 density
15 density zero
16 equivalence problem
17 family
18 family of languages
19 grammar
20 hierarchy
21 language
22 non-regular languages
23 nonterminal symbols
24 number
25 one-letter alphabet
26 problem
27 proper subset
28 regular languages
29 subset
30 symbols
31 turn
32 zeros
33 schema:name On the Number of Nonterminal Symbols in Unambiguous Conjunctive Grammars
34 schema:pagination 183-195
35 schema:productId N24ad41a1a5be471a99a596a21757c9f5
36 Nb97a5f16d99f444b866e8e27d40be0ca
37 schema:publisher N8bff287e34484c0b8da96b47272cbee8
38 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017627177
39 https://doi.org/10.1007/978-3-642-31623-4_14
40 schema:sdDatePublished 2022-05-20T07:47
41 schema:sdLicense https://scigraph.springernature.com/explorer/license/
42 schema:sdPublisher Nd2dbf82bb8bf4bbc9bac08c6179913dd
43 schema:url https://doi.org/10.1007/978-3-642-31623-4_14
44 sgo:license sg:explorer/license/
45 sgo:sdDataset chapters
46 rdf:type schema:Chapter
47 N194276ca2a6a4ad690ab4b119c342616 schema:isbn 978-3-642-31622-7
48 978-3-642-31623-4
49 schema:name Descriptional Complexity of Formal Systems
50 rdf:type schema:Book
51 N24ad41a1a5be471a99a596a21757c9f5 schema:name doi
52 schema:value 10.1007/978-3-642-31623-4_14
53 rdf:type schema:PropertyValue
54 N251654318a1f49a2ba40cf2505710019 rdf:first sg:person.012144356031.48
55 rdf:rest rdf:nil
56 N39016f3bbebd44be96c3d20a9151f0b2 rdf:first N677086b2530a4a20a579551490cf3dcc
57 rdf:rest Nf3d1f1399fcc4b1d8cb2ef65ae10da69
58 N677086b2530a4a20a579551490cf3dcc schema:familyName Kutrib
59 schema:givenName Martin
60 rdf:type schema:Person
61 N858c485dbfca4db886a947c97752ba87 rdf:first sg:person.015252371751.76
62 rdf:rest N251654318a1f49a2ba40cf2505710019
63 N895505d960d74ddea49e399289c774bb rdf:first N8cb8fa3d4241454c84b674f32f65a005
64 rdf:rest rdf:nil
65 N8bff287e34484c0b8da96b47272cbee8 schema:name Springer Nature
66 rdf:type schema:Organisation
67 N8cb8fa3d4241454c84b674f32f65a005 schema:familyName Reis
68 schema:givenName Rogério
69 rdf:type schema:Person
70 Nb0698945a27b4bebaa5056a2411ae83d schema:familyName Moreira
71 schema:givenName Nelma
72 rdf:type schema:Person
73 Nb97a5f16d99f444b866e8e27d40be0ca schema:name dimensions_id
74 schema:value pub.1017627177
75 rdf:type schema:PropertyValue
76 Nd2dbf82bb8bf4bbc9bac08c6179913dd schema:name Springer Nature - SN SciGraph project
77 rdf:type schema:Organization
78 Nf3d1f1399fcc4b1d8cb2ef65ae10da69 rdf:first Nb0698945a27b4bebaa5056a2411ae83d
79 rdf:rest N895505d960d74ddea49e399289c774bb
80 anzsrc-for:20 schema:inDefinedTermSet anzsrc-for:
81 schema:name Language, Communication and Culture
82 rdf:type schema:DefinedTerm
83 anzsrc-for:2004 schema:inDefinedTermSet anzsrc-for:
84 schema:name Linguistics
85 rdf:type schema:DefinedTerm
86 sg:person.012144356031.48 schema:affiliation grid-institutes:grid.1374.1
87 schema:familyName Okhotin
88 schema:givenName Alexander
89 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012144356031.48
90 rdf:type schema:Person
91 sg:person.015252371751.76 schema:affiliation grid-institutes:grid.8505.8
92 schema:familyName Jeż
93 schema:givenName Artur
94 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015252371751.76
95 rdf:type schema:Person
96 grid-institutes:grid.1374.1 schema:alternateName Department of Mathematics, University of Turku, Finland
97 schema:name Department of Mathematics, University of Turku, Finland
98 rdf:type schema:Organization
99 grid-institutes:grid.8505.8 schema:alternateName Institute of Computer Science, University of Wrocław, Poland
100 schema:name Institute of Computer Science, University of Wrocław, Poland
101 rdf:type schema:Organization
 




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


...