Abstract | ||
---|---|---|
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. |
Year | DOI | Venue |
---|---|---|
2020 | 10.1016/j.tcs.2019.12.037 | Theoretical Computer Science |
Keywords | Field | DocType |
Automata,Automaton group,Automaton semigroup,Expandability,Growth,Orbital graph | Discrete mathematics,Combinatorics,Algebraic number,Nondeterministic algorithm,Suffix,Upper and lower bounds,Automaton,Prefix,Decidability,Invertible matrix,Mathematics | Journal |
Volume | ISSN | Citations |
809 | 0304-3975 | 1 |
PageRank | References | Authors |
0.39 | 0 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Daniele D'Angeli | 1 | 29 | 7.01 |
Emanuele Rodaro | 2 | 55 | 15.63 |
Jan Philipp Wächter | 3 | 3 | 3.57 |