Silent Transitions in Automata with Storage
The authors consider the problem of removing silent transitions from one-way automata with various kinds of storage. Specifically, they ask for which kinds of storage the real-time and the general version have equal computational power. They consider the computational power of silent transitions in one-way automata with storage. Specifically, they ask which storage mechanisms admit a transformation of a given automaton into one that accepts the same language and reads at least one input symbol in each step. They study this question using the model of valence automata. Here, a finite automaton is equipped with a storage mechanism that is given by a monoid.
Subscribe to the Data Insider Newsletter
Learn the latest news and best practices about data science, big data analytics, artificial intelligence, data security, and more. Delivered Mondays and Thursdays