Source author record

Emanuele Rodaro

Emanuele Rodaro appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Catalog footprint

What is connected

18works
6topics
4close collaborators

Actions

Connect this record

Log in to claim

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

18 published item(s)

preprint2021arXiv

On an uncountable family of graphs whose spectrum is a Cantor set

For each $p\geq 1$, the star automaton group $\mathcal{G}_{S_p}$ is an automaton group which can be defined starting from a star graph on $p+1$ vertices. We study Schreier graphs associated with the action of the group $\mathcal{G}_{S_p}$ on the regular rooted tree $T_{p+1}$ of degree $p+1$ and on its boundary $\partial T_{p+1}$. With the transitive action on the $n$-th level of $T_{p+1}$ is associated a finite Schreier graph $Γ^p_n$, whereas there exist uncountably many orbits of the action on the boundary, represented by infinite Schreier graphs which are obtained as limits of the sequence $\{Γ_n^p\}_{n\geq 1}$ in the Gromov-Hausdorff topology. We obtain an explicit description of the spectrum of the graphs $\{Γ_n^p\}_{n\geq 1}$. Then, by using amenability of $\mathcal{G}_{S_p}$, we prove that the spectrum of each infinite Schreier graph is the union of a Cantor set of zero Lebesgue measure, which is the Julia set of the quadratic map $f_p(z) = z^2-2(p-1)z -2p$, and a countable collection of isolated points supporting the KNS spectral measure. We also give a complete classification of the infinite Schreier graphs up to isomorphism of unrooted graphs, showing that they may have $1$, $2$ or $2p$ ends, and that the case of $1$ end is generic with respect to the uniform measure on $\partial T_{p+1}$.

preprint2020arXiv

Automaton Semigroups and Groups: On the Undecidability of Problems Related to Freeness and Finiteness

In this paper, we study algorithmic problems for automaton semigroups and automaton groups related to freeness and finiteness. In the course of this study, we also exhibit some connections between the algebraic structure of automaton (semi)groups and their dynamics on the boundary. First, we show that it is undecidable to check whether the group generated by a given invertible automaton has a positive relation, i.e. a relation p = 1 such that p only contains positive generators. Besides its obvious relation to the freeness of the group, the absence of positive relations has previously been studied and is connected to the triviality of some stabilizers of the boundary. We show that the emptiness of the set of positive relations is equivalent to the dynamical property that all (directed positive) orbital graphs centered at non-singular points are acyclic. Gillibert showed that the finiteness problem for automaton semigroups is undecidable. In the second part of the paper, we show that this undecidability result also holds if the input is restricted to be bi-reversible and invertible (but, in general, not complete). As an immediate consequence, we obtain that the finiteness problem for automaton subsemigroups of semigroups generated by invertible, yet partial automata, so called automaton-inverse semigroups, is also undecidable. Erratum: Contrary to a statement in a previous version of the paper, our approach does not show that that the freeness problem for automaton semigroups is undecidable. We discuss this in an erratum at the end of the paper.

preprint2020arXiv

Circular automata synchronize with high probability

In this paper we prove that a uniformly distributed random circular automaton $\mathcal{A}_n$ of order $n$ synchronizes with high probability (whp). More precisely, we prove that $$ \mathbb{P}\left[\mathcal{A}_n \text{ synchronizes}\right] = 1- O\left(\frac{1}{n}\right). $$ The main idea of the proof is to translate the synchronization problem into properties of a random matrix; these properties are then handled with tools of the probabilistic method. Additionally, we provide an upper bound for the probability of synchronization of circular automata in terms of chromatic polynomials of circulant graphs.

preprint2020arXiv

Infinite Automaton Semigroups and Groups Have Infinite Orbits

We show that an automaton group or semigroup is infinite if and only if it admits an $ω$-word (i. e. a right-infinite word) with an infinite orbit, which solves an open problem communicated to us by Ievgen V. Bondarenko. In fact, we prove a generalization of this result, which can be applied to show that finitely generated subgroups and subsemigroups as well as principal left ideals of automaton semigroups are infinite if and only if there is an $ω$ -word with an infinite orbit under their action. The proof also shows some interesting connections between the automaton semigroup and its dual. Finally, our result is interesting from an algorithmic perspective as it allows for a reformulation of the finiteness problem for automaton groups and semigroups.

preprint2020arXiv

On the Orbits of Automaton Semigroups and Groups

We investigate the orbits of automaton semigroups and groups to obtain algorithmic and structural results, both for general automata but also for some special subclasses. First, we show that a more general version of the finiteness problem for automaton groups is undecidable. This problem is equivalent to the finiteness problem for left principal ideals in automaton semigroups generated by complete and reversible automata. Then, we look at $ω$-word (i.e. right infinite words) with a finite orbit. We show that every automaton yielding an $ω$-word with a finite orbit already yields an ultimately periodic one, which is not periodic in general, however. On the algorithmic side, we observe that it is not possible to decide whether a given periodic $ω$-word has an infinite orbit and that we cannot check whether a given reversible and complete automaton admits an $ω$-word with a finite orbit, a reciprocal problem to the finiteness problem for automaton semigroups in the reversible case. Finally, we look at automaton groups generated by reversible but not bi-reversible automata and show that many words have infinite orbits under the action of such automata.

preprint2020arXiv

On the Structure Theory of Partial Automaton Semigroups

We study automaton structures, i.e. groups, monoids and semigroups generated by an automaton, which, in this context, means a deterministic finite-state letter-to-letter transducer. Instead of considering only complete automata, we specifically investigate semigroups generated by partial automata. First, we show that the class of semigroups generated by partial automata coincides with the class of semigroups generated by complete automata if and only if the latter class is closed under removing a previously adjoined zero, which is an open problem in (complete) automaton semigroup theory stated by Cain. Then, we show that no semidirect product (and, thus, also no direct product) of an arbitrary semigroup with a (non-trivial) subsemigroup of the free monogenic semigroup is an automaton semigroup. Finally, we concentrate on inverse semigroups generated by invertible but partial automata, which we call automaton-inverse semigroups, and show that any inverse automaton semigroup can be generated by such an automaton (showing that automaton-inverse semigroups and inverse automaton semigroups coincide).

preprint2020arXiv

Orbit Expandability of Automaton Semigroups and Groups

We introduce the notion of expandability in the context of automaton semigroups and groups: a word is k-expandable if one can append a suffix to it such that the size of the orbit under the action of the automaton increases by at least k. This definition is motivated by the question which ω-words admit infinite orbits: for such a word, every prefix is expandable. In this paper, we show that, on input of a word u, an automaton T and a number k, it is decidable to check whether u is k-expandable with respect to the action of T. In fact, this can be done in exponential nondeterministic space. From this nondeterministic algorithm, we obtain a bound on the length of a potential orbit-increasing suffix x. Moreover, we investigate the situation if the automaton is invertible and generates a group. In this case, we give an algebraic characterization for the expandability of a word based on its shifted stabilizer. We also give a more efficient algorithm to decide expandability of a word in the case of automaton groups, which allows us to improve the upper bound on the maximal orbit-increasing suffix length. Then, we investigate the situation for reversible (and complete) automata and obtain that every word is expandable with respect to these automata. Finally, we give a lower bound example for the length of an orbit-increasing suffix.

preprint2014arXiv

A geometric approach to (semi)-groups defined by automata via dual transducers

We give a geometric approach to groups defined by automata via the notion of enriched dual of an inverse transducer. Using this geometric correspondence we first provide some finiteness results, then we consider groups generated by the dual of Cayley type of machines. Lastly, we address the problem of the study of the action of these groups in the boundary. We show that examples of groups having essentially free actions without critical points lie in the class of groups defined by the transducers whose enriched dual generate a torsion-free semigroup. Finally, we provide necessary and sufficient conditions to have finite Schreier graphs on the boundary yielding to the decidability of the algorithmic problem of checking the existence of Schreier graphs on the boundary whose cardinalities are upper bounded by some fixed integer.

preprint2014arXiv

Freeness of automata groups vs boundary dynamics

We prove that the boundary dynamics of the (semi)group generated by the enriched dual transducer characterizes the algebraic property of being free for an automaton group. We specialize this result to the class of bireversible transducers and we show that the property of being not free is equivalent to have a finite Schreier graph in the boundary of the enriched dual pointed on some essentially non-trivial point. From these results we derive some consequences from the dynamical, algorithmic and algebraic point of view. In the last part of the paper we address the problem of finding examples of non-bireversible transducers defining free groups, we show examples of transducers with sink accessible from every state which generate free groups, and, in general, we link this problem to the nonexistence of certain words with interesting combinatorial and geometrical properties.

preprint2014arXiv

Representation of (Left) Ideal Regular Languages by Synchronizing Automata

We follow language theoretic approach to synchronizing automata and Černý's conjecture initiated in a series of recent papers. We find a precise lower bound for the reset complexity of a principal ideal languages. Also we show a strict connection between principal left ideals and synchronizing automata. We characterize regular languages whose minimal deterministic finite automaton is synchronizing and possesses a reset word belonging to the recognized language.

preprint2013arXiv

A multi-lane traffic simulation model via continuous cellular automata

Traffic models based on cellular automata have high computational efficiency because of their simplicity in describing unrealistic vehicular behavior and the versatility of cellular automata to be implemented on parallel processing. On the other hand, the other microscopic traffic models such as car-following models are computationally more expensive, but they have more realistic driver behaviors and detailed vehicle characteristics. We propose a new class between these two categories, defining a traffic model based on continuous cellular automata where we combine the efficiency of cellular automata models with the accuracy of the other microscopic models. More precisely, we introduce a stochastic cellular automata traffic model in which the space is not coarse-grain but continuous. The continuity also allows us to embed a multi-agent fuzzy system proposed to handle uncertainties in decision making on road traffic. Therefore, we simulate different driver behaviors and study the effect of various compositions of vehicles within the traffic stream from the macroscopic point of view. The experimental results show that our model is able to reproduce the typical traffic flow phenomena showing a variety of effects due to the heterogeneity of traffic.

preprint2013arXiv

Groups and Semigroups Defined by Colorings of Synchronizing Automata

In this paper we combine the algebraic properties of Mealy machines generating self-similar groups and the combinatorial properties of the corresponding deterministic finite automata (DFA). In particular, we relate bounded automata to finitely generated synchronizing automata and characterize finite automata groups in terms of nilpotency of the corresponding DFA. Moreover, we present a decidable sufficient condition to have free semigroups in an automaton group. A series of examples and applications is widely discussed, in particular we show a way to color the De Bruijn automata into Mealy automata whose associated semigroups are free, and we present some structural results related to the associated groups.

preprint2013arXiv

Maximal subgroups of amalgams of finite inverse semigroups

We use the description of the Schutzenberger automata for amalgams of finite inverse semigroups given by Cherubini, Meakin, Piochi to obtain structural results for such amalgams. Schutzenberger automata, in the case of amalgams of finite inverse semigroups, are automata with special structure possessing finite subgraphs, that contain all essential information related to the whole automaton. Using this crucial fact, and the Bass-Serre theory, we show that the maximal subgroups of an amalgamated free-product are either isomorphic to certain subgroups of the original semigroups or can be described as fundamental groups of particular finite graphs of groups build from the maximal subgroups of the original semigroups.

preprint2012arXiv

Union-Closed vs Upward-Closed Families of Finite Sets

A finite family $\mathrsfs{F}$ of subsets of a finite set $X$ is union-closed whenever $f,g\in\mathrsfs{F}$ implies $f\cup g\in\mathrsfs{F}$. These families are well known because of Frankl's conjecture. In this paper we developed further the connection between union-closed families and upward-closed families started in Reimer (2003) using rising operators. With these techniques we are able to obtain tight lower bounds to the average of the length of the elements of $\mathrsfs{F}$ and to prove that the number of joint-irreducible elements of $\mathrsfs{F}$ can not exceed $2{n\choose \lfloor n/2\rfloor}+{n\choose \lfloor n/2\rfloor+1}$ where $|X| = n$.

preprint2011arXiv

Amalgams of inverse semigroups and reversible two-counter machines

We show that the word problem for an amalgam $[S_1,S_2;U,ω_1,ω_2]$ of inverse semigroups may be undecidable even if we assume $S_1$ and $S_2$ (and therefore $U$) to have finite $\mathcal{R}$-classes and $ω_1,ω_2$ to be computable functions, interrupting a series of positive decidability results on the subject. This is achieved by encoding into an appropriate amalgam of inverse semigroups 2-counter machines with sufficient universality, and relating the nature of certain \sch graphs to sequences of computations in the machine.