Volume 21, 2002, No. 6

Refinement of the Alternating Space Hierarchy

Viliam GEFFERT, Norbert POPÉLY   Abstract We refine the alternating space hierarchy by separating the classes $\sga{k}\spa(s(n))$ and $\pia{k}\spa(s(n))$ from $\dea{k}\spa(s(n))$ as well as from $\dea{k+1}\spa(s(n))$, for each $s(n)\in\Omega(\llgn)\cap o(\lgn)$, and $k\geq 2$. We also present unary (tally) sets separating $\sga{2}\spa(s(n))$ and $\pia{2}\spa(s(n))$ from $\dea{2}\spa(s(n))$ as well as from $\dea{3}\spa(s(n))$.

 

Modelling Multi-Agent Systems as Synchronous Concurrent Constraint Processes

Luboš BRIM, Mojmír KRETINSKÝ, Jean-Marie JACQUET, David GILBERT   Abstract We present a language \scc\ for the specification of direct exchange and/or global sharing of information in multi-agent systems. \scc\ is based on concurrent constraint programming paradigm which we modify in such a way that agents can (i)~maintain its local private store, (ii)~share (read/write) the information in the global store and (iii)~communicate with other agents (via multi-party or hand-shake). To justify our proposal we compare \scc\ to a recently proposed language for the exchange of information in multi-agent systems. We also provide an operational semantics of \scc\ and prove its compositionality.

 

QoS-Competitive Video Buffering

Alexander KESSELMAN, Yishay MANSOUR   Abstract Many multimedia applications require transmission of streaming video from a server to a client across an internetwork. In many cases loss may be unavoidable due to congestion or heterogeneous nature of the network. We explore how discard policies can be used in order to maximize the quality of service (QoS) perceived by the client. In our model the QoS of a video stream is measured in terms of a cost function, which takes into account the discarded frames. In this paper we consider online policies for selective frame discard and analyze their performance by means of \textit{competitive analysis}. In competitive analysis the performance of a given online policy is compared with that of an optimal offline policy. In this work we present competitive policies for a wide range of cost functions, describing the QoS of a video stream.

 

Robust Multiple-View Geometry Estimation Based on GMM

Mingxing HU, Qiang XING, Baozong YUAN, Xiaofang TANG   Abstract Given three partially overlapping views of the scene from which a~set of point or line correspondences have been extracted, 3D structure and camera motion parameters can be represented by the trifocal tensor, which is the key to many problems of computer vision on three views. Unlike in conventional typical methods, the residual value is the only rule to eliminate outliers with large value, we build a Gaussian mixture model assuming that the residuals corresponding to the inliers come from Gaussian distributions different from that of the residuals of outliers. Then Bayesian rule of minimal risk is employed to classify all the correspondences using the parameters computed from GMM. Experiments with both synthetic data and real images show that our method is more robust and precise than other typical methods because it can efficiently detect and delete the bad corresponding points, which include both bad locations and false matches.

 

A Sharp Separation of Sublogarithmic Space Complexity Classes

Stanislav ŽÁK   Abstract We present very sharp separation results for Turing machine sublogarithmic space complexity classes which are of the form: For any, arbitrarily slow growing, recursive nondecreasing and unbounded function $s$ there is a~$k \in N$ and an unary language $L$ such that $L \in SPACE(s(n)+k) \setminus SPACE(s(n-1))$. For a binary~$L$ the supposition $\lim{s} = \infty$ is sufficient. The witness languages differ from each language from the lower classes on infinitely many words. We use so called demon (Turing) machines where the tape limit is given automatically without any construction. The results hold for deterministic and nondeterministic demon machines and also for alternating demon machines with a constant number of alternations, and with unlimited number of alternations. The sharpness of the results is ensured by using a very sensitive measure of space complexity of Turing computations which is defined as the amount of the tape required by the simulation (of the computation in question) on a fixed universal machine. As a proof tool we use a succint diagonalization method.

 

Volume 21, 2002, No. 6