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


Ontology type: schema:Chapter     


Chapter Info

DATE

2009

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, while the equivalence, finiteness and emptiness problems for these grammars are shown to be undecidable. More... »

PAGES

191-202

Book

TITLE

Computer Science - Theory and Applications

ISBN

978-3-642-03350-6
978-3-642-03351-3

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-03351-3_19

DOI

http://dx.doi.org/10.1007/978-3-642-03351-3_19

DIMENSIONS

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


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": [
            "Academy of Finland, Finland", 
            "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": "2009", 
    "datePublishedReg": "2009-01-01", 
    "description": "Conjunctive grammars over an alphabet \u03a3\u2009=\u2009{a} are studied, with the focus on the special case with a unique nonterminal symbol. Such a grammar is equivalent to an equation X\u2009=\u2009\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, while the equivalence, finiteness and emptiness problems for these grammars are shown to be undecidable.", 
    "editor": [
      {
        "familyName": "Frid", 
        "givenName": "Anna", 
        "type": "Person"
      }, 
      {
        "familyName": "Morozov", 
        "givenName": "Andrey", 
        "type": "Person"
      }, 
      {
        "familyName": "Rybalchenko", 
        "givenName": "Andrey", 
        "type": "Person"
      }, 
      {
        "familyName": "Wagner", 
        "givenName": "Klaus W.", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-03351-3_19", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-642-03350-6", 
        "978-3-642-03351-3"
      ], 
      "name": "Computer Science - Theory and Applications", 
      "type": "Book"
    }, 
    "keywords": [
      "conjunctive grammars", 
      "grammar", 
      "nonterminal symbols", 
      "unary alphabet", 
      "nonterminals", 
      "membership problem", 
      "emptiness problem", 
      "symbols", 
      "language", 
      "alphabet", 
      "intersection", 
      "construction", 
      "focus", 
      "Union", 
      "equivalence", 
      "finiteness", 
      "equation x", 
      "natural numbers", 
      "problem", 
      "cases", 
      "set", 
      "special case", 
      "number", 
      "addition", 
      "slight modification", 
      "modification"
    ], 
    "name": "One-Nonterminal Conjunctive Grammars over a Unary Alphabet", 
    "pagination": "191-202", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1043966743"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-03351-3_19"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-03351-3_19", 
      "https://app.dimensions.ai/details/publication/pub.1043966743"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-20T07:46", 
    "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_367.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-03351-3_19"
  }
]
 

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-03351-3_19'

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-03351-3_19'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-03351-3_19'

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-03351-3_19'


 

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

112 TRIPLES      23 PREDICATES      52 URIs      45 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-03351-3_19 schema:about anzsrc-for:20
2 anzsrc-for:2004
3 schema:author N6ba1378923184dac8a6fcfd3ec2b0e7d
4 schema:datePublished 2009
5 schema:datePublishedReg 2009-01-01
6 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, while the equivalence, finiteness and emptiness problems for these grammars are shown to be undecidable.
7 schema:editor N3a22ea4d46a644f7adaa5eb6e4cc3669
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N2fb56d06647440348050edaa902dc61d
12 schema:keywords Union
13 addition
14 alphabet
15 cases
16 conjunctive grammars
17 construction
18 emptiness problem
19 equation x
20 equivalence
21 finiteness
22 focus
23 grammar
24 intersection
25 language
26 membership problem
27 modification
28 natural numbers
29 nonterminal symbols
30 nonterminals
31 number
32 problem
33 set
34 slight modification
35 special case
36 symbols
37 unary alphabet
38 schema:name One-Nonterminal Conjunctive Grammars over a Unary Alphabet
39 schema:pagination 191-202
40 schema:productId N89e2662fcada43288d9106d673a4d0ab
41 Nfaee49f4fe3c4cd596ab0db7035b68aa
42 schema:publisher N6341601420ce4ec3959b5ea25bbdeacc
43 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043966743
44 https://doi.org/10.1007/978-3-642-03351-3_19
45 schema:sdDatePublished 2022-05-20T07:46
46 schema:sdLicense https://scigraph.springernature.com/explorer/license/
47 schema:sdPublisher N111e72909ce643a2bc16ed0a27dae511
48 schema:url https://doi.org/10.1007/978-3-642-03351-3_19
49 sgo:license sg:explorer/license/
50 sgo:sdDataset chapters
51 rdf:type schema:Chapter
52 N111e72909ce643a2bc16ed0a27dae511 schema:name Springer Nature - SN SciGraph project
53 rdf:type schema:Organization
54 N2fb56d06647440348050edaa902dc61d schema:isbn 978-3-642-03350-6
55 978-3-642-03351-3
56 schema:name Computer Science - Theory and Applications
57 rdf:type schema:Book
58 N3a22ea4d46a644f7adaa5eb6e4cc3669 rdf:first Ne579528d6180422fa8a7eb9a74316c83
59 rdf:rest N96b7e772acde4be1a28d5dee8c358a6c
60 N5bb83bd1ad234800a09ff8106d914f76 rdf:first N60d08c1f18d749b6bc8beb05037d5815
61 rdf:rest N915b9a9a85394e27adf2eb95d86bfda6
62 N60d08c1f18d749b6bc8beb05037d5815 schema:familyName Rybalchenko
63 schema:givenName Andrey
64 rdf:type schema:Person
65 N6341601420ce4ec3959b5ea25bbdeacc schema:name Springer Nature
66 rdf:type schema:Organisation
67 N6ba1378923184dac8a6fcfd3ec2b0e7d rdf:first sg:person.015252371751.76
68 rdf:rest Nbdf08d6c787040da8e99b42c410fb174
69 N89e2662fcada43288d9106d673a4d0ab schema:name dimensions_id
70 schema:value pub.1043966743
71 rdf:type schema:PropertyValue
72 N915b9a9a85394e27adf2eb95d86bfda6 rdf:first Nf3ca087048194832af0c4e8a2a2d14c6
73 rdf:rest rdf:nil
74 N96b7e772acde4be1a28d5dee8c358a6c rdf:first Nfbc9c928a7774f579227dc95b8cbbae4
75 rdf:rest N5bb83bd1ad234800a09ff8106d914f76
76 Nbdf08d6c787040da8e99b42c410fb174 rdf:first sg:person.012144356031.48
77 rdf:rest rdf:nil
78 Ne579528d6180422fa8a7eb9a74316c83 schema:familyName Frid
79 schema:givenName Anna
80 rdf:type schema:Person
81 Nf3ca087048194832af0c4e8a2a2d14c6 schema:familyName Wagner
82 schema:givenName Klaus W.
83 rdf:type schema:Person
84 Nfaee49f4fe3c4cd596ab0db7035b68aa schema:name doi
85 schema:value 10.1007/978-3-642-03351-3_19
86 rdf:type schema:PropertyValue
87 Nfbc9c928a7774f579227dc95b8cbbae4 schema:familyName Morozov
88 schema:givenName Andrey
89 rdf:type schema:Person
90 anzsrc-for:20 schema:inDefinedTermSet anzsrc-for:
91 schema:name Language, Communication and Culture
92 rdf:type schema:DefinedTerm
93 anzsrc-for:2004 schema:inDefinedTermSet anzsrc-for:
94 schema:name Linguistics
95 rdf:type schema:DefinedTerm
96 sg:person.012144356031.48 schema:affiliation grid-institutes:grid.1374.1
97 schema:familyName Okhotin
98 schema:givenName Alexander
99 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012144356031.48
100 rdf:type schema:Person
101 sg:person.015252371751.76 schema:affiliation grid-institutes:grid.8505.8
102 schema:familyName Jeż
103 schema:givenName Artur
104 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015252371751.76
105 rdf:type schema:Person
106 grid-institutes:grid.1374.1 schema:alternateName Department of Mathematics, University of Turku, Finland
107 schema:name Academy of Finland, Finland
108 Department of Mathematics, University of Turku, Finland
109 rdf:type schema:Organization
110 grid-institutes:grid.8505.8 schema:alternateName Institute of Computer Science, University of Wrocław, Poland
111 schema:name Institute of Computer Science, University of Wrocław, Poland
112 rdf:type schema:Organization
 




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


...