Iterative arrays (IAs) are one-dimensional arrays of interconnected interacting finite automata with sequential input mode. We investigate IAs which work in real time and whose inter-cell communication is bounded by some constant number of bits not depending on the number of states. It is known that such IAs can recognize rather complicated unary languages with a minimum amount of communication, namely one-bit communication, in real time. Some examples are the languages {a~(2~n) ∣ n ≥ 1}, {a~(n~2)∣ n ≥ 1}, and {a~p ∣ p is prime}. Here, we consider non-unary languages and it turns out that the non-unary case is quite different. We present several real-time constructions for certain non-unary languages. For example, the languages {a~nb~n ∣ n ≥ 1}, {a~n(b~n)~m∣n, m≥1}, and {a~nba~mb(ba)~(n·m) ∣ n,m ≥ 1} are recognized in real time by 1-bit IAs. Moreover, it is shown that real-time 1-bit IAs can, in some sense, add and multiply integer numbers. Furthermore, closure properties and decidability questions of communication restricted IAs are investigated. Due to the constructions provided, non-closure results as well as undecidability results can be shown. It turns out that emptiness is still undecidable for 1-bit IAs despite their restricted communication. Thus, also the questions of finiteness, infiniteness, inclusion, and equivalence are undecidable.
展开▼
