The Power and Limitations of Uniform Samples in Testing Properties of Figures View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2018-07-31

AUTHORS

Piotr Berman, Meiram Murzabulatov, Sofya Raskhodnikova

ABSTRACT

We investigate testing of properties of 2-dimensional figures that consist of a black object on a white background. Given a parameter ϵ∈(0,1/2)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\epsilon }\in (0,1/2)$$\end{document}, a tester for a specified property has to accept with probability at least 2/3 if the input figure satisfies the property and reject with probability at least 2/3 if it is ϵ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\epsilon }$$\end{document}-far from satisfying the property. In general, property testers can query the color of any point in the input figure. We study the power of testers that get access only to uniform samples from the input figure. We show that for the property of being a half-plane, the uniform testers are as powerful as general testers: they require only O(ϵ-1)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O({\epsilon }^{-1})$$\end{document} samples. In contrast, we prove that convexity can be tested with O(ϵ-1)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O({\epsilon }^{-1})$$\end{document} queries by testers that can make queries of their choice while uniform testers for this property require Ω(ϵ-5/4)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varOmega ({\epsilon }^{-5/4})$$\end{document} samples. Previously, the fastest known tester for convexity needed Θ(ϵ-4/3)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varTheta ({\epsilon }^{-4/3})$$\end{document} queries. More... »

PAGES

1247-1266

References to SciGraph publications

  • 1999. Improved Testing Algorithms for Monotonicity in RANDOMIZATION, APPROXIMATION, AND COMBINATORIAL OPTIMIZATION. ALGORITHMS AND TECHNIQUES
  • 2000. Property Testing in Computational Geometry in ALGORITHMS - ESA 2000
  • 2016-07-12. Fast-Match: Fast Affine Template Matching in INTERNATIONAL JOURNAL OF COMPUTER VISION
  • 2016-04-22. Linearity Testing/Testing Hadamard Codes in ENCYCLOPEDIA OF ALGORITHMS
  • 2000-03. Testing Monotonicity in COMBINATORICA
  • 2016-04-22. Testing if an Array Is Sorted in ENCYCLOPEDIA OF ALGORITHMS
  • 2001-08-17. Property Testing with Geometric Queries in ALGORITHMS — ESA 2001
  • 1987. Algorithms in Combinatorial Geometry in NONE
  • 2009-08-29. Testing Periodicity in ALGORITHMICA
  • 2010. Property Testing, Current Research and Surveys in NONE
  • 2003. Approximate Testing of Visual Properties in APPROXIMATION, RANDOMIZATION, AND COMBINATORIAL OPTIMIZATION.. ALGORITHMS AND TECHNIQUES
  • 2002-02. Property Testing in Bounded Degree Graphs in ALGORITHMICA
  • 1992. Learning convex sets under uniform distribution in DATA STRUCTURES AND EFFICIENT ALGORITHMS
  • 2004. Testing Geometric Convexity in FSTTCS 2004: FOUNDATIONS OF SOFTWARE TECHNOLOGY AND THEORETICAL COMPUTER SCIENCE
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s00453-018-0467-9

    DOI

    http://dx.doi.org/10.1007/s00453-018-0467-9

    DIMENSIONS

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


    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/21", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "History and Archaeology", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/2103", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Historical Studies", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Pennsylvania State University, University Park, USA", 
              "id": "http://www.grid.ac/institutes/grid.29857.31", 
              "name": [
                "Pennsylvania State University, University Park, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Berman", 
            "givenName": "Piotr", 
            "id": "sg:person.01274506210.27", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01274506210.27"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Pennsylvania State University, University Park, USA", 
              "id": "http://www.grid.ac/institutes/grid.29857.31", 
              "name": [
                "Pennsylvania State University, University Park, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Murzabulatov", 
            "givenName": "Meiram", 
            "id": "sg:person.011013132114.05", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011013132114.05"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Boston University, Boston, USA", 
              "id": "http://www.grid.ac/institutes/grid.189504.1", 
              "name": [
                "Boston University, Boston, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Raskhodnikova", 
            "givenName": "Sofya", 
            "id": "sg:person.07502404747.45", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07502404747.45"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/3-540-44676-1_22", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1053500578", 
              "https://doi.org/10.1007/3-540-44676-1_22"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s004930070011", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1033268083", 
              "https://doi.org/10.1007/s004930070011"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-61568-9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1049996833", 
              "https://doi.org/10.1007/978-3-642-61568-9"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-16367-8", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1035758014", 
              "https://doi.org/10.1007/978-3-642-16367-8"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-45253-2_15", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1052879480", 
              "https://doi.org/10.1007/3-540-45253-2_15"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-48413-4_10", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1049264838", 
              "https://doi.org/10.1007/978-3-540-48413-4_10"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00453-001-0078-7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1004175003", 
              "https://doi.org/10.1007/s00453-001-0078-7"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-45198-3_31", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1004005510", 
              "https://doi.org/10.1007/978-3-540-45198-3_31"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00453-009-9351-y", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1015498195", 
              "https://doi.org/10.1007/s00453-009-9351-y"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s11263-016-0926-1", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1013038437", 
              "https://doi.org/10.1007/s11263-016-0926-1"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-30538-5_39", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1041646269", 
              "https://doi.org/10.1007/978-3-540-30538-5_39"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-55488-2_28", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1052476962", 
              "https://doi.org/10.1007/3-540-55488-2_28"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-1-4939-2864-4_700", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1112905245", 
              "https://doi.org/10.1007/978-1-4939-2864-4_700"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-1-4939-2864-4_202", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1043023640", 
              "https://doi.org/10.1007/978-1-4939-2864-4_202"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2018-07-31", 
        "datePublishedReg": "2018-07-31", 
        "description": "We investigate testing of properties of 2-dimensional figures that consist of a black object on a white background. Given a parameter \u03f5\u2208(0,1/2)\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$${\\epsilon }\\in (0,1/2)$$\\end{document}, a tester for a specified property has to accept with probability at least 2/3 if the input figure satisfies the property and reject with probability at least 2/3 if it is \u03f5\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$${\\epsilon }$$\\end{document}-far from satisfying the property. In general, property testers can query the color of any point in the input figure. We study the power of testers that get access only to uniform samples from the input figure. We show that for the property of being a half-plane, the uniform testers are as powerful as general testers: they require only O(\u03f5-1)\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$O({\\epsilon }^{-1})$$\\end{document} samples. In contrast, we prove that convexity can be tested with O(\u03f5-1)\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$O({\\epsilon }^{-1})$$\\end{document} queries by testers that can make queries of their choice while uniform testers for this property require \u03a9(\u03f5-5/4)\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$\\varOmega ({\\epsilon }^{-5/4})$$\\end{document} samples. Previously, the fastest known tester for convexity needed \u0398(\u03f5-4/3)\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$\\varTheta ({\\epsilon }^{-4/3})$$\\end{document} queries.", 
        "genre": "article", 
        "id": "sg:pub.10.1007/s00453-018-0467-9", 
        "isAccessibleForFree": true, 
        "isFundedItemOf": [
          {
            "id": "sg:grant.3580787", 
            "type": "MonetaryGrant"
          }
        ], 
        "isPartOf": [
          {
            "id": "sg:journal.1047644", 
            "issn": [
              "0178-4617", 
              "1432-0541"
            ], 
            "name": "Algorithmica", 
            "publisher": "Springer Nature", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "3", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "81"
          }
        ], 
        "keywords": [
          "black objects", 
          "uniform samples", 
          "probability", 
          "property tester", 
          "convexity", 
          "testing properties", 
          "properties", 
          "testing of properties", 
          "objects", 
          "parameters", 
          "input figures", 
          "point", 
          "power", 
          "figures", 
          "choice", 
          "background", 
          "samples", 
          "queries", 
          "limitations", 
          "testing", 
          "white background", 
          "tester", 
          "color", 
          "contrast", 
          "access"
        ], 
        "name": "The Power and Limitations of Uniform Samples in Testing Properties of Figures", 
        "pagination": "1247-1266", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1105927114"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s00453-018-0467-9"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s00453-018-0467-9", 
          "https://app.dimensions.ai/details/publication/pub.1105927114"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2022-08-04T17:05", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-springernature-scigraph/baseset/20220804/entities/gbq_results/article/article_767.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://doi.org/10.1007/s00453-018-0467-9"
      }
    ]
     

    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/s00453-018-0467-9'

    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/s00453-018-0467-9'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00453-018-0467-9'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00453-018-0467-9'


     

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

    157 TRIPLES      21 PREDICATES      63 URIs      41 LITERALS      6 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s00453-018-0467-9 schema:about anzsrc-for:21
    2 anzsrc-for:2103
    3 schema:author N02530bbad0b247189321f90ebe178eec
    4 schema:citation sg:pub.10.1007/3-540-44676-1_22
    5 sg:pub.10.1007/3-540-45253-2_15
    6 sg:pub.10.1007/3-540-55488-2_28
    7 sg:pub.10.1007/978-1-4939-2864-4_202
    8 sg:pub.10.1007/978-1-4939-2864-4_700
    9 sg:pub.10.1007/978-3-540-30538-5_39
    10 sg:pub.10.1007/978-3-540-45198-3_31
    11 sg:pub.10.1007/978-3-540-48413-4_10
    12 sg:pub.10.1007/978-3-642-16367-8
    13 sg:pub.10.1007/978-3-642-61568-9
    14 sg:pub.10.1007/s00453-001-0078-7
    15 sg:pub.10.1007/s00453-009-9351-y
    16 sg:pub.10.1007/s004930070011
    17 sg:pub.10.1007/s11263-016-0926-1
    18 schema:datePublished 2018-07-31
    19 schema:datePublishedReg 2018-07-31
    20 schema:description We investigate testing of properties of 2-dimensional figures that consist of a black object on a white background. Given a parameter ϵ∈(0,1/2)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\epsilon }\in (0,1/2)$$\end{document}, a tester for a specified property has to accept with probability at least 2/3 if the input figure satisfies the property and reject with probability at least 2/3 if it is ϵ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\epsilon }$$\end{document}-far from satisfying the property. In general, property testers can query the color of any point in the input figure. We study the power of testers that get access only to uniform samples from the input figure. We show that for the property of being a half-plane, the uniform testers are as powerful as general testers: they require only O(ϵ-1)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O({\epsilon }^{-1})$$\end{document} samples. In contrast, we prove that convexity can be tested with O(ϵ-1)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O({\epsilon }^{-1})$$\end{document} queries by testers that can make queries of their choice while uniform testers for this property require Ω(ϵ-5/4)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varOmega ({\epsilon }^{-5/4})$$\end{document} samples. Previously, the fastest known tester for convexity needed Θ(ϵ-4/3)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varTheta ({\epsilon }^{-4/3})$$\end{document} queries.
    21 schema:genre article
    22 schema:isAccessibleForFree true
    23 schema:isPartOf N8ce86f17c1e64988ae57e16a3625e23f
    24 Ndcd9945ea0394f5f8455bae745c4de42
    25 sg:journal.1047644
    26 schema:keywords access
    27 background
    28 black objects
    29 choice
    30 color
    31 contrast
    32 convexity
    33 figures
    34 input figures
    35 limitations
    36 objects
    37 parameters
    38 point
    39 power
    40 probability
    41 properties
    42 property tester
    43 queries
    44 samples
    45 tester
    46 testing
    47 testing of properties
    48 testing properties
    49 uniform samples
    50 white background
    51 schema:name The Power and Limitations of Uniform Samples in Testing Properties of Figures
    52 schema:pagination 1247-1266
    53 schema:productId N4348e79ce1e84d1f94d7a5e2282d5788
    54 Na7cc2db6029c4b73b0800df8562d0d35
    55 schema:sameAs https://app.dimensions.ai/details/publication/pub.1105927114
    56 https://doi.org/10.1007/s00453-018-0467-9
    57 schema:sdDatePublished 2022-08-04T17:05
    58 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    59 schema:sdPublisher Na514dcea8218438d93ed311d1b701370
    60 schema:url https://doi.org/10.1007/s00453-018-0467-9
    61 sgo:license sg:explorer/license/
    62 sgo:sdDataset articles
    63 rdf:type schema:ScholarlyArticle
    64 N02530bbad0b247189321f90ebe178eec rdf:first sg:person.01274506210.27
    65 rdf:rest N0604e8dc08bb460babefef98963c347e
    66 N0604e8dc08bb460babefef98963c347e rdf:first sg:person.011013132114.05
    67 rdf:rest Nd4934d5b45ef4de9b3febb749877412d
    68 N4348e79ce1e84d1f94d7a5e2282d5788 schema:name doi
    69 schema:value 10.1007/s00453-018-0467-9
    70 rdf:type schema:PropertyValue
    71 N8ce86f17c1e64988ae57e16a3625e23f schema:volumeNumber 81
    72 rdf:type schema:PublicationVolume
    73 Na514dcea8218438d93ed311d1b701370 schema:name Springer Nature - SN SciGraph project
    74 rdf:type schema:Organization
    75 Na7cc2db6029c4b73b0800df8562d0d35 schema:name dimensions_id
    76 schema:value pub.1105927114
    77 rdf:type schema:PropertyValue
    78 Nd4934d5b45ef4de9b3febb749877412d rdf:first sg:person.07502404747.45
    79 rdf:rest rdf:nil
    80 Ndcd9945ea0394f5f8455bae745c4de42 schema:issueNumber 3
    81 rdf:type schema:PublicationIssue
    82 anzsrc-for:21 schema:inDefinedTermSet anzsrc-for:
    83 schema:name History and Archaeology
    84 rdf:type schema:DefinedTerm
    85 anzsrc-for:2103 schema:inDefinedTermSet anzsrc-for:
    86 schema:name Historical Studies
    87 rdf:type schema:DefinedTerm
    88 sg:grant.3580787 http://pending.schema.org/fundedItem sg:pub.10.1007/s00453-018-0467-9
    89 rdf:type schema:MonetaryGrant
    90 sg:journal.1047644 schema:issn 0178-4617
    91 1432-0541
    92 schema:name Algorithmica
    93 schema:publisher Springer Nature
    94 rdf:type schema:Periodical
    95 sg:person.011013132114.05 schema:affiliation grid-institutes:grid.29857.31
    96 schema:familyName Murzabulatov
    97 schema:givenName Meiram
    98 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011013132114.05
    99 rdf:type schema:Person
    100 sg:person.01274506210.27 schema:affiliation grid-institutes:grid.29857.31
    101 schema:familyName Berman
    102 schema:givenName Piotr
    103 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01274506210.27
    104 rdf:type schema:Person
    105 sg:person.07502404747.45 schema:affiliation grid-institutes:grid.189504.1
    106 schema:familyName Raskhodnikova
    107 schema:givenName Sofya
    108 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07502404747.45
    109 rdf:type schema:Person
    110 sg:pub.10.1007/3-540-44676-1_22 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053500578
    111 https://doi.org/10.1007/3-540-44676-1_22
    112 rdf:type schema:CreativeWork
    113 sg:pub.10.1007/3-540-45253-2_15 schema:sameAs https://app.dimensions.ai/details/publication/pub.1052879480
    114 https://doi.org/10.1007/3-540-45253-2_15
    115 rdf:type schema:CreativeWork
    116 sg:pub.10.1007/3-540-55488-2_28 schema:sameAs https://app.dimensions.ai/details/publication/pub.1052476962
    117 https://doi.org/10.1007/3-540-55488-2_28
    118 rdf:type schema:CreativeWork
    119 sg:pub.10.1007/978-1-4939-2864-4_202 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043023640
    120 https://doi.org/10.1007/978-1-4939-2864-4_202
    121 rdf:type schema:CreativeWork
    122 sg:pub.10.1007/978-1-4939-2864-4_700 schema:sameAs https://app.dimensions.ai/details/publication/pub.1112905245
    123 https://doi.org/10.1007/978-1-4939-2864-4_700
    124 rdf:type schema:CreativeWork
    125 sg:pub.10.1007/978-3-540-30538-5_39 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041646269
    126 https://doi.org/10.1007/978-3-540-30538-5_39
    127 rdf:type schema:CreativeWork
    128 sg:pub.10.1007/978-3-540-45198-3_31 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004005510
    129 https://doi.org/10.1007/978-3-540-45198-3_31
    130 rdf:type schema:CreativeWork
    131 sg:pub.10.1007/978-3-540-48413-4_10 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049264838
    132 https://doi.org/10.1007/978-3-540-48413-4_10
    133 rdf:type schema:CreativeWork
    134 sg:pub.10.1007/978-3-642-16367-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035758014
    135 https://doi.org/10.1007/978-3-642-16367-8
    136 rdf:type schema:CreativeWork
    137 sg:pub.10.1007/978-3-642-61568-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049996833
    138 https://doi.org/10.1007/978-3-642-61568-9
    139 rdf:type schema:CreativeWork
    140 sg:pub.10.1007/s00453-001-0078-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004175003
    141 https://doi.org/10.1007/s00453-001-0078-7
    142 rdf:type schema:CreativeWork
    143 sg:pub.10.1007/s00453-009-9351-y schema:sameAs https://app.dimensions.ai/details/publication/pub.1015498195
    144 https://doi.org/10.1007/s00453-009-9351-y
    145 rdf:type schema:CreativeWork
    146 sg:pub.10.1007/s004930070011 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033268083
    147 https://doi.org/10.1007/s004930070011
    148 rdf:type schema:CreativeWork
    149 sg:pub.10.1007/s11263-016-0926-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013038437
    150 https://doi.org/10.1007/s11263-016-0926-1
    151 rdf:type schema:CreativeWork
    152 grid-institutes:grid.189504.1 schema:alternateName Boston University, Boston, USA
    153 schema:name Boston University, Boston, USA
    154 rdf:type schema:Organization
    155 grid-institutes:grid.29857.31 schema:alternateName Pennsylvania State University, University Park, USA
    156 schema:name Pennsylvania State University, University Park, USA
    157 rdf:type schema:Organization
     




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


    ...