Search
Search results for: DETERMINISTYCZNE AUTOMATY DRZEWIASTE
-
Perfect hashing with pseudo-minimal bottom-up deterministic tree automata
PublicationWe describe a technique that maps unranked trees to their hash codes using a bottom-up deterministic tree automaton (DTA). In contrast to techniques implemented with minimal tree automata, our procedure builds a pseudo-minimal DTA. Pseudo-minimal automata are larger than the minimal ones but in turn the mapping can be arbitrary, so it can be determined prior to the automaton construction. We also provide procedures to build incrementally...
-
Języki formalne, automaty i translatory
PublicationKsiążka stara się w przystępny sposób przedstawić zagadnienia związane z teorią języków formalnych, automatów i translatorów. Wiedza ta pomoże nie tylko zrozumieć zasady stosowanych na co dzień narzędzi informatycznych, ale pomoże również w rozwiązywaniu częstych problemów związanych z przetwarzaniem danych tekstowych o zdefiniowanej strukturze.Książka ta przeznaczona jest przede wszystkim dla szerokiego grona studentów informatyki...
-
Automaty jako narzędzia w przetwarzaniu języka
PublicationRozdział zawiera definicję, notację i chcarakterystykę automatów oraz algorytmy ich przekształcania, umożliwiające ich skuteczne wykorzystanie w przetwarzaniu języka.
-
Les transducteurs à sorties variables
PublicationW przetwarzaniu języka naturalnego słowniki elektroniczne wiążą ze słowami informacje. Najwydajniejsza reprezentacja takich słowników używa maszyn ze skończoną liczbą stanów (automatów prostych lub automatów Mealy'ego). W tym artykule wzorując się na algorytmach bezpośredniej budowy minimalnego automatu deterministycznego proponujemy nowy typ automatu Mealy'ego. Ta nowa forma pozwala na szybkie obliczanie informacji wyjściowej...
-
Śmiech w ogrodzie, czyli o tym jak automaty rozśmieszały ogrodowych gości
PublicationArtykuł przywołuje historię automatów hydraulicznych umieszczanych w ogrodach w celu rozśmieszania gości. Przeprowadza czytelnika poprzez zawiłości związane z ich budową i analizuje reakcje jakie wywoływały u bywalców ogrodów od Starożytności poprzez Średniowiecze i Renesans aż do XVIII wieku.
-
Incremental construction of Minimal Tree Automata [online]
PublicationWe describe an algorithm that allows the incremental addition or removal of unranked ordered trees to minimal frontier-to-root deterministic tree automaton (DTA). The algorithm takes a tree t and a minimal DTA A as input; it outputs a minimal DTA A' which accepts the language L(A) accepted by A incremented (or decremented) with the tree t. The algorithm can be used to efficiently maintain dictionaries which store large collections...
-
Incremental and Semi-Incremental Construction of Pseudo-Minimal Automata
PublicationPrzedstawione zostają modyfikacje trzech algorytmów przyrostowego i półprzyrostowego tworzenia automatów minimalnych w taki sposób, aby tworzyły automaty pseudominimalne. Istniejący od dawna algorytm Revuza tworzy takie automaty szybciej i zużywając mniej pamięci, ale wymaga kłopotliwego sortowania. Nie nadaje się też do dodawania nowych słów do automatu - ważnej czynności w realizacji dynamicznej doskonałej funkcji mieszającej....
-
Semi- incremental construction of minimal cyclic finite state automata usingcontinuation classes.
PublicationMinimalne automaty skończone są często wybierane do przedstawiania słowników morfologicznych języka naturalnego. Wśród ich zalet znajdują się duża szybkość rozpoznawania i małe wymagania pamięciowe. Tłumaczenie opisów morfologicznych opartych o klasy kontynuacji na minimalne, cykliczne automaty skończone jest tradycyjnie dokonywane w kilku fazach, zawierających tworzenie automatu niedeterministycznego z przejściami etykietowanymi...
-
An implementation of deterministic tree automata minimization
PublicationWstępujący, deterministyczny, skończony automat drzewiasty (DTA) może być używany jako struktura danych do przechowywania zbiorów nieuporządkowanych drzew bez narzuconej liczby poddrzew. Takie automaty są zwykle rzadsze niż automaty działające na napisach i dlatego należy zwrócić szczególną uwagę na ich wydajną minimalizację. W dostępnej literaturze jest jednak ciężko znaleźć proste i szczegółowe opisy procedury minimalizacji....
-
Incremental and pseudo-incremental construction of pseudo-minimal automata.
PublicationAutomaty pseudominimalne mają dla każdego słowa w języku automatu co najmniej jeden element własny (stan lub przejście), który nie jest współdzielony z żadnym innym słowem. Przedstawiamy przyrostowe i półprzyrostowe algorytmy tworzenia takich automatów.
-
Dynamics of surface floating objects
PublicationPrezentowana praca stanowi wstępne rozeznanie w dziedzinie badań dynamiki konstrukcji pływających z zastosowaniem teorii procesu dyfuzji. W pracy rozpatrywane są modele fizyczne jednostek wielokadłubowych oraz modele matematyczne. Spośród modeli jednostek wielokadłubowych wyróżnia się modele deterministyczne oraz modele stochastyczne.
-
Recent developments in automatic classification of musical instruments. W:[CD-ROM] Collected papers. First Pan-American/Iberian Meeting on Acoustics. 144 Meeting of the Acoustical Society of America. III Iberoamerican Cong- ress of Acoustics. 9o Mexican Congress of Acoustics. Cancun, Q. R. Mxico, 2-6 Dec. 2002. [B.m.:ASA]**2002 paper 2aMU4, 7 s. 6 rys. 1 tab. bibliogr. 21 poz. Automatyczne rozpoznawanie muzyki - przykłady eksperymentów.
PublicationW referacie dokonano przeglądu aktualnego stanu badań w dziedzinie automaty-cznego rozpoznawania muzyki. Przedstawiono też eksperymenty prowadzone aktu-alnie w Katedrze Dźwięku i Obrazu PG. Prace te dotyczyły rozpoznawania klasinstrumentów muzycznych i separacji duetów muzycznych. Pokazano przykładowewyniki i przedstawiono projekt prac do zrealizowania w przyszłych ekspery-mentach.
-
Overview of problems in mathematics related analysis of capital markets
PublicationCelem pracy jest przegląd zjawisk i problemów w analizie rynków kapitałowych metodami matematyki. Zdefiniowano główny cel analiz rynkowych. Przedstawiono stosowane podejście w analizie rynków. Przedyskutowano podejście stochastyczne i deterministyczne. Kolejno przedstawiono zjawiska sprężeń zwrotnych w rynkach. Na koniec przedstawiono, specyficzne dla rynków zjawiska, które mają duży wpływ na zniekształcenie wyników analizy.
-
Podzielne szeregowanie zadań dwuprocesorowych na maszynach dedykowanych w celu minimalizacji sumy czasów zakończenia
PublicationW pracy rozważamy deterministyczne szeregowanie zadań dwuprocesorowych na maszynach dedykowanych, które minimalizuje sumę czasów zakończenia, przy czym dopuszcza się możliwość przerwania wykonywania zadania i ponownego wznowienia obsługi z pomijalnie małym kosztem. Wiadomo, że tak postawione zagadnienie jest problemem silnie NP-trudnym. W pracy badamy złożoność obliczeniową problemu, ograniczając liczbę maszyn.
-
Finite-state lexical tools
PublicationArtykuł przedstawia trzy pakiety oprogramowania zawierające narzędzia poziomu leksykalnego wykorzystujące automaty skończone: dwa zbiory samodzielnych programów i skryptów pomocniczych - jeden używający prostych automatów skończonych, drugi używający automatów Mealy`ego oraz bibliotekę funkcji. Wszystkie przedstawione pakiety posiadają podobne funkcje. Zamiast opisywać poszczególne pakiety, opis skupiony jest na dostarczanych przez...
-
Mechatronics in the design of three wheeled mobile platform controlled by surveillance system at energy performance index
PublicationPraca jest poświęcona projektowaniu mechatronicznemu trójkołowej platformy mobilnej, sterowanej systemem nadzorowania bazującym na energetycznym wskaźniku jakości. Zdefiniowany zakres badań i silna nieliniowość obiektu wymagały niezawodnego systemu sterowania. Warunki deterministyczne i zastosowany algorytm wpłynęły na wybór metody opracowania systemu. Przedstawione techniki projektowania mechatronicznego i przeprowadzone warianty...
-
Finite automata for compact representation of language models in NLP
PublicationPrzedstawiona zostaje technika reprezentacji modeli języka w przetwarzaniu języka naturalnego wymagająca mało pamięci. Po krótkim omówieniu przyczyn poszukiwania oszczędnej reprezentacji takich modeli języka, pokazane jest, jak automaty skończone mogą być użyte w tym celu. Technika może być postrzegana jako zastosowanie i rozszerzenie doskonałej funkcji mieszającej z wykorzystaniem automatów skończonych. Pierwsze doświadczenia...
-
The reliability of ring, star and hybrid networks
PublicationJednym z parametrów charakteryzującym jakość sieci jest jej niezawodność. Rozważono sieci o topologiach drzewiastych, gwiaździstych, pętlowych, wielo-pętlowych oraz mieszanych. Przyjęto następujący model uszkodzeń. Węzły oraz kanały sieci ulegają uszkodzeniom z określonym prawdopodobieństwem, uszkodzenia elementów sieci są od siebie statystycznie niezależne. Jako oceny niezawodności sieci przyjęto: średnią liczbę sprawnych par...
-
Capturing semantics of semi-structured data using partial-order trees
PublicationW artykule zaprezentowano nowe podejście do problemu klasyfikacji danych semistrukturalnych. Kryteria klasyfikacji bazują na strukturze danych (zwanej typem danych) oraz na ich usytuowaniu w grafir danych (zwanym rolą danych). Zastosowano model OEM (Object Exchange Model) do reprezentacji nazy danych semistrukturalnych. Bazując na tej reprezentacji, definiuje się typy i role obiektów semistrukturalnych i organizuje się je w struktury...
-
Gazetteer compression technique based on substructure recognition
PublicationAutomaty skończone są najlepszą formą reprezentacji słowników do przetwarzania języka naturalnego. Przedstawiamy nową technikę kompresji, która jest szczególnie użyteczna w stosunku do pewnego rodzaju słowników. Zastępujemy wielokrotnie występujące podstruktury ich niepowtarzalnymi reprezentantami. Do ich znalezienia traktujemy wektor przejść jako tekst i stosujemy technikę kompresji tekstu w stylu Ziv-Lempel, która znajduje powtórzenia...