dc.contributor.author |
Khoussainov, B |
en |
dc.contributor.author |
Takisaka, T |
en |
dc.date.accessioned |
2018-07-18T04:42:50Z |
en |
dc.date.available |
2018-07-18T04:42:50Z |
en |
dc.date.issued |
2017 |
en |
dc.identifier.citation |
CDMTCS Research Reports CDMTCS-504 (2017) |
en |
dc.identifier.issn |
1178-3540 |
en |
dc.identifier.uri |
http://hdl.handle.net/2292/37491 |
en |
dc.description.abstract |
We introduce geometric consideration into the theory of formal languages. We aim to shed light on our understanding
of global patterns that occur on infinite strings. We utilise methods of geometric group theory. Our emphasis is on large scale geometries. Two infinite strings have the same large scale geometry if there are colour preserving bi-Lipschitz maps with distortions between the strings. Call these maps quasi-isometries. Introduction of large scale geometries
poses several questions. The first question asks to study the partial order induced by quasi-isometries. This partial
order compares large scale geometries; as such it presents an algebraic tool for classification of global patterns. We
prove there is a greatest large scale geometry and infinitely many minimal large scale geometries. The second question
is related to understanding the quasi-isometric maps on various classes of strings. The third question investigates the
sets of large scale geometries of strings accepted by computational models, e.g. B¨uchi automata. We provide an algorithm that describes large scale geometries of strings accepted by B¨uchi automata. This links large scale geometries with automata theory. The fourth question studies the complexity of the quasi-isometry problem. |
en |
dc.publisher |
Department of Computer Science, The University of Auckland, New Zealand |
en |
dc.relation.ispartofseries |
CDMTCS Research Report Series |
en |
dc.rights |
Items in ResearchSpace are protected by copyright, with all rights reserved, unless otherwise indicated. Previously published items are made available in accordance with the copyright policy of the publisher. |
en |
dc.rights.uri |
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm |
en |
dc.source.uri |
https://www.cs.auckland.ac.nz/research/groups/CDMTCS/researchreports/index.php |
en |
dc.title |
Large Scale Geometries of Infinite Strings |
en |
dc.type |
Technical Report |
en |
dc.subject.marsden |
Fields of Research |
en |
dc.rights.holder |
The author(s) |
en |
dc.rights.accessrights |
http://purl.org/eprint/accessRights/OpenAccess |
en |