Wyniki wyszukiwania - BazTech

1

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.

2

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.

3

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.