Continuing the study of connections between classical and P automata variants, we show that dP automata, i.e., distributed systems of P automata, where the input multiset is mapped to the set of strings consisting of all permutations of its elements, are as powerful as the class of distributed systems of special counter machine acceptors. These variants of counter machines read multisets (represented as sets of all permutations of their elements) and manipulate counters in a conventional manner.
展开▼
