Searching for just a few words should be enough to get started. If you need to make more complex queries, use the tips below to guide you.
Issue title: Special Issue on Machines, Computations and Universality (MCU 2018)
Guest editors: Jérôme Durand-Lose, Jarkko Kari and Sergey Verlan
Article type: Research Article
Authors: Geffert, Viliam; *; † | Bednárová, Zuzana; *
Affiliations: Department of Computer Science, P. J. Šafárik University, Jesenná 5, 04154 Košice, Slovakia. viliam.geffert@upjs.sk, zuzana.bednarova@upjs.sk
Correspondence: [†] Address for correspondence: Department of Computer Science, P. J. Šafárik University, Jesenná 5, 04154 Košice, Slovakia
Note: [*] Supported by the Slovak Grant Agency for Science (VEGA) under contract 1/0177/21 “Descriptional and Computational Complexity of Automata and Algorithms” and by the Slovak Research and Development Agency under contract APVV-15-0091 “Efficient Algorithms, Automata, and Data Structures”.
Abstract: We show that, for automata using a finite number of counters, the minimal space that is required for accepting a nonregular language is (log n)ɛ. This is required for weak space bounds on the size of their counters, for real-time and one-way, and for nondeterministic and alternating versions of these automata. The same holds for two-way automata, independent of whether they work with strong or weak space bounds, and of whether they are deterministic, nondeterministic, or alternating. (Here ɛ denotes an arbitrarily small—but fixed—constant; the “space” refers to the values stored in the counters, rather than to the lengths of their binary representation.) On the other hand, we show that the minimal space required for accepting a nonregular language is nɛ for multicounter automata with strong space bounds, both for real-time and one-way versions, independent of whether they are deterministic, nondeterministic, or alternating, and also for real-time and one-way deterministic multicounter automata with weak space bounds. All these bounds are optimal both for unary and general nonregular languages. However, for automata equipped with only one counter, it was known that one-way nondeterministic automata cannot recognize any unary nonregular languages at all, even if the size of the counter is not restricted, while, with weak space bound log n, we present a real-time nondeterministic automaton recognizing a binary nonregular language here.
Keywords: space complexity, pushdown automata, counter automata, real-time automata
DOI: 10.3233/FI-2021-2053
Journal: Fundamenta Informaticae, vol. 181, no. 2-3, pp. 99-127, 2021
IOS Press, Inc.
6751 Tepper Drive
Clifton, VA 20124
USA
Tel: +1 703 830 6300
Fax: +1 703 830 2300
sales@iospress.com
For editorial issues, like the status of your submitted paper or proposals, write to editorial@iospress.nl
IOS Press
Nieuwe Hemweg 6B
1013 BG Amsterdam
The Netherlands
Tel: +31 20 688 3355
Fax: +31 20 687 0091
info@iospress.nl
For editorial issues, permissions, book requests, submissions and proceedings, contact the Amsterdam office info@iospress.nl
Inspirees International (China Office)
Ciyunsi Beili 207(CapitaLand), Bld 1, 7-901
100025, Beijing
China
Free service line: 400 661 8717
Fax: +86 10 8446 7947
china@iospress.cn
For editorial issues, like the status of your submitted paper or proposals, write to editorial@iospress.nl
如果您在出版方面需要帮助或有任何建, 件至: editorial@iospress.nl