Unambiguous Conjunctive Grammars over a One-Letter Alphabet View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2013

AUTHORS

Artur Jeż , Alexander Okhotin

ABSTRACT

It is demonstrated that unambiguous conjunctive grammars over a unary alphabet Σ = {a} have non-trivial expressive power, and that their basic properties are undecidable. The key result is that for every base \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$k \geqslant 11$\end{document} and for every one-way real-time cellular automaton operating over the alphabet of base-k digits \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\big\{\lfloor\frac{k+9}{4}\rfloor, \ldots, \lfloor\frac{k+1}{2}\rfloor\big\}$\end{document}, the language of all strings an with the base-k notation of the form 1w1, where w is accepted by the automaton, is generated by an unambiguous conjunctive grammar. Another encoding is used to simulate a cellular automaton in a unary language containing almost all strings. These constructions are used to show that for every fixed unambiguous conjunctive language L0, testing whether a given unambiguous conjunctive grammar generates L0 is undecidable. More... »

PAGES

277-288

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-38771-5_25

DOI

http://dx.doi.org/10.1007/978-3-642-38771-5_25

DIMENSIONS

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


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": [
            "Max-Planck-Institut f\u00fcr Informatik, Saarbr\u00fccken, Germany", 
            "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 and Statistics, University of Turku, Finland", 
          "id": "http://www.grid.ac/institutes/grid.1374.1", 
          "name": [
            "Department of Mathematics and Statistics, 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": "2013", 
    "datePublishedReg": "2013-01-01", 
    "description": "It is demonstrated that unambiguous conjunctive grammars over a unary alphabet \u03a3\u2009=\u2009{a} have non-trivial expressive power, and that their basic properties are undecidable. The key result is that for every base \\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}$k \\geqslant 11$\\end{document} and for every one-way real-time cellular automaton operating over the alphabet of base-k digits \\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}$\\big\\{\\lfloor\\frac{k+9}{4}\\rfloor, \\ldots, \\lfloor\\frac{k+1}{2}\\rfloor\\big\\}$\\end{document}, the language of all strings an with the base-k notation of the form 1w1, where w is accepted by the automaton, is generated by an unambiguous conjunctive grammar. Another encoding is used to simulate a cellular automaton in a unary language containing almost all strings. These constructions are used to show that for every fixed unambiguous conjunctive language L0, testing whether a given unambiguous conjunctive grammar generates L0 is undecidable.", 
    "editor": [
      {
        "familyName": "B\u00e9al", 
        "givenName": "Marie-Pierre", 
        "type": "Person"
      }, 
      {
        "familyName": "Carton", 
        "givenName": "Olivier", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-38771-5_25", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-642-38770-8", 
        "978-3-642-38771-5"
      ], 
      "name": "Developments in Language Theory", 
      "type": "Book"
    }, 
    "keywords": [
      "conjunctive grammars", 
      "one-way real-time cellular automata", 
      "one-letter alphabet", 
      "unary languages", 
      "grammar", 
      "language", 
      "alphabet \u03a3", 
      "expressive power", 
      "alphabet", 
      "automata", 
      "construction", 
      "strings", 
      "notation", 
      "power", 
      "encoding", 
      "base", 
      "key results", 
      "digits", 
      "L0", 
      "basic properties", 
      "results", 
      "cellular automata", 
      "properties"
    ], 
    "name": "Unambiguous Conjunctive Grammars over a One-Letter Alphabet", 
    "pagination": "277-288", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1017013633"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-38771-5_25"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-38771-5_25", 
      "https://app.dimensions.ai/details/publication/pub.1017013633"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-20T07:45", 
    "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_297.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-38771-5_25"
  }
]
 

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-38771-5_25'

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-38771-5_25'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-38771-5_25'

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-38771-5_25'


 

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

99 TRIPLES      23 PREDICATES      49 URIs      42 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-38771-5_25 schema:about anzsrc-for:20
2 anzsrc-for:2004
3 schema:author N92556152d2574c1ab78417d0d9cdb18c
4 schema:datePublished 2013
5 schema:datePublishedReg 2013-01-01
6 schema:description It is demonstrated that unambiguous conjunctive grammars over a unary alphabet Σ = {a} have non-trivial expressive power, and that their basic properties are undecidable. The key result is that for every base \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$k \geqslant 11$\end{document} and for every one-way real-time cellular automaton operating over the alphabet of base-k digits \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\big\{\lfloor\frac{k+9}{4}\rfloor, \ldots, \lfloor\frac{k+1}{2}\rfloor\big\}$\end{document}, the language of all strings an with the base-k notation of the form 1w1, where w is accepted by the automaton, is generated by an unambiguous conjunctive grammar. Another encoding is used to simulate a cellular automaton in a unary language containing almost all strings. These constructions are used to show that for every fixed unambiguous conjunctive language L0, testing whether a given unambiguous conjunctive grammar generates L0 is undecidable.
7 schema:editor Nbdccdd07c5fd456d9ea611e90a5f3272
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N2a50d6cfeea54b34b882763cd39166ed
12 schema:keywords L0
13 alphabet
14 alphabet Σ
15 automata
16 base
17 basic properties
18 cellular automata
19 conjunctive grammars
20 construction
21 digits
22 encoding
23 expressive power
24 grammar
25 key results
26 language
27 notation
28 one-letter alphabet
29 one-way real-time cellular automata
30 power
31 properties
32 results
33 strings
34 unary languages
35 schema:name Unambiguous Conjunctive Grammars over a One-Letter Alphabet
36 schema:pagination 277-288
37 schema:productId N66ce622bcd3c43788676b6f730fb2b4c
38 Nfedb11d2d1c04ef184c19b6ebb817ca5
39 schema:publisher N11a10f8bfe7c49bf8806a16fa4291eb3
40 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017013633
41 https://doi.org/10.1007/978-3-642-38771-5_25
42 schema:sdDatePublished 2022-05-20T07:45
43 schema:sdLicense https://scigraph.springernature.com/explorer/license/
44 schema:sdPublisher N093d731d0949469db1f58cab283a39bb
45 schema:url https://doi.org/10.1007/978-3-642-38771-5_25
46 sgo:license sg:explorer/license/
47 sgo:sdDataset chapters
48 rdf:type schema:Chapter
49 N093d731d0949469db1f58cab283a39bb schema:name Springer Nature - SN SciGraph project
50 rdf:type schema:Organization
51 N0c24d805422348e295baf2d10c4a1131 rdf:first Nd4f738eb95ce46afb24a1aec86a0a1b7
52 rdf:rest rdf:nil
53 N11a10f8bfe7c49bf8806a16fa4291eb3 schema:name Springer Nature
54 rdf:type schema:Organisation
55 N28d3339616754b7891ee5eaf3746296a rdf:first sg:person.012144356031.48
56 rdf:rest rdf:nil
57 N2a50d6cfeea54b34b882763cd39166ed schema:isbn 978-3-642-38770-8
58 978-3-642-38771-5
59 schema:name Developments in Language Theory
60 rdf:type schema:Book
61 N5cd310aa0d83450f8b1aef8475793f39 schema:familyName Béal
62 schema:givenName Marie-Pierre
63 rdf:type schema:Person
64 N66ce622bcd3c43788676b6f730fb2b4c schema:name doi
65 schema:value 10.1007/978-3-642-38771-5_25
66 rdf:type schema:PropertyValue
67 N92556152d2574c1ab78417d0d9cdb18c rdf:first sg:person.015252371751.76
68 rdf:rest N28d3339616754b7891ee5eaf3746296a
69 Nbdccdd07c5fd456d9ea611e90a5f3272 rdf:first N5cd310aa0d83450f8b1aef8475793f39
70 rdf:rest N0c24d805422348e295baf2d10c4a1131
71 Nd4f738eb95ce46afb24a1aec86a0a1b7 schema:familyName Carton
72 schema:givenName Olivier
73 rdf:type schema:Person
74 Nfedb11d2d1c04ef184c19b6ebb817ca5 schema:name dimensions_id
75 schema:value pub.1017013633
76 rdf:type schema:PropertyValue
77 anzsrc-for:20 schema:inDefinedTermSet anzsrc-for:
78 schema:name Language, Communication and Culture
79 rdf:type schema:DefinedTerm
80 anzsrc-for:2004 schema:inDefinedTermSet anzsrc-for:
81 schema:name Linguistics
82 rdf:type schema:DefinedTerm
83 sg:person.012144356031.48 schema:affiliation grid-institutes:grid.1374.1
84 schema:familyName Okhotin
85 schema:givenName Alexander
86 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012144356031.48
87 rdf:type schema:Person
88 sg:person.015252371751.76 schema:affiliation grid-institutes:grid.8505.8
89 schema:familyName Jeż
90 schema:givenName Artur
91 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015252371751.76
92 rdf:type schema:Person
93 grid-institutes:grid.1374.1 schema:alternateName Department of Mathematics and Statistics, University of Turku, Finland
94 schema:name Department of Mathematics and Statistics, University of Turku, Finland
95 rdf:type schema:Organization
96 grid-institutes:grid.8505.8 schema:alternateName Institute of Computer Science, University of Wrocław, Poland
97 schema:name Institute of Computer Science, University of Wrocław, Poland
98 Max-Planck-Institut für Informatik, Saarbrücken, Germany
99 rdf:type schema:Organization
 




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


...