Conjunctive Grammars Can Generate Non-regular Unary Languages View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2007

AUTHORS

Artur Jeż

ABSTRACT

Conjunctive grammars were introduced by A. Okhotin in [1] as a natural extension of context-free grammars with an additional operation of intersection in the body of any production of the grammar. Several theorems and algorithms for context-free grammars generalize to the conjunctive case. Still some questions remained open. A. Okhotin posed nine problems concerning those grammars. One of them was a question, whether a conjunctive grammar over unary alphabet can generate only regular languages. We give a negative answer, contrary to the conjectured positive one, by constructing a conjunctive grammar for the language \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\{ a^{4^{n}} : n \in \mathbb{N} \}$\end{document}. We then generalise this result—for every set of numbers L such that their representation in some k-ary system is regular set we show that \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\{ a^{k^{n}} : n \in L \}$\end{document} is generated by some conjunctive grammar over unary alphabet. More... »

PAGES

242-253

Book

TITLE

Developments in Language Theory

ISBN

978-3-540-73207-5
978-3-540-73208-2

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-540-73208-2_24

DOI

http://dx.doi.org/10.1007/978-3-540-73208-2_24

DIMENSIONS

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


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, ul. Joliot-Curie 15, 50-383 Wroclaw, Poland", 
          "id": "http://www.grid.ac/institutes/grid.425308.8", 
          "name": [
            "Institute of Computer Science, ul. Joliot-Curie 15, 50-383 Wroclaw, 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"
      }
    ], 
    "datePublished": "2007", 
    "datePublishedReg": "2007-01-01", 
    "description": "Conjunctive grammars were introduced by A.\u00a0Okhotin in [1] as a natural extension of context-free grammars with an additional operation of intersection in the body of any production of the grammar. Several theorems and algorithms for context-free grammars generalize to the conjunctive case. Still some questions remained open. A.\u00a0Okhotin posed nine problems concerning those grammars. One of them was a question, whether a conjunctive grammar over unary alphabet can generate only regular languages. We give a negative answer, contrary to the conjectured positive one, by constructing a conjunctive grammar for the language \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$\\{ a^{4^{n}} : n \\in \\mathbb{N} \\}$\\end{document}. We then generalise this result\u2014for every set of numbers L such that their representation in some k-ary system is regular set we show that \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$\\{ a^{k^{n}} : n \\in L \\}$\\end{document} is generated by some conjunctive grammar over unary alphabet.", 
    "editor": [
      {
        "familyName": "Harju", 
        "givenName": "Tero", 
        "type": "Person"
      }, 
      {
        "familyName": "Karhum\u00e4ki", 
        "givenName": "Juhani", 
        "type": "Person"
      }, 
      {
        "familyName": "Lepist\u00f6", 
        "givenName": "Arto", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-540-73208-2_24", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-73207-5", 
        "978-3-540-73208-2"
      ], 
      "name": "Developments in Language Theory", 
      "type": "Book"
    }, 
    "keywords": [
      "conjunctive grammars", 
      "context-free grammars", 
      "unary alphabet", 
      "unary languages", 
      "regular languages", 
      "grammar", 
      "conjunctive case", 
      "language", 
      "Okhotin", 
      "alphabet", 
      "ary systems", 
      "questions", 
      "intersection", 
      "representation", 
      "positive ones", 
      "answers", 
      "negative answer", 
      "body", 
      "one", 
      "production", 
      "number L", 
      "natural extension", 
      "problem", 
      "set", 
      "cases", 
      "extension", 
      "additional operations", 
      "system", 
      "results", 
      "operation", 
      "algorithm", 
      "theorem"
    ], 
    "name": "Conjunctive Grammars Can Generate Non-regular Unary Languages", 
    "pagination": "242-253", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1034216610"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-540-73208-2_24"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-540-73208-2_24", 
      "https://app.dimensions.ai/details/publication/pub.1034216610"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-20T07:42", 
    "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_162.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-540-73208-2_24"
  }
]
 

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-73208-2_24'

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-73208-2_24'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-73208-2_24'

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-73208-2_24'


 

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

102 TRIPLES      23 PREDICATES      58 URIs      51 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-540-73208-2_24 schema:about anzsrc-for:20
2 anzsrc-for:2004
3 schema:author Nf1769a7526454ff7b79248365d4413b7
4 schema:datePublished 2007
5 schema:datePublishedReg 2007-01-01
6 schema:description Conjunctive grammars were introduced by A. Okhotin in [1] as a natural extension of context-free grammars with an additional operation of intersection in the body of any production of the grammar. Several theorems and algorithms for context-free grammars generalize to the conjunctive case. Still some questions remained open. A. Okhotin posed nine problems concerning those grammars. One of them was a question, whether a conjunctive grammar over unary alphabet can generate only regular languages. We give a negative answer, contrary to the conjectured positive one, by constructing a conjunctive grammar for the language \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\{ a^{4^{n}} : n \in \mathbb{N} \}$\end{document}. We then generalise this result—for every set of numbers L such that their representation in some k-ary system is regular set we show that \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\{ a^{k^{n}} : n \in L \}$\end{document} is generated by some conjunctive grammar over unary alphabet.
7 schema:editor N9a2a30a0a06f4ca2b75d389ad1785a52
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N8f3f5233fad6473fb549d2618474020e
12 schema:keywords Okhotin
13 additional operations
14 algorithm
15 alphabet
16 answers
17 ary systems
18 body
19 cases
20 conjunctive case
21 conjunctive grammars
22 context-free grammars
23 extension
24 grammar
25 intersection
26 language
27 natural extension
28 negative answer
29 number L
30 one
31 operation
32 positive ones
33 problem
34 production
35 questions
36 regular languages
37 representation
38 results
39 set
40 system
41 theorem
42 unary alphabet
43 unary languages
44 schema:name Conjunctive Grammars Can Generate Non-regular Unary Languages
45 schema:pagination 242-253
46 schema:productId N20ba371fb7d3497daa46bec3d035b9c0
47 Nfa3d4b239cf445069dbfa09260e25591
48 schema:publisher N9b28127cc9f341efb3b2a676ebfaf7f9
49 schema:sameAs https://app.dimensions.ai/details/publication/pub.1034216610
50 https://doi.org/10.1007/978-3-540-73208-2_24
51 schema:sdDatePublished 2022-05-20T07:42
52 schema:sdLicense https://scigraph.springernature.com/explorer/license/
53 schema:sdPublisher N3ceb423009f949129ae7180d50b93f8b
54 schema:url https://doi.org/10.1007/978-3-540-73208-2_24
55 sgo:license sg:explorer/license/
56 sgo:sdDataset chapters
57 rdf:type schema:Chapter
58 N116d448fb1c04af299dd1402325a8f9e schema:familyName Lepistö
59 schema:givenName Arto
60 rdf:type schema:Person
61 N20ba371fb7d3497daa46bec3d035b9c0 schema:name dimensions_id
62 schema:value pub.1034216610
63 rdf:type schema:PropertyValue
64 N3ceb423009f949129ae7180d50b93f8b schema:name Springer Nature - SN SciGraph project
65 rdf:type schema:Organization
66 N4ee7a9f800cc4ababe3251c5a0a8d0ce rdf:first Ne48a56fc96d44e40bc7ba29ee2bece64
67 rdf:rest Ne69f6aa1e229448f89b4b00b6bb30113
68 N8f3f5233fad6473fb549d2618474020e schema:isbn 978-3-540-73207-5
69 978-3-540-73208-2
70 schema:name Developments in Language Theory
71 rdf:type schema:Book
72 N8fe96a2af0154a38854fd7c7de221605 schema:familyName Harju
73 schema:givenName Tero
74 rdf:type schema:Person
75 N9a2a30a0a06f4ca2b75d389ad1785a52 rdf:first N8fe96a2af0154a38854fd7c7de221605
76 rdf:rest N4ee7a9f800cc4ababe3251c5a0a8d0ce
77 N9b28127cc9f341efb3b2a676ebfaf7f9 schema:name Springer Nature
78 rdf:type schema:Organisation
79 Ne48a56fc96d44e40bc7ba29ee2bece64 schema:familyName Karhumäki
80 schema:givenName Juhani
81 rdf:type schema:Person
82 Ne69f6aa1e229448f89b4b00b6bb30113 rdf:first N116d448fb1c04af299dd1402325a8f9e
83 rdf:rest rdf:nil
84 Nf1769a7526454ff7b79248365d4413b7 rdf:first sg:person.015252371751.76
85 rdf:rest rdf:nil
86 Nfa3d4b239cf445069dbfa09260e25591 schema:name doi
87 schema:value 10.1007/978-3-540-73208-2_24
88 rdf:type schema:PropertyValue
89 anzsrc-for:20 schema:inDefinedTermSet anzsrc-for:
90 schema:name Language, Communication and Culture
91 rdf:type schema:DefinedTerm
92 anzsrc-for:2004 schema:inDefinedTermSet anzsrc-for:
93 schema:name Linguistics
94 rdf:type schema:DefinedTerm
95 sg:person.015252371751.76 schema:affiliation grid-institutes:grid.425308.8
96 schema:familyName Jeż
97 schema:givenName Artur
98 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015252371751.76
99 rdf:type schema:Person
100 grid-institutes:grid.425308.8 schema:alternateName Institute of Computer Science, ul. Joliot-Curie 15, 50-383 Wroclaw, Poland
101 schema:name Institute of Computer Science, ul. Joliot-Curie 15, 50-383 Wroclaw, Poland
102 rdf:type schema:Organization
 




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


...