Wyniki wyszukiwania - BazTech

1

On the Expressive Power of Non-deterministic and Unambiguous Petri Nets over Infinite Words

Finkel Olivier, Skrzypczak Michał

Fundamenta Informaticae

|

2021

|

Vol. 183, nr 3-4

243--291

EN

To identify the causes of performance problems or to predict process behavior, it is essential to have correct and complete event data. This is particularly important for distributed systems with shared resources, e.g., one case can block another case competing for the same machine, leading to inter-case dependencies in performance. However, due to a variety of reasons, real-life systems often record only a subset of all events taking place. To understand and analyze the behavior and performance of processes with shared resources, we aim to reconstruct bounds for timestamps of events in a case that must have happened but were not recorded by inference over events in other cases in the system. We formulate and solve the problem by systematically introducing multi-entity concepts in event logs and process models. We introduce a partial-order based model of a multi-entity event log and a corresponding compositional model for multi-entity processes. We define PQR-systems as a special class of multi-entity processes with shared resources and queues. We then study the problem of inferring from an incomplete event log unobserved events and their timestamps that are globally consistent with a PQR-system. We solve the problem by reconstructing unobserved traces of resources and queues according to the PQR-model and derive bounds for their timestamps using a linear program. While the problem is illustrated for material handling systems like baggage handling systems in airports, the approach can be applied to other settings where recording is incomplete. The ideas have been implemented in ProM and were evaluated using both synthetic and real-life event logs.

2

Length-k-overlap-free Binary Infinite Words

Séébold P.

Fundamenta Informaticae

|

2012

|

Vol. 116, nr 1-4

251-263

EN

We study length-k-overlap-free binary infinite words, i.e., binary infinite words which can contain only overlaps xyxyx with |x| ≤ k-1. We prove that no such word can be generated by a morphism, except if k = 1. On the other hand, for every k ≥ 2, there exist length-k-overlap-free binary infinite words which are not length-(k-1)-overlap-free. As an application, we prove that, for every non-negative integer n, there exist infinitely many length-k-overlap-free binary infinite partial words with n holes.

3

On the Borel Complexity of MSO Definable Sets of Branches

Bojańczyk M., Niwiński D., Rabinovich A., Radziwończyk–Syta A., Skrzypczak M.

Fundamenta Informaticae

|

2010

|

Vol. 98, nr 4

337-349

EN

An infinite binaryword can be identified with a branch in the full binary tree. We consider sets of branches definable in monadic second-order logic over the tree, where we allow some extra monadic predicates on the nodes. We show that this class equals to the Boolean combinations of sets in the Borel class Σ over the Cantor discontinuum. Note that the last coincides with the Borel complexity of ω-regular languages.

4

Associativity of Infinite Synchronized Shuffles and Team Automata

ter Beek M.H., Kleijn J.

Fundamenta Informaticae

|

2009

|

Vol. 91, nr 3-4

4437-461

EN

Motivated by different ways to obtain team automata from synchronizing component automata, we consider various definitions of synchronized shuffles of words. A shuffle of two words is an interleaving of their symbol occurrenceswhich preserves the original order of these occurrences within each of the two words. In a synchronized shuffle, however, also two occurrences of one symbol, each from a different word, may be identified as a single occurrence. In case at least one of the words involved is infinite, a (synchronized) shuffle can also be unfair in the sense that an infinite word may prevail fromsome point onwards even when the other word still has occurrences to contribute to the shuffle. We prove that for the synchronized shuffle operations under consideration, every (fair or unfair) synchronized shuffle can be obtained as a limit of synchronized shuffles of the finite prefixes of the words involved. In addition, it is shown that with the exception of one, all synchronized shuffle operations that we consider satisfy a natural notion of associativity, also in case of unfairness. Finally, using these results, some compositionality results for team automata are established.

5

Undecidability in w-Regular Languages

Halava V., Harju T., Karhumäki J.

Fundamenta Informaticae

|

2006

|

Vol. 73, nr 1-2

119-125

EN

In the infinite Post Correspondence Problem an instance (h,g) consists of two morphisms h and g, and the problem is to determine whether or not there exists an infinite word a such that h(a) = g(a). In the general case this problem was shown to be undecidable by K. Ruohonen (1985). Recently, it was proved that the infinite PCP is undecidable already when the domain alphabet of the morphisms consists of at least 9 letters. Here we show that the problem is undecidable for instances where the morphisms have a domain of 6 letters, when we restrict to solutions of w-languages of the form Rw where R is a given regular language.

6

Analiza ciągłości pewnych odwzorowań na zbiorze skończonych i prawostronnie nieskończonych słów

Matyja J.

Zeszyty Naukowe. Organizacja i Zarządzanie / Politechnika Śląska

|

2004

|

z. 20 cz. 1

93-100

PL

W tej pracy zajmujemy się szczególnymi odwzorowaniami genetycznymi przez endomorfizmy wolnych monoidów. Jest wiele prac zajmujących się takimi odwzorowaniami. Cześć z nich koncentruje się na ich kombinatorycznych własnościach, a inne na cechach stowarzyszonych, topologicznych przestrzeni. Jak przedstawiono to poniżej, własności te mogą być również łączone.

EN

In this paper we are dealing with particular mappings, generated by endomorphisms of free monoids. There exist many papers related to these mapping. Some of them are concerned with their combinatorial properties, others with the properties of associated topological spaces. These properties can also be joined, as described below.

7

An ω-Power of a Finitary Language Which is a Borel Set of Infinite Rank

Finkel O.

Fundamenta Informaticae

|

2004

|

Vol. 62, nr 3,4

333--342

EN

ω-powers of finitary languages are ω-languages s in the form Vω, where V is a finitary language over a finite alphabet Σ. Since the set Σ,sup>ω of infinite words over Σ can be equipped with the usual Cantor topology, the question of the topological complexity of ω-powers naturally arises and has been raised by Niwinski [13], by Simonnet [15], and by Staiger [18]. It has been proved in [4] that for each integer n ≥ 1, there exist some ω-powers of context free languages which are Πn0-complete Borel sets, and in [5] that there exists a context free language L such that Lω is analytic but not Borel. But the question was still open whether there exists a finitary language V such that Vω is a Borel set of infinite rank. We answer this question in this paper, giving an example of a finitary language whose ω-power is Borel of infinite rank.