Then, the execution proceeds in an infinite sequence of synchronous rounds, where each node determines its next state as a function of its own current state and the current state of its incoming neighbor (i.e., the node to its left). To run a distributed automaton on such a path, we first place a copy of the automaton on each node and initialize it to a state that may depend on the node’s label. For our purposes, they also act as language recognizers, but their input word is given in form of a directed path graph whose nodes are labeled with the symbols of the word (such that the first symbol is on the source node).
On the other hand, we look at distributed automata, which are devices that can use a lot of time. Both of these conditions entail that counter values can grow only linearly with the input length, and, as we will see, they yield in fact the same expressive power.
#Copyless 2 update#
(Every update consumes an input symbol, i.e., there are no epsilon transitions.) Our main concern are two special cases of this model: sumless counter machines, which can increment, decrement and copy counter values but not sum them up, and copyless counter machines, which can compute arbitrary sums but not use the same counter more than once per update step. Whenever it processes a symbol of the input word, it can deterministically change its internal state and simultaneously update each counter to a new value that is expressed as the sum of values of several counters and a constant \(c\). The machine has read access to those values up to some fixed threshold. However, in addition to having a finite-state memory, such a machine also has a fixed number of counters, which can store arbitrarily large integer values (and are initially set to zero). Just like classical finite automata, they take a finite word as input, read it once from left to right, and then decide whether or not to accept that word. In the way we define them here, these devices act as language recognizers. On the one hand, we look at counter machines, which can use a lot of space. In this paper, we consider two types of devices whose usages of space and time turn out to be dual to each other. Typically, the more of these resources a computing device has at its disposal, the harder the problems it can solve. Space and time are the two standard resources for solving computational problems.
0 kommentar(er)
