One-Variable Word Equations in Linear Time View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2013

AUTHORS

Artur Jeż

ABSTRACT

In this paper we consider word equations with one variable (and arbitrary many appearances of it). A recent technique of recompression, which is applicable to general word equations, is shown to be suitable also in this case. While in general case it is non-deterministic, it determinises in case of one variable and the obtained running time is \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal{O}(n)$\end{document} (in RAM model). More... »

PAGES

324-335

Book

TITLE

Automata, Languages, and Programming

ISBN

978-3-642-39211-5
978-3-642-39212-2

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-39212-2_30

DOI

http://dx.doi.org/10.1007/978-3-642-39212-2_30

DIMENSIONS

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


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/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0102", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Applied Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Institute of Computer Science, University of Wroc\u0142aw, ul. Joliot-Curie 15, PL-50383, Wroc\u0142aw, Poland", 
          "id": "http://www.grid.ac/institutes/grid.8505.8", 
          "name": [
            "Max Planck Institute f\u00fcr Informatik, Campus E1 4, DE-66123, Saarbr\u00fccken, Germany", 
            "Institute of Computer Science, University of Wroc\u0142aw, ul. Joliot-Curie 15, PL-50383, Wroc\u0142aw, Poland"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Je\u017c", 
        "givenName": "Artur", 
        "id": "sg:person.015252371751.76", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015252371751.76"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2013", 
    "datePublishedReg": "2013-01-01", 
    "description": "In this paper we consider word equations with one variable (and arbitrary many appearances of it). A recent technique of recompression, which is applicable to general word equations, is shown to be suitable also in this case. While in general case it is non-deterministic, it determinises in case of one variable and the obtained running time is \\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}$\\mathcal{O}(n)$\\end{document} (in RAM model).", 
    "editor": [
      {
        "familyName": "Fomin", 
        "givenName": "Fedor V.", 
        "type": "Person"
      }, 
      {
        "familyName": "Freivalds", 
        "givenName": "R\u016bsi\u0146\u0161", 
        "type": "Person"
      }, 
      {
        "familyName": "Kwiatkowska", 
        "givenName": "Marta", 
        "type": "Person"
      }, 
      {
        "familyName": "Peleg", 
        "givenName": "David", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-39212-2_30", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-642-39211-5", 
        "978-3-642-39212-2"
      ], 
      "name": "Automata, Languages, and Programming", 
      "type": "Book"
    }, 
    "keywords": [
      "word equations", 
      "One-Variable Word Equations", 
      "general case", 
      "equations", 
      "linear time", 
      "recent techniques", 
      "variables", 
      "cases", 
      "technique", 
      "time", 
      "recompression", 
      "paper"
    ], 
    "name": "One-Variable Word Equations in Linear Time", 
    "pagination": "324-335", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1002595012"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-39212-2_30"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-39212-2_30", 
      "https://app.dimensions.ai/details/publication/pub.1002595012"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-10T10:55", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220509/entities/gbq_results/chapter/chapter_91.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-39212-2_30"
  }
]
 

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-642-39212-2_30'

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-642-39212-2_30'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-39212-2_30'

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-642-39212-2_30'


 

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

88 TRIPLES      23 PREDICATES      38 URIs      31 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-39212-2_30 schema:about anzsrc-for:01
2 anzsrc-for:0102
3 schema:author N3a5d937e2d6745b4a76179c7d658c339
4 schema:datePublished 2013
5 schema:datePublishedReg 2013-01-01
6 schema:description In this paper we consider word equations with one variable (and arbitrary many appearances of it). A recent technique of recompression, which is applicable to general word equations, is shown to be suitable also in this case. While in general case it is non-deterministic, it determinises in case of one variable and the obtained running time is \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal{O}(n)$\end{document} (in RAM model).
7 schema:editor N150547109d51467ab10503e222234d08
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf Na299e53d384f42e283caff923e89af98
12 schema:keywords One-Variable Word Equations
13 cases
14 equations
15 general case
16 linear time
17 paper
18 recent techniques
19 recompression
20 technique
21 time
22 variables
23 word equations
24 schema:name One-Variable Word Equations in Linear Time
25 schema:pagination 324-335
26 schema:productId N1010846f9862457ebfde72bd1d37f66c
27 Nf457f1ea12564d49ad42090f4dd37d7a
28 schema:publisher N7069983d66a8482cafb09a316e900fe6
29 schema:sameAs https://app.dimensions.ai/details/publication/pub.1002595012
30 https://doi.org/10.1007/978-3-642-39212-2_30
31 schema:sdDatePublished 2022-05-10T10:55
32 schema:sdLicense https://scigraph.springernature.com/explorer/license/
33 schema:sdPublisher Nd601ea4b0fdc4874a5aed96a2b70d884
34 schema:url https://doi.org/10.1007/978-3-642-39212-2_30
35 sgo:license sg:explorer/license/
36 sgo:sdDataset chapters
37 rdf:type schema:Chapter
38 N1010846f9862457ebfde72bd1d37f66c schema:name dimensions_id
39 schema:value pub.1002595012
40 rdf:type schema:PropertyValue
41 N11c4cdd598cf4ad8a405a239dcd7ecd5 schema:familyName Fomin
42 schema:givenName Fedor V.
43 rdf:type schema:Person
44 N150547109d51467ab10503e222234d08 rdf:first N11c4cdd598cf4ad8a405a239dcd7ecd5
45 rdf:rest N90005ff680a640ffa85cc35bdec3c26a
46 N3a5d937e2d6745b4a76179c7d658c339 rdf:first sg:person.015252371751.76
47 rdf:rest rdf:nil
48 N3e7a35fb3121425b8ab866b7a1649159 rdf:first N8f85e0699d8d48cd92dcdd31dbc7fb8b
49 rdf:rest Neb8d89b362ea4f47825c330cf95c66a5
50 N7069983d66a8482cafb09a316e900fe6 schema:name Springer Nature
51 rdf:type schema:Organisation
52 N8f85e0699d8d48cd92dcdd31dbc7fb8b schema:familyName Kwiatkowska
53 schema:givenName Marta
54 rdf:type schema:Person
55 N90005ff680a640ffa85cc35bdec3c26a rdf:first Nc55644747c5749ccabba2259f3b76df8
56 rdf:rest N3e7a35fb3121425b8ab866b7a1649159
57 Na299e53d384f42e283caff923e89af98 schema:isbn 978-3-642-39211-5
58 978-3-642-39212-2
59 schema:name Automata, Languages, and Programming
60 rdf:type schema:Book
61 Nc55644747c5749ccabba2259f3b76df8 schema:familyName Freivalds
62 schema:givenName Rūsiņš
63 rdf:type schema:Person
64 Nd601ea4b0fdc4874a5aed96a2b70d884 schema:name Springer Nature - SN SciGraph project
65 rdf:type schema:Organization
66 Ne934267d4c8c498f923c34aa7f4c3192 schema:familyName Peleg
67 schema:givenName David
68 rdf:type schema:Person
69 Neb8d89b362ea4f47825c330cf95c66a5 rdf:first Ne934267d4c8c498f923c34aa7f4c3192
70 rdf:rest rdf:nil
71 Nf457f1ea12564d49ad42090f4dd37d7a schema:name doi
72 schema:value 10.1007/978-3-642-39212-2_30
73 rdf:type schema:PropertyValue
74 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
75 schema:name Mathematical Sciences
76 rdf:type schema:DefinedTerm
77 anzsrc-for:0102 schema:inDefinedTermSet anzsrc-for:
78 schema:name Applied Mathematics
79 rdf:type schema:DefinedTerm
80 sg:person.015252371751.76 schema:affiliation grid-institutes:grid.8505.8
81 schema:familyName Jeż
82 schema:givenName Artur
83 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015252371751.76
84 rdf:type schema:Person
85 grid-institutes:grid.8505.8 schema:alternateName Institute of Computer Science, University of Wrocław, ul. Joliot-Curie 15, PL-50383, Wrocław, Poland
86 schema:name Institute of Computer Science, University of Wrocław, ul. Joliot-Curie 15, PL-50383, Wrocław, Poland
87 Max Planck Institute für Informatik, Campus E1 4, DE-66123, Saarbrücken, Germany
88 rdf:type schema:Organization
 




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


...