Wyniki wyszukiwania - Biblioteka Nauki

1

Social Networks with Competing Products

100%

Apt K. R. , Markakis E.

Fundamenta Informaticae

|

2014

|

tom Vol. 129, nr 3

225--250

EN

We introduce a new threshold model of social networks, in which the nodes influenced by their neighbours can adopt one out of several alternatives. We characterize social networks for which adoption of a product by the whole network is possible (respectively necessary) and the ones for which a unique outcome is guaranteed. These characterizations directly yield polynomial time algorithms that allow us to determine whether a given social network satisfies one of the above properties. We also study algorithmic questions for networks without unique outcomes. We show that the problem of determining whether a final network exists in which all nodes adopted some product is NP-complete. In turn, we also resolve the complexity of the problems of determining whether a given node adopts some (respectively, a given) product in some (respectively, all) network(s). Further, we show that the problem of computing the minimum possible spread of a product is NPhard to approximate with an approximation ratio better than W(n), in contrast to the maximum spread, which is efficiently computable. Finally, we clarify that some of the above problems can be solved in polynomial time when there are only two products.

2

UPSILON: Universal Programming System with Incomplete Lazy Object Notation

88%

Postow B. , Regan K. , Smith C. H.

|

2002

|

tom Vol. 50, nr 3,4

325-359

EN

This paper presents a new model of computation that differs from prior models in that it emphasizes data over flow control, has no named variables and has an object-oriented flavor. We prove that this model is a complete and confluent acceptable programming system and has a usable type theory. A new data synchronization primitive is introduced in order to achieve the above properties. Subtle variations of the model are shown to fall short of having all these necessary properties.

3

Limits of Modularity

75%

Bednarczyk M. A.

|

2006

|

tom Vol. 74, nr 2,3

167-187

EN

It has been observed that various synchronisation operators underlying the modular design of concurrent systems can be explained as pullbacks in suitable categories of concurrent systems. Here, the boundaries of such approach are investigated. For this purpose we study the issue of completeness in categories of trace monoids. It turns out that (finite) completeness is achieved if trace monoids with concurrency preserving homomorphisms are considered. Taking arbitrary monoid homomorphisms leads, in general, to incompleteness. The results obtained are used to reveal an area in which the code problem for trace monoids, undecidable in general, has always a positive answer.

4

Generowanie maszyn Turinga poprzez zastosowanie nowych modeli obliczeniowych

75%

Dubiel L.

Computer Science

|

2003

|

tom Vol. 5

7-25

PL

Dla każdego problemu obliczalnego istnieje algorytm jego rozwiązania, który może być przedstawiony w postaci konkretnej maszyny Turinga. Ze względu na prostotę tej maszyny programy są bardzo skomplikowane i nieprzejrzyste. Dlatego tworzy się inne modele obliczenia, na których można szybko i łatwo zapisywać algorytmy związane z danym typem problemu, a następnie symuluje się działanie tych modeli na maszynie Turinga. Niniejszy artykuł przedstawia metodologię znajdowania modelu obliczeniowego pasującego do danego typu problemów i przekształcenie go w odpowiednią maszynę Turinga na przykładzie obliczeń na liczbach naturalnych.

EN

For each problem that can be solved there exists algorithm, which can be described with a program of Turing machine. Because this is very simple model programs tend to be very complicated and hard to analyse by human. The best practice to solve given type of problems is to define a new model of computation that allows for quick and easy programming, and then to emulate its operation with Turing machine. This article shows how to define most suitable model for computation on natural numbers and defines Turing machine that emulates its operation.

5

Limits of Modularity

51%

Bednarczyk M.

|

tom Nr 989

1-21

EN

It has been observed that various synchronisation operators that underly modular design of concurrent systems can be explained as {\em pullbacks in suitable categories of concurrent systems. Here, the boundaries of such approach are investigated. For this purpose we study the issue of completeness in categories of trace monoids. It turns out that (finite) completeness is achieved if trace monoids with concurrency preserving homomorphisms are considered. Taking arbitrary monoid homomorphisms leads, in general, to incompleteness. In terms of code problem for trace monoids.

PL

Wcześnie zauważono, że modularne techniki konstruowania systemów współbieżnych oparte o mechanizmy synchronizacji można opisać jako (zmodyfikowane) produkty lub wręcz jako produkty włókniste w stosownych kategoriach systemów współbieżnych. Celem niniejszej pracy jest wyznaczenie granic stosowalności tego teorio-kategoryjnego podejścia. W tym celu w pracy rozważa się problem (skończonej) zupełności kategorii monoidów śladów Mazurkiewicza dla różnych klas morfizmów formalizującej pojęcie symulacji systemów. Okazuje się, że skończoną zupełność gwarantuje przyjęcie, iż obiektem badań są reprezentacje monoidów śladów postaci alfabet i relacja niezależności, zaś morfizmy to funkcje z alfabetu do monoidu śladów zachowujące niezależność. Z kolei akceptacja dowolnych homomorfizmów, niekoniecznie zachowujących niezależność, prowadzi na ogół do braku zupełności kategorii. Osiągnięte wyniki rozszerzają też obszar, w którym problem kodu dla monoidów śladów jest rozstrzygalny w sposób pozytywny.