Deciding the NTS property of context-free grammars View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

1994

AUTHORS

Joost Engelfriet

ABSTRACT

An algorithm is presented that is a variation of the one of Senizergues in [4]. It decides the NonTerminal Separation property of context-free grammars in polynomial time. A straightforward generalization of the algorithm decides the NTS property of extended context-free grammars (but not in polynomial time).

PAGES

124-130

Book

TITLE

Results and Trends in Theoretical Computer Science

ISBN

978-3-540-58131-4
978-3-540-48445-5

Author Affiliations

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-58131-6_41

DOI

http://dx.doi.org/10.1007/3-540-58131-6_41

DIMENSIONS

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


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/1801", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Law", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/18", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Law and Legal Studies", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Leiden University", 
          "id": "https://www.grid.ac/institutes/grid.5132.5", 
          "name": [
            "Department of Computer Science, Leiden University, P.O. Box 9512, 2300\u00a0RA Leiden, The Netherlands"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Engelfriet", 
        "givenName": "Joost", 
        "id": "sg:person.014574236321.39", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014574236321.39"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "1994", 
    "datePublishedReg": "1994-01-01", 
    "description": "An algorithm is presented that is a variation of the one of Senizergues in [4]. It decides the NonTerminal Separation property of context-free grammars in polynomial time. A straightforward generalization of the algorithm decides the NTS property of extended context-free grammars (but not in polynomial time).", 
    "editor": [
      {
        "familyName": "Karhum\u00e4ki", 
        "givenName": "Juliani", 
        "type": "Person"
      }, 
      {
        "familyName": "Maurer", 
        "givenName": "Hermann", 
        "type": "Person"
      }, 
      {
        "familyName": "Rozenberg", 
        "givenName": "Grzegorz", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-58131-6_41", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-58131-4", 
        "978-3-540-48445-5"
      ], 
      "name": "Results and Trends in Theoretical Computer Science", 
      "type": "Book"
    }, 
    "name": "Deciding the NTS property of context-free grammars", 
    "pagination": "124-130", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-58131-6_41"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "b7871eb04a05bd26bcf9571b33e027744530144feffeec15bac6f62f21eac3f0"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1038527222"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-58131-6_41", 
      "https://app.dimensions.ai/details/publication/pub.1038527222"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-15T21:46", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000001_0000000264/records_8693_00000066.jsonl", 
    "type": "Chapter", 
    "url": "http://link.springer.com/10.1007/3-540-58131-6_41"
  }
]
 

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/3-540-58131-6_41'

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/3-540-58131-6_41'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-58131-6_41'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/3-540-58131-6_41'


 

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

75 TRIPLES      22 PREDICATES      27 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-58131-6_41 schema:about anzsrc-for:18
2 anzsrc-for:1801
3 schema:author N78a62e715cc3426faa494bdbb93c6e72
4 schema:datePublished 1994
5 schema:datePublishedReg 1994-01-01
6 schema:description An algorithm is presented that is a variation of the one of Senizergues in [4]. It decides the NonTerminal Separation property of context-free grammars in polynomial time. A straightforward generalization of the algorithm decides the NTS property of extended context-free grammars (but not in polynomial time).
7 schema:editor N069d3b608ffa4666916bda1b00ff7a90
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf Ncdd6b049b1d541f7b2e50a133413a4de
12 schema:name Deciding the NTS property of context-free grammars
13 schema:pagination 124-130
14 schema:productId N2471be7db29b47e08a5e42a937368750
15 N4817562524dd4b89ad78e425e3e8a574
16 N8f819a321a4348a9a7914f58ebab7380
17 schema:publisher Na4b60bf72b634383bf1569c4e88583d2
18 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038527222
19 https://doi.org/10.1007/3-540-58131-6_41
20 schema:sdDatePublished 2019-04-15T21:46
21 schema:sdLicense https://scigraph.springernature.com/explorer/license/
22 schema:sdPublisher N209a419f2f0449d5b6954046db51f6a8
23 schema:url http://link.springer.com/10.1007/3-540-58131-6_41
24 sgo:license sg:explorer/license/
25 sgo:sdDataset chapters
26 rdf:type schema:Chapter
27 N069d3b608ffa4666916bda1b00ff7a90 rdf:first N296ef966565d4824bb148d3bbc5f9916
28 rdf:rest N5966f57f62554b48a69719b897a91c83
29 N209a419f2f0449d5b6954046db51f6a8 schema:name Springer Nature - SN SciGraph project
30 rdf:type schema:Organization
31 N2471be7db29b47e08a5e42a937368750 schema:name readcube_id
32 schema:value b7871eb04a05bd26bcf9571b33e027744530144feffeec15bac6f62f21eac3f0
33 rdf:type schema:PropertyValue
34 N296ef966565d4824bb148d3bbc5f9916 schema:familyName Karhumäki
35 schema:givenName Juliani
36 rdf:type schema:Person
37 N4817562524dd4b89ad78e425e3e8a574 schema:name dimensions_id
38 schema:value pub.1038527222
39 rdf:type schema:PropertyValue
40 N5966f57f62554b48a69719b897a91c83 rdf:first Nc4f03efe024e4636abcb84c9035c67c9
41 rdf:rest N6b5ce9b39d384f53bb8182478d94f561
42 N6b5ce9b39d384f53bb8182478d94f561 rdf:first N8b97784886dd4f078ac01df383555a2c
43 rdf:rest rdf:nil
44 N78a62e715cc3426faa494bdbb93c6e72 rdf:first sg:person.014574236321.39
45 rdf:rest rdf:nil
46 N8b97784886dd4f078ac01df383555a2c schema:familyName Rozenberg
47 schema:givenName Grzegorz
48 rdf:type schema:Person
49 N8f819a321a4348a9a7914f58ebab7380 schema:name doi
50 schema:value 10.1007/3-540-58131-6_41
51 rdf:type schema:PropertyValue
52 Na4b60bf72b634383bf1569c4e88583d2 schema:location Berlin, Heidelberg
53 schema:name Springer Berlin Heidelberg
54 rdf:type schema:Organisation
55 Nc4f03efe024e4636abcb84c9035c67c9 schema:familyName Maurer
56 schema:givenName Hermann
57 rdf:type schema:Person
58 Ncdd6b049b1d541f7b2e50a133413a4de schema:isbn 978-3-540-48445-5
59 978-3-540-58131-4
60 schema:name Results and Trends in Theoretical Computer Science
61 rdf:type schema:Book
62 anzsrc-for:18 schema:inDefinedTermSet anzsrc-for:
63 schema:name Law and Legal Studies
64 rdf:type schema:DefinedTerm
65 anzsrc-for:1801 schema:inDefinedTermSet anzsrc-for:
66 schema:name Law
67 rdf:type schema:DefinedTerm
68 sg:person.014574236321.39 schema:affiliation https://www.grid.ac/institutes/grid.5132.5
69 schema:familyName Engelfriet
70 schema:givenName Joost
71 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014574236321.39
72 rdf:type schema:Person
73 https://www.grid.ac/institutes/grid.5132.5 schema:alternateName Leiden University
74 schema:name Department of Computer Science, Leiden University, P.O. Box 9512, 2300 RA Leiden, The Netherlands
75 rdf:type schema:Organization
 




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


...