A Fast Algorithm Finding the Shortest Reset Words
In this paper we present a new fast algorithm finding minimal reset words for finite synchronizing automata. The problem is know to be computationally hard, and our algorithm is exponential. Yet, it is faster than the algorithms used so far and it works well in practice. The main idea is to use a bidirectional BFS and radix (Patricia) tries to store and compare resulted subsets. We give both theoretical and practical arguments showing that the branching factor is reduced efficiently. As a practical test we perform an experimental study of the length of the shortest reset word for random automata with $n$ states and 2 input letters. We follow Skvorsov and Tipikin, who have performed such a s…
A Fast Algorithm Finding the Shortest Reset Words
In this paper we present a new fast algorithm for finding minimal reset words for finite synchronizing automata, which is a problem appearing in many practical applications. The problem is known to be computationally hard, so our algorithm is exponential in the worst case, but it is faster than the algorithms used so far and it performs well on average. The main idea is to use a bidirectional BFS and radix (Patricia) tries to store and compare subsets. Also a number of heuristics are applied. We give both theoretical and practical arguments showing that the effective branching factor is considerably reduced. As a practical test we perform an experimental study of the length of the shortest …
Preliminary report on the microvertebrate faunal remains from the Late Triassic locality at Krasiejów, SW Poland
Fossil vertebrate remains from the Keuper unit in the vicinity of the village of Krasiejów have been analyzed for almost two decades. However, the main goal of these works was focused mainly on large vertebrates. Here the authors present the first description of microvertebrate fossils from that site. The collection of around 5,000 specimens is mainly comprised of teeth and scales. The most numerous remains belong to osteichthyans: dipnoans (Ptychoceratodus and cf. Arganodus), palaeoniscids, semionotids, redfieldiids and chondrichthyans, such as Lonchidion sp., which is the first indisputable record of that genus in the Upper Triassic of Poland and the first shark at the Krasiejów locality.…
Eucynodont teeth from the Late Triassic of Krasiejów, Southern Poland
Recent discoveries of Mammaliamorph teeth in the Keuper of southern Poland have extended the global record of eucynodonts in the Late Triassic and revealed a significant diversity of the group at that time. Here,we expand on this record with the description of new cynodont postcanine teeth from the Krasiejów bone bed. They show the dental morphology typical for Dromatheriidae, with a single root and crown without cingulum. We assigned them to Polonodon woznikensis, described from Woźniki. None of the 38 teeth from Krasiejów and Woźniki exhibit signs of serious wear, potentially indicating a very fast rate of tooth replacement in Polonodon.