Wyniki wyszukiwania - BazTech

1

Languages Accepted by Weighted Restarting Automata

Wang Qichao

Fundamenta Informaticae

|

2021

|

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.

2

Stochastic Orders and Ageing Classes

Miziuła P.

Mathematica Applicanda

|

2012

|

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].

3

A Survey of Results on Stateless Multicounter Automata

Ibarra O.H., Egecioglu Ö.

Fundamenta Informaticae

|

2012

|

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.

4

Blind Counter Automata on w-Words

Fernau H., Stiebe R.

Fundamenta Informaticae

|

2008

|

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.

5

New Language Operations in Formal Language Theory

Meduna A., Vítek M.

Schedae Informaticae

|

2004

|

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.

6

Closure Properties of Multiset Language Families

Kudlek M., Mitrana V.

Fundamenta Informaticae

|

2002

|

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.

7

Timed Cooperating Automata

Lanotte R., Maggiolo-Schettini A.

Fundamenta Informaticae

|

2000

|

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.