Computational Complexity of Problems on Probabilistic Grammars and Transducers View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2000

AUTHORS

Francisco Casacuberta , Colin de la Higuera

ABSTRACT

Determinism plays an important role in grammatical inference. However, in practice, ambiguous grammars (and non determinism grammars in particular) are more used than determinism grammars. Computing the probability of parsing a given string or its most probable parse with stochastic regular grammars can be performed in linear time. However, the problem of finding the most probable string has yet not given any satisfactory answer. In this paper we prove that the problem is NP-hard and does not allow for a polynomial time approximation scheme. The result extends to stochastic regular syntax-directed translation schemes. More... »

PAGES

15-24

References to SciGraph publications

Book

TITLE

Grammatical Inference: Algorithms and Applications

ISBN

978-3-540-41011-9
978-3-540-45257-7

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-540-45257-7_2

DOI

http://dx.doi.org/10.1007/978-3-540-45257-7_2

DIMENSIONS

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


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/0104", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Statistics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Polytechnic University of Valencia", 
          "id": "https://www.grid.ac/institutes/grid.157927.f", 
          "name": [
            "Departamento de Sistemas Inform\u00e1ticos y Computaci\u00f3n, Universidad Polit\u00e9cnica de Valencia, 46071, Valencia, Spain"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Casacuberta", 
        "givenName": "Francisco", 
        "id": "sg:person.010572020053.79", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010572020053.79"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "name": [
            "EURISE, Facult\u00e9 des Sciences et Techniques, Universit\u00e9 de Saint Etienne \u2013 Jean Monnet, 42023, Saint Etienne, France"
          ], 
          "type": "Organization"
        }, 
        "familyName": "de la Higuera", 
        "givenName": "Colin", 
        "id": "sg:person.0614626144.21", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0614626144.21"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/978-3-642-83069-3_35", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1005585357", 
          "https://doi.org/10.1007/978-3-642-83069-3_35"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bfb0033362", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1007489390", 
          "https://doi.org/10.1007/bfb0033362"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-57745-1_27", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1009380616", 
          "https://doi.org/10.1007/978-3-642-57745-1_27"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-57745-1_27", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1009380616", 
          "https://doi.org/10.1007/978-3-642-57745-1_27"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-58473-0_141", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1013671835", 
          "https://doi.org/10.1007/3-540-58473-0_141"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-58473-0_144", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1020984415", 
          "https://doi.org/10.1007/3-540-58473-0_144"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/225298.225302", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1021952608"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0304-3975(97)00014-5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1024472591"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0885-2308(91)90009-f", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1024934091"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-58473-0_146", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1031901738", 
          "https://doi.org/10.1007/3-540-58473-0_146"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/322326.322334", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1032331779"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1023/a:1007353007695", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1037014576", 
          "https://doi.org/10.1023/a:1007353007695"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0022-0000(91)90023-x", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1043200457"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1051/ita:1999102", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1056972030"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/34.211465", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061155805"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/34.57687", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061156566"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/tsmc.1975.5408432", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061792866"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1142/s0218001496000153", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062951047"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2000", 
    "datePublishedReg": "2000-01-01", 
    "description": "Determinism plays an important role in grammatical inference. However, in practice, ambiguous grammars (and non determinism grammars in particular) are more used than determinism grammars. Computing the probability of parsing a given string or its most probable parse with stochastic regular grammars can be performed in linear time. However, the problem of finding the most probable string has yet not given any satisfactory answer. In this paper we prove that the problem is NP-hard and does not allow for a polynomial time approximation scheme. The result extends to stochastic regular syntax-directed translation schemes.", 
    "editor": [
      {
        "familyName": "Oliveira", 
        "givenName": "Arlindo L.", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-540-45257-7_2", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-41011-9", 
        "978-3-540-45257-7"
      ], 
      "name": "Grammatical Inference: Algorithms and Applications", 
      "type": "Book"
    }, 
    "name": "Computational Complexity of Problems on Probabilistic Grammars and Transducers", 
    "pagination": "15-24", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1005228610"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-540-45257-7_2"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "18e92c4108c2b271ee5ed826aaa9b17e2dfd77f0ea8ed1356037c1e024cc29d4"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-540-45257-7_2", 
      "https://app.dimensions.ai/details/publication/pub.1005228610"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-16T08:02", 
    "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/0000000359_0000000359/records_29203_00000000.jsonl", 
    "type": "Chapter", 
    "url": "https://link.springer.com/10.1007%2F978-3-540-45257-7_2"
  }
]
 

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-45257-7_2'

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-45257-7_2'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-45257-7_2'

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-45257-7_2'


 

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

132 TRIPLES      23 PREDICATES      44 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-540-45257-7_2 schema:about anzsrc-for:01
2 anzsrc-for:0104
3 schema:author Ne768962c90d641adb3bd4bfe366d4c79
4 schema:citation sg:pub.10.1007/3-540-58473-0_141
5 sg:pub.10.1007/3-540-58473-0_144
6 sg:pub.10.1007/3-540-58473-0_146
7 sg:pub.10.1007/978-3-642-57745-1_27
8 sg:pub.10.1007/978-3-642-83069-3_35
9 sg:pub.10.1007/bfb0033362
10 sg:pub.10.1023/a:1007353007695
11 https://doi.org/10.1016/0022-0000(91)90023-x
12 https://doi.org/10.1016/0885-2308(91)90009-f
13 https://doi.org/10.1016/s0304-3975(97)00014-5
14 https://doi.org/10.1051/ita:1999102
15 https://doi.org/10.1109/34.211465
16 https://doi.org/10.1109/34.57687
17 https://doi.org/10.1109/tsmc.1975.5408432
18 https://doi.org/10.1142/s0218001496000153
19 https://doi.org/10.1145/225298.225302
20 https://doi.org/10.1145/322326.322334
21 schema:datePublished 2000
22 schema:datePublishedReg 2000-01-01
23 schema:description Determinism plays an important role in grammatical inference. However, in practice, ambiguous grammars (and non determinism grammars in particular) are more used than determinism grammars. Computing the probability of parsing a given string or its most probable parse with stochastic regular grammars can be performed in linear time. However, the problem of finding the most probable string has yet not given any satisfactory answer. In this paper we prove that the problem is NP-hard and does not allow for a polynomial time approximation scheme. The result extends to stochastic regular syntax-directed translation schemes.
24 schema:editor N9dbe65deb995498ca7d10dd16601740a
25 schema:genre chapter
26 schema:inLanguage en
27 schema:isAccessibleForFree true
28 schema:isPartOf Nf08da1a72f1f4f739663db3c5a847927
29 schema:name Computational Complexity of Problems on Probabilistic Grammars and Transducers
30 schema:pagination 15-24
31 schema:productId N42bd3482b0e7409db41185f43683fba6
32 N65a7cc57dae24d9a85e32802e52af143
33 N69fec10e371041ee99e775856b6005fd
34 schema:publisher N0f930e723d4d45f8890a4b622b0d63b8
35 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005228610
36 https://doi.org/10.1007/978-3-540-45257-7_2
37 schema:sdDatePublished 2019-04-16T08:02
38 schema:sdLicense https://scigraph.springernature.com/explorer/license/
39 schema:sdPublisher N7a90186617f44d48a190785ceaa5c88e
40 schema:url https://link.springer.com/10.1007%2F978-3-540-45257-7_2
41 sgo:license sg:explorer/license/
42 sgo:sdDataset chapters
43 rdf:type schema:Chapter
44 N09aad631164e4fa1b27e41f77fccc6d7 schema:name EURISE, Faculté des Sciences et Techniques, Université de Saint Etienne – Jean Monnet, 42023, Saint Etienne, France
45 rdf:type schema:Organization
46 N0f930e723d4d45f8890a4b622b0d63b8 schema:location Berlin, Heidelberg
47 schema:name Springer Berlin Heidelberg
48 rdf:type schema:Organisation
49 N42bd3482b0e7409db41185f43683fba6 schema:name dimensions_id
50 schema:value pub.1005228610
51 rdf:type schema:PropertyValue
52 N65a7cc57dae24d9a85e32802e52af143 schema:name readcube_id
53 schema:value 18e92c4108c2b271ee5ed826aaa9b17e2dfd77f0ea8ed1356037c1e024cc29d4
54 rdf:type schema:PropertyValue
55 N69fec10e371041ee99e775856b6005fd schema:name doi
56 schema:value 10.1007/978-3-540-45257-7_2
57 rdf:type schema:PropertyValue
58 N7a90186617f44d48a190785ceaa5c88e schema:name Springer Nature - SN SciGraph project
59 rdf:type schema:Organization
60 N89315ebbd9da47c88c917a55f24f37c7 rdf:first sg:person.0614626144.21
61 rdf:rest rdf:nil
62 N9dbe65deb995498ca7d10dd16601740a rdf:first Nebe9474e119e468caa87c82beeb16241
63 rdf:rest rdf:nil
64 Ne768962c90d641adb3bd4bfe366d4c79 rdf:first sg:person.010572020053.79
65 rdf:rest N89315ebbd9da47c88c917a55f24f37c7
66 Nebe9474e119e468caa87c82beeb16241 schema:familyName Oliveira
67 schema:givenName Arlindo L.
68 rdf:type schema:Person
69 Nf08da1a72f1f4f739663db3c5a847927 schema:isbn 978-3-540-41011-9
70 978-3-540-45257-7
71 schema:name Grammatical Inference: Algorithms and Applications
72 rdf:type schema:Book
73 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
74 schema:name Mathematical Sciences
75 rdf:type schema:DefinedTerm
76 anzsrc-for:0104 schema:inDefinedTermSet anzsrc-for:
77 schema:name Statistics
78 rdf:type schema:DefinedTerm
79 sg:person.010572020053.79 schema:affiliation https://www.grid.ac/institutes/grid.157927.f
80 schema:familyName Casacuberta
81 schema:givenName Francisco
82 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010572020053.79
83 rdf:type schema:Person
84 sg:person.0614626144.21 schema:affiliation N09aad631164e4fa1b27e41f77fccc6d7
85 schema:familyName de la Higuera
86 schema:givenName Colin
87 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0614626144.21
88 rdf:type schema:Person
89 sg:pub.10.1007/3-540-58473-0_141 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013671835
90 https://doi.org/10.1007/3-540-58473-0_141
91 rdf:type schema:CreativeWork
92 sg:pub.10.1007/3-540-58473-0_144 schema:sameAs https://app.dimensions.ai/details/publication/pub.1020984415
93 https://doi.org/10.1007/3-540-58473-0_144
94 rdf:type schema:CreativeWork
95 sg:pub.10.1007/3-540-58473-0_146 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031901738
96 https://doi.org/10.1007/3-540-58473-0_146
97 rdf:type schema:CreativeWork
98 sg:pub.10.1007/978-3-642-57745-1_27 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009380616
99 https://doi.org/10.1007/978-3-642-57745-1_27
100 rdf:type schema:CreativeWork
101 sg:pub.10.1007/978-3-642-83069-3_35 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005585357
102 https://doi.org/10.1007/978-3-642-83069-3_35
103 rdf:type schema:CreativeWork
104 sg:pub.10.1007/bfb0033362 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007489390
105 https://doi.org/10.1007/bfb0033362
106 rdf:type schema:CreativeWork
107 sg:pub.10.1023/a:1007353007695 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037014576
108 https://doi.org/10.1023/a:1007353007695
109 rdf:type schema:CreativeWork
110 https://doi.org/10.1016/0022-0000(91)90023-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1043200457
111 rdf:type schema:CreativeWork
112 https://doi.org/10.1016/0885-2308(91)90009-f schema:sameAs https://app.dimensions.ai/details/publication/pub.1024934091
113 rdf:type schema:CreativeWork
114 https://doi.org/10.1016/s0304-3975(97)00014-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024472591
115 rdf:type schema:CreativeWork
116 https://doi.org/10.1051/ita:1999102 schema:sameAs https://app.dimensions.ai/details/publication/pub.1056972030
117 rdf:type schema:CreativeWork
118 https://doi.org/10.1109/34.211465 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061155805
119 rdf:type schema:CreativeWork
120 https://doi.org/10.1109/34.57687 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061156566
121 rdf:type schema:CreativeWork
122 https://doi.org/10.1109/tsmc.1975.5408432 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061792866
123 rdf:type schema:CreativeWork
124 https://doi.org/10.1142/s0218001496000153 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062951047
125 rdf:type schema:CreativeWork
126 https://doi.org/10.1145/225298.225302 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021952608
127 rdf:type schema:CreativeWork
128 https://doi.org/10.1145/322326.322334 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032331779
129 rdf:type schema:CreativeWork
130 https://www.grid.ac/institutes/grid.157927.f schema:alternateName Polytechnic University of Valencia
131 schema:name Departamento de Sistemas Informáticos y Computación, Universidad Politécnica de Valencia, 46071, Valencia, Spain
132 rdf:type schema:Organization
 




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


...