Search

We introduce a new generalization of weighted automata – automata with auxiliary weights. They allow to compute several quantities not directly computable over semirings by generalizing both semiring addition and semiring multiplication. Moreover, our automata retain key properties of ordinary weighted automata. We prove that automata over multi-hemirings of Droste and Kuich [7] can be modelled using our framework, and that automata with auxiliary weights can be used to describe several additional settings. Finally, we introduce rational expressions with auxiliary weights and prove that they are equivalent to our automata.

This paper continues the investigation of the concept of synchronized alternation. The open problems from Ref. 4 are solved by showing that one-way synchronized alternating (multihead) automata are as powerful as two-way ones. More precisely it is shown that: (i) one-way synchronized alternating finite automata recognize exactly context-sensitive languages, and (ii) NSPACE(nk) is exactly the family of languages recognized by one-way (two-way) synchronized alternating k-head finite automata, for k≥1. Finaly, the synchronization complexity of one-way synchronized Turing machines (1satm's) is investigated and an infinite hierarchy among classes of sets accepted by 1satm's with space and synchronization bounds between log log n and log n is established. Some closure properties of the classes in this hierarchy are also proved.