Wyniki wyszukiwania - BazTech

1

A Communication Approach to the Superposition Problem

Ablayev F., Ablayeva S.

Fundamenta Informaticae

|

2010

|

Vol. 104, nr 3

185-200

EN

In function theory the superposition problem is known as the problem of representing a continuous function f(x1, . . . , xk) in k variables as the composition of "simpler”"functions. This problem stems from the Hilbert’s thirteenth problem. In computer science good formalization for the notion of composition of functions is formula. In the paper we consider real-valued continuous functions in k variables in the cube [0, 1]k from the class [...] with ω_p a special modulus of continuity (measure the smoothness of a function) defined in the paper. [...] is a superset of Hölder class of functions. We present an explicit function [...] which is hard in the sense that it cannot be represented in the following way as a formula: zero level (input) gates associated with variables {x1, . . . , xk} (different input gates can be associated with the same variable xi . {x1, . . . , xk}), on the first level of the formula, arbitrary number s ≥1 of t variable functions from [...] for t < k are allowed, while the second (output) level may compute any s variable H¨older function. We apply communication complexity for constructing such hard explicit function. Notice that one can show the existence of such function using the "non constructive" proof method known in function theory as Kolmogorov's entropy method.

2

Survivability issues in IP-MPLS networks

Molisz W.

Systems Science

|

2005

|

Vol. 31, no 4

87-107

EN

A model for survivability assessment of IP-MPLS networks implemented directly in optical transport networks OTN (WDM) is described under assumptions as follows: end-to-end path protection; preplanned node-disjoint, dedicated or shared, backup path for each working path: distributed control of all top-down restoration actions: LSP-to-lightpath mapping minimizing the number of wavelengths converters. Survivability of such networks has a fundamental importance, since a single link cut can affect extremely large traffic volumes. The optimization problem ofsurvivable routing and wavelength assignment (SRWA) can be decomposed into a survivable routing followed by a wavelength assignment optimization problem. They are stated as the mixed integer and integer programming problems, respectively. Unfortunately, they both are NP-complete. Heuristic algorithms are proposed to solve the problems. The presented approach has been verified by means of simulation. Some results of the large number of simulation experiments investigating networks: DARPA. and NSF are described and discussed. Conclusions help in better understanding of survivability issues in IP-MPLS networks. All results are the original contribution and are published for the first time.

3

Communication complexity for multi-speed cooperating automata

Jurdziński T., Kutyłowski M., Rzechonek P., Zatopiański J.

Prace Naukowe Instytutu Matematyki Politechniki Wrocławskiej. Konferencje

|

2001

|

Vol. 24, nr 3

17-30

EN

We consider bounded memory asynchronous systems. They consist of finite automata working independently and communicating by exchanging messages. We discuss what impact the differences in timing models on computational power of such systems have. It is known that a total lack of synchronization has profound consequences for computational power of systems of automata. Lower bounds found for this model indicate that the only way to perform a nontrivial computation would be to re-synchronize the automata every 0(1) steps. We examine much weaker form of asynchronism. We consider the model in which automata work with constant speeds, but the speed might be different for each automaton, and the automata have no knowledge about the speeds. (We call this model multi-speed systems of finite automata.) In particular, it may happen that some speed cannot be expressed exactly by the means of internal states of automata. Nevertheless, we expect the automata to compute the correct output. The main result of this paper is that, quite unexpectedly, the systems described might be as powerful as synchronous systems, where all automata work with the same speed. More precisely, some languages, which have been candidates for distinguishing multi-speed and synchronous models, can be recognized by multi-speed systems with approximately the same number of messages sent.