Wyniki wyszukiwania - Biblioteka Nauki

1

Closure Properties of Multiset Language Families

100%

Kudlek M. , Mitrana V.

Fundamenta Informaticae

|

2002

|

tom Vol. 49, nr 1-3

191-203

EN

Multiset languages are languages defined by multiset grammars in the sense of [4]. We extend to multiset languages the usual operations defined for string languages and define new operations specific for multiset languages. The closure properties of the main classes of multiset languages are investigated. Along these lines we introduce two notions of abstract family of multiset languages.

2

Timed Cooperating Automata

80%

Lanotte R. , Maggiolo-Schettini A.

Fundamenta Informaticae

|

2000

|

tom Vol. 43, Nr 1-4

153-173

EN

We propose Timed Cooperating Automata (TC As), an extension of the model Cooperating Automata of Harel and Drusinsky, and we investigate some basic properties. In particular we consider variants of TCAs based on the presence or absence of internal activity, urgency and reactivity, and we compare the expressiveness of these variants with that of the classical model of Timed Automata (TAs) and its extensions with periodic clock constraints and with silent moves. We consider also closure and decidability properties of TCAs and start a study on succinctness of their variants with respect to that of TAs.

3

Blind Counter Automata on w-Words

80%

Fernau H. , Stiebe R.

Fundamenta Informaticae

|

2008

|

tom Vol. 83, nr 1-2

51-64

EN

This paper generalizes the concept of blind multicounter languages to infinite words. We introduce two different acceptance modes of blind multicounter machines on w-words, called synchrononous and asynchronous acceptance. These acceptance modes are compared with each other and with families of w-languages of the form L=[formula], where Ui, Vi are finitary blind multicounter languages.

4

Languages Accepted by Weighted Restarting Automata

70%

Wang Q.

Fundamenta Informaticae

|

2021

|

tom Vol. 180, nr 1-2

151--177

EN

Weighted restarting automata have been introduced to study quantitative aspects of computations of restarting automata. In earlier works we studied the classes of functions and relations that are computed by weighted restarting automata. Here we use them to define classes of formal languages by restricting the weight associated to a given input word through an additional requirement. In this way, weighted restarting automata can be used as language acceptors. First, we show that by using the notion of acceptance relative to the tropical semiring, we can avoid the use of auxiliary symbols. Furthermore, a certain type of word-weighted restarting automata turns out to be equivalent to non-forgetting restarting automata, and another class of languages accepted by word-weighted restarting automata is shown to be closed under the operation of intersection. This is the first result that shows that a class of languages defined in terms of a quite general class of restarting automata is closed under intersection. Finally, we prove that the restarting automata that are allowed to use auxiliary symbols in a rewrite step, and to keep on reading after performing a rewrite step can be simulated by regular-weighted restarting automata that cannot do this.

5

A Survey of Results on Stateless Multicounter Automata

60%

Ibarra O. H. , Egecioglu Ö.

Fundamenta Informaticae

|

2012

|

tom Vol. 116, nr 1-4

129-140

EN

A stateless multicountermachine hasm-counters operating on a one-way input delimited by left and right end markers. A move of the machine depends only on the symbol under the input head and the sign pattern of the counters. An input string is accepted if, when the input head is started on the left end marker with all counters zero, themachine eventually reaches the configurationwhere the input head is on the right end marker with all the counters again zero. We bring together a number of results on stateless multicounter automata of various different types: deterministic, nondeterministic, realtime (the input head moves right at every step), or non-realtime. We investigate realtime and non-realtime machines in both deterministic and nondeterministic cases with respect to the number of counters and reversals. In addition to hierarchy results, we also consider closure properties and the connections to stateless multihead automata.

6

Stochastic orders and ageing classes

60%

Miziuła P.

Mathematica Applicanda

|

2012

|

tom 40

|

nr 1

PL

Teoria niezawodnosci opisuje losowe czasy działania urzadzen podatnychna awarie. Na potrzeby tego typu badan opracowano specyficzne branzowepojecia, m.in. resztowy czas zycia, intensywnosc awarii, czy sredni resztowy czaszycia. Ich definicje zostały podane w Rozdziale 2. Znalazły sie w nim takze podstawowe definicje i fakty dotyczace systemów monotonicznych. Systemy monotoniczne tworza bardzo prosty i wygodny model, opisujacy działanie urzadzen składajacych sie z odpowiednio ułozonych wzgledem siebie czesci. Jest to dynamicznie rozwijajaca sie teoria, znajdujaca zastosowania w wielu dziedzinach nauki. Wiecej na ten temat mozna dowiedziec sie z ksiazek [2] i [13].Rozmaite porzadki stochastyczne, czyli porzadki na zbiorach rozkładów prawdopodobienstwa, maja zastosowanie w wielu dziedzinach rachunku prawdopodobienstwa i statystyki matematycznej. Wiele o porzadkach mozna nauczyć się z książki [14]. W Rozdziale 3 niniejszego artykułu zostały zdefiniowane i porównane ze soba tylko te porzadki, które najbardziej przydaja sie w pracy z klasami rozkładów czasu zycia. Nie powinno dziwic, ze takie kryterium wyboru spełniaja przede wszystkim porzadki, które prostota definicji i wszechstronnym zastosowaniem zasłuzyły sobie na miano klasycznych. Relacje miedzy wprowadzonymi porzadkami zostały podsumowane na Rysunku 1.W Rozdziale 4 opisane zostały wybrane klasy rozkładów czasu zycia – zarównote znane od kilkudziesieciu lat, jak i niektóre sposród wprowadzonych stosunkowoniedawno. Nacisk został połozony na dwa zagadnienia: relacje miedzy poszczególnymi klasami oraz domknietosci poszczególnych klas wzgledem najczesciej uzywanych operacji niezawodnosciowych: splotów, mieszanek i tworzenia systemów monotonicznych. Zostały tez wyróznione klasy domkniete ze wzgledu na maksima i minima. Wyniki zostały podsumowane na Rysunku 2 i w Tabeli 2.Wszystkim zainteresowanym zastosowaniem przedstawionych pojec na pewnoprzypadnie do gustu przystepnie i rzetelnie napisana ksiazka [10].

EN

This article covers knowledge of recently used stochastic orders, ageing classes, and relations between them. Definitions and relations between particular stochastic orders are presented there. The paper also contains definitions (especially using stochastic orders), relations and closure properties of ageing classes. Closure properties are investigated there under five useful reliability operations: convolutions, mixtures, formation of monotonic systems, maxima and minima.

7

New Language Operations in Formal Language Theory

51%

Meduna A. , Vítek M.

Schedae Informaticae

|

2004

|

tom Vol. 13

123-150

EN

Stringology represents a modern part of the formal language theory which deal with strings, languages and operations on them. It introduces many new languages operations, which can be divided into two groups - insertion and deletion operations. Some of these operations are described in [1] . This paper presents these operations and some of their properties. Especially, closure properties are studied here. New algorithms that construct finite automata accepting languages resulting from some of these operations are described here. We actually demonstrate by designing these algorithms, that the family of regular languages is closed under these operations.

8

Stochastic Orders and Ageing Classes

41%

Miziuła P.

Mathematica Applicanda

|

2012

|

tom Vol. 40, No. 1

105-125

EN

This article covers the knowledge of the recently used stochastic orders, ageing classes, and relations between them. Definitions and relations between particular stochastic orders are presented here. The paper also contains definitions (especially using stochastic orders), relations and closure properties of ageing classes. Closure properties are investigated here under five useful reliability operations: convolutions, mixtures, formation of monotonic systems, maxima, and minima.

PL

Teoria niezawodności opisuje losowe czasy działania urządzeń podatnych na awarie. Na potrzeby tego typu badań opracowano specyficzne branżowe pojęcia, m.in. resztowy czas życia, intensywność awarii, czy średni resztowy czas życia. Ich definicje zostały podane w Rozdziale 2. Znalazły się w nim także podstawowe definicje i fakty dotyczące systemów monotonicznych. Systemy monotoniczne tworzą bardzo prosty i wygodny model, opisujący działanie urzadzeń składających się z odpowiednio ułożonych względem siebie części. Jest to dynamicznie rozwijająca się teoria, znajdująca zastosowania w wielu dziedzinach nauki. Więcej na ten temat można dowiedzieć się z książek [2] i [13]. Rozmaite porządki stochastyczne, czyli porządki na zbiorach rozkładów prawdopodobieństwa, maja zastosowanie w wielu dziedzinach rachunku prawdopodobieństwa i statystyki matematycznej. Wiele o porządkach można nauczyć się z książki [14]. W Rozdziale 3 niniejszego artykułu zostały zdefiniowane i porównane ze sobą tylko te porządki, które najbardziej przydają się w pracy z klasami rozkładów czasu życia. Nie powinno dziwić, że takie kryterium wyboru spełniają przede wszystkim porządki, które prostota definicji i wszechstronnym zastosowaniem zasłużyły sobie na miano klasycznych. Relacje miedzy wprowadzonymi porządkami zostały podsumowane na Rysunku 1. W Rozdziale 4 opisane zostały wybrane klasy rozkładów czasu życia - zarówno te znane od kilkudziesięciu lat, jak i niektóre spośród wprowadzonych stosunkowo niedawno. Nacisk został położony na dwa zagadnienia: relacje miedzy poszczególnymi klasami oraz domkniętości poszczególnych klas względem najczęściej używanych operacji niezawodnościowych: splotów, mieszanek i tworzenia systemów monotonicznych. Zostały tez wyróżnione klasy domknięte ze względu na maksima i minima. Wyniki zostały podsumowane na Rysunku 2 i w Tabeli 2. Wszystkim zainteresowanym zastosowaniem przedstawionych pojęć na pewno przypadnie do gustu przystępnie i rzetelnie napisana książka [10].