Finding All Solutions of Equations in Free Groups and Monoids with Involution View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2014

AUTHORS

Volker Diekert , Artur Jeż , Wojciech Plandowski

ABSTRACT

The aim of this paper is to present a PSPACE algorithm which yields a finite graph of exponential size and which describes the set of all solutions of equations in free groups and monoids with involution in the presence of rational constraints. This became possible due to the recently invented recompression technique of the second author.He successfully applied the recompression technique for pure word equations without involution or rational constraints. In particular, his method could not be used as a black box for free groups (even without rational constraints). Actually, the presence of an involution (inverse elements) and rational constraints complicates the situation and some additional analysis is necessary. Still, the recompression technique is powerful enough to simplify proofs for many existing results in the literature. In particular, it simplifies proofs that solving word equations is in PSPACE (Plandowski 1999) and the corresponding result for equations in free groups with rational constraints (Diekert, Hagenah and Gutiérrez 2001). As a byproduct we obtain a direct proof that it is decidable in PSPACE whether or not the solution set is finite. More... »

PAGES

1-15

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-319-06686-8_1

DOI

http://dx.doi.org/10.1007/978-3-319-06686-8_1

DIMENSIONS

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


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/0103", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Numerical and Computational Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Institut f\u00fcr Formale Methoden der Informatik, University of Stuttgart, Germany", 
          "id": "http://www.grid.ac/institutes/grid.5719.a", 
          "name": [
            "Institut f\u00fcr Formale Methoden der Informatik, University of Stuttgart, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Diekert", 
        "givenName": "Volker", 
        "id": "sg:person.012621714747.48", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012621714747.48"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Institute of Informatics, University of Warsaw, Poland", 
          "id": "http://www.grid.ac/institutes/grid.12847.38", 
          "name": [
            "Institute of Computer Science, University of Wroclaw, Poland", 
            "Institute of Informatics, University of Warsaw, 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"
      }, 
      {
        "affiliation": {
          "alternateName": "Max Planck Institute f\u00fcr Informatik, Saarbr\u00fccken, Germany", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "Max Planck Institute f\u00fcr Informatik, Saarbr\u00fccken, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Plandowski", 
        "givenName": "Wojciech", 
        "id": "sg:person.010207617143.19", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010207617143.19"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2014", 
    "datePublishedReg": "2014-01-01", 
    "description": "The aim of this paper is to present a PSPACE algorithm which yields a finite graph of exponential size and which describes the set of all solutions of equations in free groups and monoids with involution in the presence of rational constraints. This became possible due to the recently invented recompression technique of the second author.He successfully applied the recompression technique for pure word equations without involution or rational constraints. In particular, his method could not be used as a\u00a0black box for free groups (even without rational constraints). Actually, the presence of an involution (inverse elements) and rational constraints complicates the situation and some additional analysis is necessary. Still, the recompression technique is powerful enough to simplify proofs for many existing results in the literature. In particular, it simplifies proofs that solving word equations is in PSPACE (Plandowski 1999) and the corresponding result for equations in free groups with rational constraints (Diekert, Hagenah and Guti\u00e9rrez 2001). As a byproduct we obtain a\u00a0direct proof that it is decidable in PSPACE whether or not the solution set is finite.", 
    "editor": [
      {
        "familyName": "Hirsch", 
        "givenName": "Edward A.", 
        "type": "Person"
      }, 
      {
        "familyName": "Kuznetsov", 
        "givenName": "Sergei O.", 
        "type": "Person"
      }, 
      {
        "familyName": "Pin", 
        "givenName": "Jean-\u00c9ric", 
        "type": "Person"
      }, 
      {
        "familyName": "Vereshchagin", 
        "givenName": "Nikolay K.", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-319-06686-8_1", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-319-06685-1", 
        "978-3-319-06686-8"
      ], 
      "name": "Computer Science - Theory and Applications", 
      "type": "Book"
    }, 
    "keywords": [
      "solution of equations", 
      "recompression technique", 
      "free group", 
      "word equations", 
      "rational constraints", 
      "finite graphs", 
      "solution set", 
      "existing results", 
      "PSPACE algorithm", 
      "equations", 
      "corresponding results", 
      "second author", 
      "exponential size", 
      "direct proof", 
      "constraints", 
      "monoids", 
      "PSPACE", 
      "proof", 
      "solution", 
      "involution", 
      "graph", 
      "set", 
      "black box", 
      "algorithm", 
      "technique", 
      "results", 
      "situation", 
      "size", 
      "analysis", 
      "byproducts", 
      "box", 
      "presence", 
      "literature", 
      "authors", 
      "Additional analyses", 
      "group", 
      "aim", 
      "paper", 
      "method"
    ], 
    "name": "Finding All Solutions of Equations in Free Groups and Monoids with Involution", 
    "pagination": "1-15", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1050228689"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-319-06686-8_1"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-319-06686-8_1", 
      "https://app.dimensions.ai/details/publication/pub.1050228689"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-10T10:49", 
    "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_360.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-319-06686-8_1"
  }
]
 

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-319-06686-8_1'

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-319-06686-8_1'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-06686-8_1'

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-319-06686-8_1'


 

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

135 TRIPLES      23 PREDICATES      65 URIs      58 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-319-06686-8_1 schema:about anzsrc-for:01
2 anzsrc-for:0103
3 schema:author N2d78f9136c0244708b6ea1f217798687
4 schema:datePublished 2014
5 schema:datePublishedReg 2014-01-01
6 schema:description The aim of this paper is to present a PSPACE algorithm which yields a finite graph of exponential size and which describes the set of all solutions of equations in free groups and monoids with involution in the presence of rational constraints. This became possible due to the recently invented recompression technique of the second author.He successfully applied the recompression technique for pure word equations without involution or rational constraints. In particular, his method could not be used as a black box for free groups (even without rational constraints). Actually, the presence of an involution (inverse elements) and rational constraints complicates the situation and some additional analysis is necessary. Still, the recompression technique is powerful enough to simplify proofs for many existing results in the literature. In particular, it simplifies proofs that solving word equations is in PSPACE (Plandowski 1999) and the corresponding result for equations in free groups with rational constraints (Diekert, Hagenah and Gutiérrez 2001). As a byproduct we obtain a direct proof that it is decidable in PSPACE whether or not the solution set is finite.
7 schema:editor N7d28a796b0694747bacf70034a545fc0
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf Nc4e1cb06a8bc47cfb0bdf0d2f3632e1d
12 schema:keywords Additional analyses
13 PSPACE
14 PSPACE algorithm
15 aim
16 algorithm
17 analysis
18 authors
19 black box
20 box
21 byproducts
22 constraints
23 corresponding results
24 direct proof
25 equations
26 existing results
27 exponential size
28 finite graphs
29 free group
30 graph
31 group
32 involution
33 literature
34 method
35 monoids
36 paper
37 presence
38 proof
39 rational constraints
40 recompression technique
41 results
42 second author
43 set
44 situation
45 size
46 solution
47 solution of equations
48 solution set
49 technique
50 word equations
51 schema:name Finding All Solutions of Equations in Free Groups and Monoids with Involution
52 schema:pagination 1-15
53 schema:productId N2a7e17cf8f434cc7a32e6d6f6d5c65a8
54 N96e1c40cd6bd427eacc04e2c6c37192c
55 schema:publisher N08e0f3d7689f457093d91ac2541b0ef5
56 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050228689
57 https://doi.org/10.1007/978-3-319-06686-8_1
58 schema:sdDatePublished 2022-05-10T10:49
59 schema:sdLicense https://scigraph.springernature.com/explorer/license/
60 schema:sdPublisher N2064f1e866b746c7bbb6b7661f08d854
61 schema:url https://doi.org/10.1007/978-3-319-06686-8_1
62 sgo:license sg:explorer/license/
63 sgo:sdDataset chapters
64 rdf:type schema:Chapter
65 N08e0f3d7689f457093d91ac2541b0ef5 schema:name Springer Nature
66 rdf:type schema:Organisation
67 N0adfa10a390b4308b6461c55b4f34a27 schema:familyName Vereshchagin
68 schema:givenName Nikolay K.
69 rdf:type schema:Person
70 N0c6cfd406a4d4128b1ee7fe63804054c rdf:first N3b3b06dd55f646bd8e9d28f9fe1761df
71 rdf:rest Nc37fdfd46d8f4209bc2e889e75aa9796
72 N2064f1e866b746c7bbb6b7661f08d854 schema:name Springer Nature - SN SciGraph project
73 rdf:type schema:Organization
74 N2a7e17cf8f434cc7a32e6d6f6d5c65a8 schema:name doi
75 schema:value 10.1007/978-3-319-06686-8_1
76 rdf:type schema:PropertyValue
77 N2d78f9136c0244708b6ea1f217798687 rdf:first sg:person.012621714747.48
78 rdf:rest N4c0cbab80c3e4b23a40da4c182a4d546
79 N3b3b06dd55f646bd8e9d28f9fe1761df schema:familyName Pin
80 schema:givenName Jean-Éric
81 rdf:type schema:Person
82 N4c0cbab80c3e4b23a40da4c182a4d546 rdf:first sg:person.015252371751.76
83 rdf:rest N4d065a6b7c3a4291a9f22e414408e824
84 N4d065a6b7c3a4291a9f22e414408e824 rdf:first sg:person.010207617143.19
85 rdf:rest rdf:nil
86 N4d7aad53462a4067b54d4caa2c3b5087 schema:familyName Kuznetsov
87 schema:givenName Sergei O.
88 rdf:type schema:Person
89 N663168e0ea064336ac9588fca67a4900 schema:familyName Hirsch
90 schema:givenName Edward A.
91 rdf:type schema:Person
92 N7d28a796b0694747bacf70034a545fc0 rdf:first N663168e0ea064336ac9588fca67a4900
93 rdf:rest Nd17c8a3420b24bcabd374e83bca3a416
94 N96e1c40cd6bd427eacc04e2c6c37192c schema:name dimensions_id
95 schema:value pub.1050228689
96 rdf:type schema:PropertyValue
97 Nc37fdfd46d8f4209bc2e889e75aa9796 rdf:first N0adfa10a390b4308b6461c55b4f34a27
98 rdf:rest rdf:nil
99 Nc4e1cb06a8bc47cfb0bdf0d2f3632e1d schema:isbn 978-3-319-06685-1
100 978-3-319-06686-8
101 schema:name Computer Science - Theory and Applications
102 rdf:type schema:Book
103 Nd17c8a3420b24bcabd374e83bca3a416 rdf:first N4d7aad53462a4067b54d4caa2c3b5087
104 rdf:rest N0c6cfd406a4d4128b1ee7fe63804054c
105 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
106 schema:name Mathematical Sciences
107 rdf:type schema:DefinedTerm
108 anzsrc-for:0103 schema:inDefinedTermSet anzsrc-for:
109 schema:name Numerical and Computational Mathematics
110 rdf:type schema:DefinedTerm
111 sg:person.010207617143.19 schema:affiliation grid-institutes:None
112 schema:familyName Plandowski
113 schema:givenName Wojciech
114 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010207617143.19
115 rdf:type schema:Person
116 sg:person.012621714747.48 schema:affiliation grid-institutes:grid.5719.a
117 schema:familyName Diekert
118 schema:givenName Volker
119 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012621714747.48
120 rdf:type schema:Person
121 sg:person.015252371751.76 schema:affiliation grid-institutes:grid.12847.38
122 schema:familyName Jeż
123 schema:givenName Artur
124 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015252371751.76
125 rdf:type schema:Person
126 grid-institutes:None schema:alternateName Max Planck Institute für Informatik, Saarbrücken, Germany
127 schema:name Max Planck Institute für Informatik, Saarbrücken, Germany
128 rdf:type schema:Organization
129 grid-institutes:grid.12847.38 schema:alternateName Institute of Informatics, University of Warsaw, Poland
130 schema:name Institute of Computer Science, University of Wroclaw, Poland
131 Institute of Informatics, University of Warsaw, Poland
132 rdf:type schema:Organization
133 grid-institutes:grid.5719.a schema:alternateName Institut für Formale Methoden der Informatik, University of Stuttgart, Germany
134 schema:name Institut für Formale Methoden der Informatik, University of Stuttgart, Germany
135 rdf:type schema:Organization
 




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


...