Wyniki wyszukiwania - Biblioteka Nauki

1

Polygons Drawn from Permutations

100%

Bilotta S. , Rinaldi S. , Socci S.

Fundamenta Informaticae

|

2013

|

tom Vol. 125, nr 3/4

329--342

EN

In this paper we consider the class of column-convex permutominoes, i.e. column-convex polyominoes defined by a pair of permutations (π1, π2). First, using a geometric construction, we prove that for every permutation π there is at least one column-convex permutomino P such that π1(P) = π or π2(P) = π. In the second part of the paper, we show how, for any given permutation π, it is possible to define a set of logical implications F(p) on the points of π, and prove that there exists a column-convex permutomino P such that π1(P) = π if and only if F(p) is satisfiable. This property can be then used to give a characterization of the set of column-convex permutominoes P such that π1(P) = π.

2

On Fixed Points of the Burrows-Wheeler Transform

80%

Mantaci S. , Restivo A. , Rosone G. , Russo F. , Sciortino M.

Fundamenta Informaticae

|

2017

|

tom Vol. 154, nr 1/4

277--288

EN

The Burrows-Wheeler Transform is a well known transformation widely used in Data Compression: important competitive compression software, such as Bzip (cf. [1]) and Szip (cf. [2]) and some indexing software, like the FM-index (cf. [3]), are deeply based on the Burrows Wheeler Transform. The main advantage of using BWT for data compression consists in its feature of “clustering” together equal characters. In this paper we show the existence of fixed points of BWT, i.e., words on which BWT has no effect. We show a characterization of the permutations associated to BWT of fixed points and we give the explicit form of fixed points on a binary ordered alphabet {a, b} having at most four b’s and those having at most four a’s.

3

Paweł Hendrich’s Emergent Sound System

80%

Hendrich P. , Stefański K.

Musicology Today

|

2015

|

tom 12

|

nr 1

116-126

EN

Paweł Hendrich’s compositions can be compared to macrocrystals - solids composed of numerous small and identical elements, constructed in accordance with a strict pattern. Importantly, the same internal crystal structure can produce forms highly diversified with regard to external shape. Similarly, this composer’s works are very precisely structured already on the level of individual sounds, but this structure is only a tool for the creation of very clear musical macroforms. The idea of emergence - of new values resulting from the combination of simple elements - is of key importance to this composer. The paper presents the principles of organising music material in the works of Paweł Hendrich. These are, among others: periodicity, multilayered structures, permutations and flexibility. These ideas are reflected in the musical work in many dimensions, both on the level of microand macro-structure. Their application exerts a major impact on the forms created by the composer. With the development of his musical language, the composer transforms his initial material more and more radically. Simple elements and processes that underlie the construction of his works become progressively more and more difficult to reconstruct, largely due to the application of a computer in the composition process. A comprehensive look at Paweł Hendrich’s entire output of compositions proves that his work is emergent as a whole. With each new piece, a new element is added, but all of them form a coherent system. No wonder, then, that one of the composer’s works bears the telling title of Emergon.

4

Adaptive reordering of observation space to improve pattern recognition

80%

Kulikowski J. L.

TASK Quarterly : scientific bulletin of Academic Computer Centre in Gdansk

|

2007

|

tom Vol. 11, No 1-2

59-69

EN

The problem of observation space reordering is presented as a novel approach to pattern recognition based on non-parametric, combinatorial statistical tests. It consists in linearly ordering the elements of a discrete multi-dimensional observation space along a curve such that elements belonging to different similarity classes are as close to each other as possible, the similarity classes are mutually separated, and the length of the curve is kept to minimum. The problem is NP-difficult and it is shown how its approximate solution can be reached by a series of transformations improving the initial lexicographic linear order of a discrete observation space. Recommendations are formulated for linear order improvement leading to a pattern recognition algorithm based on serial statistical test.

5

Uniform Generation of languages by scattered context grammars

80%

Meduna A.

Fundamenta Informaticae

|

2001

|

tom Vol. 45, nr 3

231-235

EN

The present paper discusses the uniform generation of languages by scattered context grammars. More specifically, it demonstrates that every recursively enumerable language can be generated by a scattered context grammar, G, so that every sentential form in a generation of a sentence has the form y1Ľym u, where u is a terminal word and each yi is a permutation of either of two equally long words, z1 E {A, B,C}* and z2 E {A, B, D}*, where A, B, C, and D are G's nonterminals. Then, it presents an analogical result so that u precedes y1...ym.

6

Remarks on Memory Consistency Description

70%

Czaja L.

Fundamenta Informaticae

|

2016

|

tom Vol. 147, nr 2/3

209--221

EN

Two observations in the matter of pictorial as well as formal presentation of some consistency in distributed shared memory are made. The first concerns geometric transformation of line segments and points picturing read/write operations, the second - converting partial order of the operations into linear order of their initiations and terminations. This allows to reduce serialization of the read/write operations as a whole to permutations of their beginnings and ends. Some draft proposals are introduced.

7

More on Square-free Words Obtained from Prefixes by Permutations

70%

Ochem P.

Fundamenta Informaticae

|

2014

|

tom Vol. 132, nr 1

109--112

EN

An infinite square-free word w over the alphabet Σ3 = {0, 1, 2} is said to have a k-stem σ if |σ| = k and w = σw1w2· · · where for each i, there exists a permutation πi of Σ3 which extended to a morphism gives wi= πi (σ). Harju proved that there exists an infinite k-stem word for k = 1, 2, 3, 9 and 13 ≤ k ≤ 19, but not for 4 ≤ k ≤ 8 and 10 ≤ k ≤ 12. He asked whether k-stem words exist for each k ≥ 20. We give a positive answer to this question. Currie has found another construction that answers Harju’s question.

8

The Structure of Elementary Strategies for Gene Assembly in Ciliates

70%

Rogojin V. , Petre I.

Fundamenta Informaticae

|

2015

|

tom Vol. 138, nr 1/2

145--158

EN

We consider in this paper the assembly of micronuclear genes in stichotrichous ciliates to their macronuclear form. We represent the micronuclear genes and all their intermediate forms from micro- to macro- as signed permutations, where integer i stands for the i-th MDS of the macronuclear gene and i stands for the inverted form of that MDS; the macronuclear assembled gene is represented as the sorted permutation 1 2 : : : n, while its micronuclear form is an arbitrary signed permutation. We focus on the elementary gene assembly model consisting of two operations on signed permutations: eh (elementary hairpin inverting) and ed (elementary double recombination); gene assembly is modeled in this framework as a permutation sorting process. The general problem we investigate is to give a characterization of all signed permutations that can be sorted by the elementary operations. We make progress towards a full solution for this problem by relating sequences of eh and ed operations applicable to a given permutation to paths in the dependency graph associated to that permutation.

9

The Identity Transform of a Permutation and its Applications

70%

Frosini A. , Battaglino D. , Rinaldi S. , Socci S.

Fundamenta Informaticae

|

2015

|

tom Vol. 141, nr 2/3

191--205

EN

Starting from a Theorem by Hall, we define the identity transform of a permutation π as C(π) = (0 + π(0), 1 + π(1), ..., (n - 1) + π(n - 1)), and we define the set Cn = {(C(π) : π ∈ Sn}, where Sn is the set of permutations of the elements of the cyclic group Zn. In the first part of this paper we study the set Cn: we show some closure properties of this set, and then provide some of its combinatorial and algebraic characterizations and connections with other combinatorial structures. In the second part of the paper, we use some of the combinatorial properties we have determined to provide a different algorithm for the proof of Hall's Theorem.

10

Automorphism Classification of Cellular Automata

60%

Nishio H.

Fundamenta Informaticae

|

2010

|

tom Vol. 104, nr 1/2

125-140

EN

A new classification of arbitrary cellular automata (CA for short) in Z^d is studied considering the set (group) of all permutations of the neighborhood v and state set Q. Two CA (Z^d, Q, f_A, .A) and (Z^d, Q, f_B, v_B) are called automorphic, if there is a pair of permutationsπ&pfi" of v and Q, respectively, such that (f_B, vB) = ([formula] where v^π denotes a permutation of v and f*π denotes a permutation of arguments of local function f corresponding to v*π This automorphism naturally induces a classification of CA, such that it generally preserves the global properties of CA up to permutation. As a typical example of the theory, the local functions of 256 ECA (1- dimensional 3-nearest neighbors 2-states CA) are classified into 46 classes. We also give a computer test of surjectivity, injecitivity and reversibility of the classes.

11

Sets with two associative operations

60%

Pirashvili T.

Open Mathematics

|

2003

|

tom 1

|

nr 2

169-183

EN

In this paper we consider duplexes, which are sets with two associative binary operations. Dimonoids in the sense of Loday are examples of duplexes. The set of all permutations carries a structure of a duplex. Our main result asserts that it is a free duplex with an explicitly described set of generators. The proof uses a construction of the free duplex with one generator by planary trees.

12

Generowanie permutacji z wykorzystaniem odwzorowań chaotycznych

60%

Lawnik M.

Studia Informatica

|

2014

|

tom Vol. 35, nr 1

21--27

PL

Prezentowany w tym artykule algorytm służy do generacji permutacji zbiorów skończonych, z wykorzystaniem odwzorowań chaotycznych. Jego zmodyfikowana wersja może być wykorzystana do generacji permutacji z zadanymi wcześniej wagami.

EN

Presented in this article algorithm is used to generate permutations of finite set basing upon chaotic maps. The modified version of this algorithm may be used to generate a permutation with previously predetermined weights.

13

Discrete Fourier transform and permutations

51%

Hui S. , Żak S. H.

Bulletin of the Polish Academy of Sciences. Technical Sciences

|

2019

|

tom Vol. 67, nr 6

995--1005

EN

It is well known that the magnitudes of the coefficients of the discrete Fourier transform (DFT) are invariant under certain operations on the input data. In this paper, the effects of rearranging the elements of an input data on its DFT are studied. In the one-dimensional case, the effects of permuting the elements of a finite sequence of length N on its Discrete Fourier transform (DFT) coefficients are investigated. The permutations that leave the unordered collection of Fourier coefficients and their magnitudes invariant are completely characterized. Conditions under which two different permutations give the same DFT coefficient magnitudes are given. The characterizations are based on the automorphism group of the additive group ZN of integers modulo N and the group of translations of ZN. As an application of the results presented, a generalization of the theorem characterizing all permutations that commute with the discrete Fourier transform is given. Numerical examples illustrate the obtained results. Possible generalizations and open problems are discussed. In higher dimensions, results on the effects of certain geometric transformations of an input data array on its DFT are given and illustrated with an example.

14

The strongly and weakly divergent permutations

51%

Wituła R. , Przybyła M.

Demonstratio Mathematica

|

2006

|

tom Vol. 39, nr 1

107-116

EN

We introduce the concepts of strongly and weakly divergent permutations and consider some relations between them.

15

On Erdos' theorem for monotonic subsequences

51%

Wituła R. , Słota D. , Seweryn R.

Demonstratio Mathematica

|

2007

|

tom Vol. 40, nr 2

229-259

EN

In this paper finite one-one sequences of reals are studied. We consider the strengthening of famous Erdös'theorem. We discuss the lengths of the largest decreasing and increasing subsequences of the given sequences. Also, we study the length of the largest monotonic subsequences, which the first or the last elment is equal to a given elment ai of the sequence a. What is particulary important is the connection betwen estimation of these values with the problem of the existence of the3-elements monotonic subsequences of a having the form{ak, ak+1, ak+2}. Moreover, we introduce some conditons which are sufficient to the existence of such 3-elments subsequences of sequence a. As a new example of the application of Erdös' theorem for monotonic subsequences we give a combinatoric characterization of divergent permutations.