Wyniki wyszukiwania - BazTech

1

Social Networks with Competing Products

Apt K.R., Markakis E.

Fundamenta Informaticae

|

2014

|

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

A minimization algorithm of 1-way quantum finite automata

Siedlecka-Lamch O.

Metody Informatyki Stosowanej

|

2010

|

nr 4 (24)

73-79

EN

A minimization of finite automata is important for designing of computer's hardware and software. A finite automata can be a model of any system with finite number of states. A limitation of number of states will save resources and time. In this article 1-way quantum finite automata is presented. We describe its characteristics, behaviour and languages accepted by it. This type of automata can be in future exploited to design and checking the behaviour of quantum systems, in lexical anaiyzer of a compiler, that will be used on quantum computers, or in verification systems. Also in this case Iimitation of states will save resources. The article holds formulated definition of indistinguishableness relation for 1-way quantum finite automata, on base of which minimization algorithm was created. Additionally, the algorithm 's complexity analysis and example of behaviour is holded.

3

Limits of Modularity

Bednarczyk M.

Prace Instytutu Podstaw Informatyki Polskiej Akademii Nauk

|

2006

|

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.

4

Limits of Modularity

Bednarczyk M.A.

Fundamenta Informaticae

|

2006

|

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.

5

Real Recursive Functions and Baire Classes

Mycka J.

Fundamenta Informaticae

|

2005

|

Vol. 65, nr 3

263--278

EN

Recursive functions over the reals [6] have been considered, first as a model of analog computation, and second to obtain analog characterizations of classical computational complexity classes [2]. However, one of the operators introduced in the seminal paper by Cris Moore (in 1996), the minimalization operator, creates some difficulties: (a) although differential recursion (the analog counterpart of classical recurrence) is, to some extent, directly implementable in the General Purpose Analog Computer of Claude Shannon, analog minimalization is far from physical realizability, and (b) analog minimalization was borrowed from classical recursion theory and does not fit well the analytic realm of analog computation. In this paper we use the most natural operator captured from Analysis - the operator of taking a limit - instead of the minimalization with respect to the equivalance of these operators given in [8]. In this context the natural question about coincidence between real recursive functions and Baire classes arises. To solve this problem the limit hierarchy of real recursive funcions is introduced. Relations between Baire classes, effective Baire classes and the limit hierachy are also studied.

6

Generowanie maszyn Turinga poprzez zastosowanie nowych modeli obliczeniowych

Dubiel L.

Computer Science

|

2003

|

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.

7

UPSILON: Universal Programming System with Incomplete Lazy Object Notation

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

Fundamenta Informaticae

|

2002

|

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.