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 N2e7f7e0ee663431985259ed455f04bb1
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 N1a81b31653264e009c7a66d3abbd8945
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N743eb4a524b440a1a5ae151394ffbc7f
12 schema:name Deciding the NTS property of context-free grammars
13 schema:pagination 124-130
14 schema:productId N2fc019584da4404d8641ccec4114d773
15 N65a6ad7a2ce24ae0b8ef6a02b5738977
16 Nde32e4d4ea43412f89a185ebbc4d8fc0
17 schema:publisher N2e715b7b0f1941a695f690a30de90265
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 Na2caf8e3ff214a3ca12f784c3d20bd4b
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 N09cff57082e74599862b4017d73365c2 schema:familyName Karhumäki
28 schema:givenName Juliani
29 rdf:type schema:Person
30 N1a81b31653264e009c7a66d3abbd8945 rdf:first N09cff57082e74599862b4017d73365c2
31 rdf:rest N6caefcc136e94096bca6f38fec622d8a
32 N2e715b7b0f1941a695f690a30de90265 schema:location Berlin, Heidelberg
33 schema:name Springer Berlin Heidelberg
34 rdf:type schema:Organisation
35 N2e7f7e0ee663431985259ed455f04bb1 rdf:first sg:person.014574236321.39
36 rdf:rest rdf:nil
37 N2fc019584da4404d8641ccec4114d773 schema:name doi
38 schema:value 10.1007/3-540-58131-6_41
39 rdf:type schema:PropertyValue
40 N52c71cfa69694bf39a7d1ed05e7ecf8f rdf:first N67060ec526494e28a1a2cfd348d5f1ae
41 rdf:rest rdf:nil
42 N5f5ed4fc269d421a8980f820dea33941 schema:familyName Maurer
43 schema:givenName Hermann
44 rdf:type schema:Person
45 N65a6ad7a2ce24ae0b8ef6a02b5738977 schema:name dimensions_id
46 schema:value pub.1038527222
47 rdf:type schema:PropertyValue
48 N67060ec526494e28a1a2cfd348d5f1ae schema:familyName Rozenberg
49 schema:givenName Grzegorz
50 rdf:type schema:Person
51 N6caefcc136e94096bca6f38fec622d8a rdf:first N5f5ed4fc269d421a8980f820dea33941
52 rdf:rest N52c71cfa69694bf39a7d1ed05e7ecf8f
53 N743eb4a524b440a1a5ae151394ffbc7f schema:isbn 978-3-540-48445-5
54 978-3-540-58131-4
55 schema:name Results and Trends in Theoretical Computer Science
56 rdf:type schema:Book
57 Na2caf8e3ff214a3ca12f784c3d20bd4b schema:name Springer Nature - SN SciGraph project
58 rdf:type schema:Organization
59 Nde32e4d4ea43412f89a185ebbc4d8fc0 schema:name readcube_id
60 schema:value b7871eb04a05bd26bcf9571b33e027744530144feffeec15bac6f62f21eac3f0
61 rdf:type schema:PropertyValue
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)


...