A New Hierarchy for Automaton Semigroups

DOI10.1142/S0129054120420046zbMath1474.68168OpenAlexW3119344436MaRDI QIDQ5859663

Laurent Bartholdi, Camille Noûs, Thibault Godin, Matthieu Picantin, Ines Klimann

Publication date: 19 April 2021

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0129054120420046

zbMATH Keywords

entropydecision problemhierarchyautomaton semigroup

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Semigroups in automata theory, linguistics, etc. (20M35)

Uses Software

• FR

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
• The word and order problems for self-similar and automata groups
• On transition functions of Mealy automata of finite growth.
• Automorphisms of one-rooted trees: growth, circuit structure, and acyclicity.
• On bireversible Mealy automata and the Burnside problem
• An automaton group with undecidable order and Engel problems
• The smallest Mealy automaton of intermediate growth.
• Implementing Computations in Automaton (Semi)groups
• Advanced Graph Theory and Combinatorics
• Finite state languages
• The entropies of topological Markov shifts and a related class of algebraic integers
• Combinatorial Complexity of Regular Languages
• Comparing Complexity Functions of a Language and Its Extendable Part
• Finding the Growth Rate of a Regular of Context-Free Language in Polynomial Time
• An Introduction to Symbolic Dynamics and Coding
• A Characterization of Those Automata That Structurally Generate Finite Groups
• THE FINITENESS PROBLEM FOR AUTOMATON SEMIGROUPS IS UNDECIDABLE
• Algorithmic Decidability of Engel’s Property for Automaton Groups

This page was built for publication: A New Hierarchy for Automaton Semigroups