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

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

Resource Details

Provided by:
Cornell University
Topic:
Storage
Format:
PDF