Conference paper

Publication year: 2016

Pages: 187-214

Journal: International Journal of Foundations of Computer Science

Volume number: 27

Issue number: 2

ISSN: 0129-0541

eISSN: 1793-6373

DOI Link: https://doi.org/10.1142/S0129054116400062

Conference: 18th International Conference on Developments in Language Theory (DLT)

Publisher: World Scientific Publishing

Abstract: 
We cunsider the model of deterministic set automata which are basically deterministic finite automata equipped with a set as an additional storage medium. The basic operations on the set are the insertion of elements, the removing of elements, and the test whether an element is in the set. We investigate the computational power of deterministic set automata and compare the language class accepted with the context-free languages and classes of languages accepted by queue automata. As result the incomparability to all classes considered is obtained. Furthermore, we examine the closure properties under several operations. Then we show that deterministic set automata may be an interesting model from a practical point of view by proving that their regularity problem as well as the problems of emptiness, finiteness, infiniteness, and universality are decidable. Finally, the descriptional complexity of deterministic and nondeterministic set automata is investigated. A conversion procedure that turns a deterministic set automaton accepting a regular language into a deterministic finite automaton is developed which leads to a double exponential upper bound. This bound is proved to be tight in the order of magnitude by presenting also a double exponential lower bound. In contrast to these recursive bounds we obtain non-recursive trade-offs when nondeterministic set automata are considered.

Harvard Citation style: Kutrib, M., Malcher, A. and Wendlandt, M. (2016) Set Automata, International Journal of Foundations of Computer Science, 27(2), pp. 187-214. https://doi.org/10.1142/S0129054116400062

APA Citation style: Kutrib, M., Malcher, A., & Wendlandt, M. (2016). Set Automata. International Journal of Foundations of Computer Science. 27(2), 187-214. https://doi.org/10.1142/S0129054116400062