Lifts, derandomization, and diameters of Schreier graphs of Mealy automata
DOI10.1007/s00493-016-3306-0zbMath1413.05159arXiv1407.4600OpenAlexW2963114196MaRDI QIDQ681602
Igor Pak, Anton Valentinovich Malyshev
Publication date: 12 February 2018
Published in: Combinatorica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1407.4600
diametergroup actions on treesMealy automata\(2\)-lifts of graphsautomaton groupfamilies of expandersSchreier graph of a Mealy automaton
Formal languages and automata (68Q45) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Algebraic theory of languages and automata (68Q70) Structural characterization of families of graphs (05C75) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Graph operations (line graphs, products, etc.) (05C76)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the conjugacy problem for finite-state automorphisms of regular rooted trees. With an appendix by Raphaël M. Jungers
- Some topics in the dynamics of group actions on rooted trees.
- Automata generating free products of groups of order 2.
- Lifts, discrepancy and nearly optimal spectral gap
- Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators
- On a series of finite automata defining free transformation groups.
- A free group of finite automata
- Discrete groups, expanding graphs and invariant measures. Appendix by Jonathan D. Rogawski
- A geometric approach to (semi)-groups defined by automata via dual transducers.
- Interlacing families. I: Bipartite Ramanujan graphs of all degrees
- Automata and square complexes.
- On a free group of transformations defined by an automaton.
- Expander graphs and their applications
- Classification of groups generated by 3-state automata over a 2-letter alphabet
- CONJUGATION IN TREE AUTOMORPHISM GROUPS
