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.

In this paper, we continue the research on formal treatment of attributes of information, based on the computational approach. In this scenario, the usefulness of advisory information is measured by the decrease in complexity of a problem we need to solve. We propose to model the time criticality via usefulness of a piece of information which is received during the computation. As a modeling tool, we use deterministic finite automata. We give two definitions of time criticality. In the static case, we consider supplementary information which concerns the entire input instance. In the dynamic case, we consider information about the unprocessed part of the input. Despite the simplicity of our model, we shall see that the development of time criticality may exhibit an interesting behavior.

The study of synchronized alternating machines has enabled to characterize several natural complexity classes. It is known that synchronized alternating space SASPACE(S(n))= ∪c>0NSPACE(ncS(n)) for any (space-constructible) function S(n) [Hromkovicˇet al. (1991)]. In particular, context-sensitive languages are characterized by two-way synchronized alternating finite automata. Furthermore, PSPACE is characterized by synchronized alternating multihead finite automata and NLOG by synchronized alternating two-way finite automata with parallelism bounded by a constant. In the present paper we prove analogous characterizations for deterministic space classes using a restricted form of synchronization — globally deterministic synchronization. This enables to study the well-known open problems concerning nondeterminism versus determinism as problems about synchronization. We also show that globally deterministic synchronization is strictly more powerful than deterministic synchronization.

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.

A study of assisted problem solving formalized via decompositions of deterministic finite automata is initiated. The landscape of new types of decompositions of finite automata this study uncovered is presented. Languages with various degrees of decomposability between undecomposable and perfectly decomposable are shown to exist.

The paper investigates a version of the resource allocation problem arising in the wireless networking, namely in the OVSF code reallocation process. In this setting a complete binary tree of a given height n is considered, together with a sequence of requests which have to be served in an online manner. The requests are of two types: an insertion request requires to allocate a complete subtree of a given height, and a deletion request frees a given allocated subtree. In order to serve an insertion request it might be necessary to move some already allocated subtrees to other locations in order to free a large enough subtree. We are interested in the worst case average number of such reallocations needed to serve a request. In [4] the authors delivered bounds on the competitive ratio of online algorithm solving this problem, and showed that the ratio is between 1.5 and O(n). We partially answer their question about the exact value by giving an O(1)-competitive online algorithm. In [3], authors use the same model in the context of memory management systems, and analyze the number of reallocations needed to serve a request in the worst case. In this setting, our result is a corresponding amortized analysis.

We shall showthat simple communication can be substituted by parallel rewriting and nondeterminism without a time penalty. This is no longer true for more complex communication. In particular, we shall show that time preserving simulation of regular PCGS by g-systems is possible whereas time preserving simulation of context-free PCGS is impossible.

In this note, we reconsider the results in Rovan and Steskal (2007, Vol. 4497 of Lecture Notes in Computer Science, pp. 660–669, Springer) concerning TMDC (Display Turing Machines with Control) with Chomsky like control language. We shall show that, under the given assumptions, various degrees of the control complexity do not give rise to a hierarchy of language families, thus correcting an error in Rovan and Steskal (2007, Vol. 4497 of Lecture Notes in Computer Science, pp. 660–669, Springer).

Interval routing is an attractive space-efficient routing method for point-to-point networks (introduced in [13] and [15]) which has found industrial applications in the INMOS T9000 transputer design. Surveys of the principal theoretical results as well as recent trends in the area of interval routing can be found in [16, 5, 11].

We present deadlock-free packet (wormhole) routing algorithms based on multi-dimensional interval schemes for certain multiprocessor interconnection networks and give their analysis in terms of the compactness and the size (the maximum number of buffers per node (per link)). The issue of a simultaneous reduction of the compactness and the size is fundamental, worth to investigate and of practical importance, as interval routing and wormhole routing have been realized in INMOS Transputer C104 Router chips.