Weak and strong recognition by 2-way randomized automata View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

1997

AUTHORS

Andris Ambainis , Rūsiņš Freivalds , Marek Karpinski

ABSTRACT

Languages weakly recognized by a Monte Carlo 2-way finite automaton with n states are proved to be strongly recognized by a Monte Carlo 2-way finite automaton with no(n) states. This improves dramatically over the previously known result by M.Karpinski and R.Verbeek [10] which is also nontrivial since these languages can be nonregular [5]. For tally languages the increase in the number of states is proved to be only polynomial, and these languages are regular. More... »

PAGES

175-185

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-63248-4_15

DOI

http://dx.doi.org/10.1007/3-540-63248-4_15

DIMENSIONS

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


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 Mathematics and Computer Science, University of Latvia, Raina bulv. 29, Riga, Latvia", 
          "id": "http://www.grid.ac/institutes/grid.9845.0", 
          "name": [
            "Institute of Mathematics and Computer Science, University of Latvia, Raina bulv. 29, Riga, Latvia"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Ambainis", 
        "givenName": "Andris", 
        "id": "sg:person.013055041521.26", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013055041521.26"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Institute of Mathematics and Computer Science, University of Latvia, Raina bulv. 29, Riga, Latvia", 
          "id": "http://www.grid.ac/institutes/grid.9845.0", 
          "name": [
            "Institute of Mathematics and Computer Science, University of Latvia, Raina bulv. 29, Riga, Latvia"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Freivalds", 
        "givenName": "R\u016bsi\u0146\u0161", 
        "id": "sg:person.014644001541.17", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014644001541.17"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, University of Bonn, 53117, Bonn, Germany", 
          "id": "http://www.grid.ac/institutes/grid.10388.32", 
          "name": [
            "Department of Computer Science, University of Bonn, 53117, Bonn, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Karpinski", 
        "givenName": "Marek", 
        "id": "sg:person.011636042271.02", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011636042271.02"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "1997", 
    "datePublishedReg": "1997-01-01", 
    "description": "Languages weakly recognized by a Monte Carlo 2-way finite automaton with n states are proved to be strongly recognized by a Monte Carlo 2-way finite automaton with no(n) states. This improves dramatically over the previously known result by M.Karpinski and R.Verbeek [10] which is also nontrivial since these languages can be nonregular [5]. For tally languages the increase in the number of states is proved to be only polynomial, and these languages are regular.", 
    "editor": [
      {
        "familyName": "Rolim", 
        "givenName": "Jos\u00e9", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-63248-4_15", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-63248-1", 
        "978-3-540-69247-8"
      ], 
      "name": "Randomization and Approximation Techniques in Computer Science", 
      "type": "Book"
    }, 
    "keywords": [
      "language", 
      "finite automata", 
      "automata", 
      "n states", 
      "strong recognition", 
      "state", 
      "tally", 
      "number of states", 
      "recognition", 
      "Monte Carlo", 
      "results", 
      "number", 
      "Carlo", 
      "increase"
    ], 
    "name": "Weak and strong recognition by 2-way randomized automata", 
    "pagination": "175-185", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1036048948"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-63248-4_15"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-63248-4_15", 
      "https://app.dimensions.ai/details/publication/pub.1036048948"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-12-01T06:52", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20221201/entities/gbq_results/chapter/chapter_379.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/3-540-63248-4_15"
  }
]
 

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-63248-4_15'

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-63248-4_15'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-63248-4_15'

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-63248-4_15'


 

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

90 TRIPLES      22 PREDICATES      39 URIs      32 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-63248-4_15 schema:about anzsrc-for:20
2 anzsrc-for:2004
3 schema:author N5cea2422c4d646cf9a9c07ef1d1ab97e
4 schema:datePublished 1997
5 schema:datePublishedReg 1997-01-01
6 schema:description Languages weakly recognized by a Monte Carlo 2-way finite automaton with n states are proved to be strongly recognized by a Monte Carlo 2-way finite automaton with no(n) states. This improves dramatically over the previously known result by M.Karpinski and R.Verbeek [10] which is also nontrivial since these languages can be nonregular [5]. For tally languages the increase in the number of states is proved to be only polynomial, and these languages are regular.
7 schema:editor N7d73d0275d444c188925835da775ab2c
8 schema:genre chapter
9 schema:isAccessibleForFree false
10 schema:isPartOf Nf9af0879e7fd4e59b6e9ea201f18cb68
11 schema:keywords Carlo
12 Monte Carlo
13 automata
14 finite automata
15 increase
16 language
17 n states
18 number
19 number of states
20 recognition
21 results
22 state
23 strong recognition
24 tally
25 schema:name Weak and strong recognition by 2-way randomized automata
26 schema:pagination 175-185
27 schema:productId Nbdeca49bc1a2499c96bea6df350b65e9
28 Nffb8bd26e6f347da8fc159173780f8f0
29 schema:publisher N285d0f1f094f4d1ea69ca4a63616aece
30 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036048948
31 https://doi.org/10.1007/3-540-63248-4_15
32 schema:sdDatePublished 2022-12-01T06:52
33 schema:sdLicense https://scigraph.springernature.com/explorer/license/
34 schema:sdPublisher N33882a6c03eb45a1aaa9b786ad534093
35 schema:url https://doi.org/10.1007/3-540-63248-4_15
36 sgo:license sg:explorer/license/
37 sgo:sdDataset chapters
38 rdf:type schema:Chapter
39 N12fcc75209da474e93ec4e75f8e014f1 schema:familyName Rolim
40 schema:givenName José
41 rdf:type schema:Person
42 N285d0f1f094f4d1ea69ca4a63616aece schema:name Springer Nature
43 rdf:type schema:Organisation
44 N33882a6c03eb45a1aaa9b786ad534093 schema:name Springer Nature - SN SciGraph project
45 rdf:type schema:Organization
46 N5cea2422c4d646cf9a9c07ef1d1ab97e rdf:first sg:person.013055041521.26
47 rdf:rest N71bc08103a864dc4ad55eb775c3a6e28
48 N71bc08103a864dc4ad55eb775c3a6e28 rdf:first sg:person.014644001541.17
49 rdf:rest N9d05e0e141be45e2b98bb89683c578ce
50 N7d73d0275d444c188925835da775ab2c rdf:first N12fcc75209da474e93ec4e75f8e014f1
51 rdf:rest rdf:nil
52 N9d05e0e141be45e2b98bb89683c578ce rdf:first sg:person.011636042271.02
53 rdf:rest rdf:nil
54 Nbdeca49bc1a2499c96bea6df350b65e9 schema:name doi
55 schema:value 10.1007/3-540-63248-4_15
56 rdf:type schema:PropertyValue
57 Nf9af0879e7fd4e59b6e9ea201f18cb68 schema:isbn 978-3-540-63248-1
58 978-3-540-69247-8
59 schema:name Randomization and Approximation Techniques in Computer Science
60 rdf:type schema:Book
61 Nffb8bd26e6f347da8fc159173780f8f0 schema:name dimensions_id
62 schema:value pub.1036048948
63 rdf:type schema:PropertyValue
64 anzsrc-for:20 schema:inDefinedTermSet anzsrc-for:
65 schema:name Language, Communication and Culture
66 rdf:type schema:DefinedTerm
67 anzsrc-for:2004 schema:inDefinedTermSet anzsrc-for:
68 schema:name Linguistics
69 rdf:type schema:DefinedTerm
70 sg:person.011636042271.02 schema:affiliation grid-institutes:grid.10388.32
71 schema:familyName Karpinski
72 schema:givenName Marek
73 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011636042271.02
74 rdf:type schema:Person
75 sg:person.013055041521.26 schema:affiliation grid-institutes:grid.9845.0
76 schema:familyName Ambainis
77 schema:givenName Andris
78 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013055041521.26
79 rdf:type schema:Person
80 sg:person.014644001541.17 schema:affiliation grid-institutes:grid.9845.0
81 schema:familyName Freivalds
82 schema:givenName Rūsiņš
83 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014644001541.17
84 rdf:type schema:Person
85 grid-institutes:grid.10388.32 schema:alternateName Department of Computer Science, University of Bonn, 53117, Bonn, Germany
86 schema:name Department of Computer Science, University of Bonn, 53117, Bonn, Germany
87 rdf:type schema:Organization
88 grid-institutes:grid.9845.0 schema:alternateName Institute of Mathematics and Computer Science, University of Latvia, Raina bulv. 29, Riga, Latvia
89 schema:name Institute of Mathematics and Computer Science, University of Latvia, Raina bulv. 29, Riga, Latvia
90 rdf:type schema:Organization
 




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


...