Automatic logarithm and associated measures
We introduce the notion of the automatic logarithm \(\operatorname{Log}_{\mathcal A}(\mathcal B)\) of a finite initial Mealy automaton \(\mathcal B\), with another automaton \(\mathcal A\) as the base. It allows one to find for any input word \(w\) a power \(n\) such that \(\mathcal B(w)=\mathcal A^...
Saved in:
| Date: | 2023 |
|---|---|
| Main Authors: | , , |
| Format: | Article |
| Language: | English |
| Published: |
Lugansk National Taras Shevchenko University
2023
|
| Subjects: | |
| Online Access: | https://admjournal.luguniv.edu.ua/index.php/adm/article/view/2014 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Algebra and Discrete Mathematics |
Institution
Algebra and Discrete Mathematics| id |
admjournalluguniveduua-article-2014 |
|---|---|
| record_format |
ojs |
| spelling |
admjournalluguniveduua-article-20142023-02-08T16:55:57Z Automatic logarithm and associated measures Grigorchuk, R. Kogan, R. Vorobets, Y. Mealy automaton, Moore machine, regular rooted tree, Markov measure, finite-state measure 20E08, 37B10, 60B05, 68Q45 We introduce the notion of the automatic logarithm \(\operatorname{Log}_{\mathcal A}(\mathcal B)\) of a finite initial Mealy automaton \(\mathcal B\), with another automaton \(\mathcal A\) as the base. It allows one to find for any input word \(w\) a power \(n\) such that \(\mathcal B(w)=\mathcal A^n(w)\). The purpose is to study the expanding properties of graphs describing the action of the group generated by \(\mathcal A\) and \(\mathcal B\) on input words of a fixed length interpreted as levels of a regular \(d\)-ary rooted tree \(\mathcal T\). Formally, the automatic logarithm is a single map \(\operatorname{Log}_{\mathcal A}(\mathcal B)\colon\partial \mathcal T \rightarrow \mathbb{Z}_d\) from the boundary of the tree to the \(d\)-adic integers. Under the assumption that the action of the automaton \(\mathcal A\) on the tree \(\mathcal T\) is level-transitive and of bounded activity, we show that \(\operatorname{Log}_{\mathcal A}(\mathcal B)\) can be computed by a Moore machine. The distribution of values of the automatic logarithm yields a probabilistic measure \(\mu\) on \(\partial \mathcal T\), which in some cases can be computed by a Mealy-type machine (we then say that \(\mu\) is finite-state). We provide a criterion to determine whether \(\mu\) is finite-state. A number of examples with \(\mathcal A\) being the adding machine are considered. Lugansk National Taras Shevchenko University 2023-02-08 Article Article Peer-reviewed Article application/pdf https://admjournal.luguniv.edu.ua/index.php/adm/article/view/2014 10.12958/adm2014 Algebra and Discrete Mathematics; Vol 34, No 1 (2022) 2415-721X 1726-3255 en https://admjournal.luguniv.edu.ua/index.php/adm/article/view/2014/pdf https://admjournal.luguniv.edu.ua/index.php/adm/article/downloadSuppFile/2014/1004 https://admjournal.luguniv.edu.ua/index.php/adm/article/downloadSuppFile/2014/1005 https://admjournal.luguniv.edu.ua/index.php/adm/article/downloadSuppFile/2014/1006 Copyright (c) 2023 Algebra and Discrete Mathematics |
| institution |
Algebra and Discrete Mathematics |
| baseUrl_str |
|
| datestamp_date |
2023-02-08T16:55:57Z |
| collection |
OJS |
| language |
English |
| topic |
Mealy automaton Moore machine regular rooted tree Markov measure finite-state measure 20E08 37B10 60B05 68Q45 |
| spellingShingle |
Mealy automaton Moore machine regular rooted tree Markov measure finite-state measure 20E08 37B10 60B05 68Q45 Grigorchuk, R. Kogan, R. Vorobets, Y. Automatic logarithm and associated measures |
| topic_facet |
Mealy automaton Moore machine regular rooted tree Markov measure finite-state measure 20E08 37B10 60B05 68Q45 |
| format |
Article |
| author |
Grigorchuk, R. Kogan, R. Vorobets, Y. |
| author_facet |
Grigorchuk, R. Kogan, R. Vorobets, Y. |
| author_sort |
Grigorchuk, R. |
| title |
Automatic logarithm and associated measures |
| title_short |
Automatic logarithm and associated measures |
| title_full |
Automatic logarithm and associated measures |
| title_fullStr |
Automatic logarithm and associated measures |
| title_full_unstemmed |
Automatic logarithm and associated measures |
| title_sort |
automatic logarithm and associated measures |
| description |
We introduce the notion of the automatic logarithm \(\operatorname{Log}_{\mathcal A}(\mathcal B)\) of a finite initial Mealy automaton \(\mathcal B\), with another automaton \(\mathcal A\) as the base. It allows one to find for any input word \(w\) a power \(n\) such that \(\mathcal B(w)=\mathcal A^n(w)\). The purpose is to study the expanding properties of graphs describing the action of the group generated by \(\mathcal A\) and \(\mathcal B\) on input words of a fixed length interpreted as levels of a regular \(d\)-ary rooted tree \(\mathcal T\). Formally, the automatic logarithm is a single map \(\operatorname{Log}_{\mathcal A}(\mathcal B)\colon\partial \mathcal T \rightarrow \mathbb{Z}_d\) from the boundary of the tree to the \(d\)-adic integers. Under the assumption that the action of the automaton \(\mathcal A\) on the tree \(\mathcal T\) is level-transitive and of bounded activity, we show that \(\operatorname{Log}_{\mathcal A}(\mathcal B)\) can be computed by a Moore machine. The distribution of values of the automatic logarithm yields a probabilistic measure \(\mu\) on \(\partial \mathcal T\), which in some cases can be computed by a Mealy-type machine (we then say that \(\mu\) is finite-state). We provide a criterion to determine whether \(\mu\) is finite-state. A number of examples with \(\mathcal A\) being the adding machine are considered. |
| publisher |
Lugansk National Taras Shevchenko University |
| publishDate |
2023 |
| url |
https://admjournal.luguniv.edu.ua/index.php/adm/article/view/2014 |
| work_keys_str_mv |
AT grigorchukr automaticlogarithmandassociatedmeasures AT koganr automaticlogarithmandassociatedmeasures AT vorobetsy automaticlogarithmandassociatedmeasures |
| first_indexed |
2025-12-02T15:35:19Z |
| last_indexed |
2025-12-02T15:35:19Z |
| _version_ |
1850411287267246080 |