Iterative arrays with small time bounds

An iterative arrays 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. Sometimes in the literature this model is referred to as cellular automaton with sequential input mode. We investigate deterministic iterative arrays (IA) with small time bounds between real-time and linear-time. It is shown that there exists an infinite dense hierarchy of strictly included complexity classes in that range. The result closes the last gap in the time hierarchy of IAs.

Iterative arrays with small time bounds

Files

Date

Authors

Advisors/Reviewers

Further Contributors

Contributing Institutions

Publisher

Journal Title

Journal ISSN

Volume Title

Publisher

License

Quotable link

Abstract

Link to publications or other datasets

Description

Notes

Original publication in

Original publication in

Anthology

Collections

URI of original publication

Forschungsdaten

Series

Citation