Iterative arrays with a wee bit alternation
Loading...
Date
Advisors/Reviewers
Further Contributors
Contributing Institutions
Publisher
Journal Title
Journal ISSN
Volume Title
Publisher
License
Quotable link
Abstract
An iterative array is a line of interconnected interacting finite automata. One distinguished automaton, the communication cell, is connected to the outside world and fetches the input serially symbol by symbol. We are investigating iterative arrays with an alternating communication cell. All the other automata are deterministic. The number of alternating state transitions is regarded as a limited resource which depends on the length of the input. We center our attention to realtime computations and compare alternating IAs with nondeterministic IAs. By proving that the language families of the latter are not closed under complement for sublogarithmic limits it is shown that alternation is strictly more powerful than nondeterminism. Moreover, for these limits there exist infinite hierarchies of properly included alternating language families. It is shown that these families are closed under boolean operations.Link to publications or other datasets
Description
Notes
Original publication in
Original publication in
Anthology
Collections
URI of original publication
Forschungsdaten
Series
IFIG Research Report; 9905 / 1999