Wyniki wyszukiwania - BazTech

1

State Complexity of Multiple Catenations

Caron P., Luque J.-G., Patrou B.

Fundamenta Informaticae

|

2018

|

Vol. 160, nr 3

255--279

EN

We improve some results relative to the state complexity of the multiple catenations described by Gao and Yu. In particular we nearly divide by 2 the size of the alphabet needed for witnesses. We also give some refinements to the algebraic expression of the state complexity, which is especially complex with this operation. We obtain these results by using peculiar DFAs defined by Brzozowski.

2

Finding Shortest Triangular Path and its Family inside a Digital Object

Sarkar A., Biswas A., Dutt M., Mondal S.

Fundamenta Informaticae

|

2018

|

Vol. 159, nr 3

297--325

EN

This article presents a combinatorial algorithm to find a shortest triangular path (STP) between two points inside a digital object imposed on triangular grid that runs in O(n/g log n/g) time, where n is the number of pixels on the contour of the object and g is the grid size. Initially, the inner triangular cover which maximally inscribes the object is constructed to ensure that the path lies within the object. An appropriate bounding parallelogram is considered with those two points in diagonally opposite corners and then one of the semi-perimeters of the parallelogram is traversed. Certain combinatorial rules are formulated based on the properties of triangular grid and are applied during the traversal whenever required to shorten the triangular path. A shortest triangular path between any two points may not be unique. Another combinatorial algorithm is presented, which finds the family of shortest triangular path (FSTP) (i.e., the region containing all possible shortest triangular paths) between two given points inside a digital object and runs in O(n/g log n/g) time. Experimental results are presented to verify the correctness, robustness, and efficacy of the algorithms. STP and FSTP can be useful for shape analysis of digital objects and determining shape signatures.

3

A New Proof for Undecidability of the Bi-Infinite Post Correspondence Problem

Halava V., Harju T., Sahla E.

Fundamenta Informaticae

|

2017

|

Vol. 154, nr 1/4

167--176

EN

We give a new simplified proof for undecidability of the Bi-Infinite Post Correspondence Problem (ℤPCP). We reduce the special case of the word problem of semi-Thue systems to ℤPCP.

4

Shift Design with Answer Set Programming

Abseher M., Musliu N., Woltran S., Gebser M., Schaub T.

Fundamenta Informaticae

|

2016

|

Vol. 147, nr 1

1--25

EN

Answer Set Programming (ASP) is a powerful declarative programming paradigm that has been successfully applied to many different domains. Recently, ASP has also proved successful for hard optimization problems like course timetabling and travel allotment. In this paper, we approach another important task, namely, the shift design problem, aiming at an alignment of a minimum number of shifts in order to meet required numbers of employees (which typically vary for different time periods) in such a way that over- and understaffing is minimized. We provide an ASP encoding of the shift design problem, which, to the best of our knowledge, has not been addressed by ASP yet. Our experimental results demonstrate that ASP is capable of improving the best known solutions to some benchmark problems. Other instances remain challenging and make the shift design problem an interesting benchmark for ASP-based optimization methods.

5

The Identity Transform of a Permutation and its Applications

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

Fundamenta Informaticae

|

2015

|

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.

6

DNA Tiles, Wang Tiles and Combinators

Bellia M., Occhiuto M. E.

Fundamenta Informaticae

|

2014

|

Vol. 133, nr 2/3

105--121

EN

We investigate the relation between Combinatory Logic and Wang Tiles with the aim of studying Combinators as a programming language for Self-Assembly and DNA computing. We introduce a subset of Combinatory Logic, SKI#, which is Turing Complete, includes simply Typed Combinatory Logic and contains only combinators whose computations require finitely many different redexes. Then, we define a language of Tiles, SKI-Tile, for the representation and the computation of the terms of SKI# in Self-Assembly. Moreover, we introduce a program development methodology that given any computable function, expressed in SKI#, provides a finite set of Tiles that self-assemble to return the computations of the function applications. Finally, the methodology is applied to the derivation of a SKI-Tile program that self-assemble to compute the factorial function.

7

Combinatorial Algorithms for Computing Degenerations of Modules of Finite Dimension

Mróz A., Zwara G.

Fundamenta Informaticae

|

2014

|

Vol. 132, nr 4

519--532

EN

We present combinatorial algorithms for solving three problems that appear in the study of the degeneration order ≤degfor the variety of finite-dimensional modules over a k-algebra Δ, where M ≤deg N means that a module N belongs to an orbit closure O(M) of a module M in the variety of Δ-modules. In particular, we introduce algorithmic techniques for deciding whether or not the relation M ≤deg N holds and for determining all predecessors (resp. succesors) of a given module M with respect to ≤deg. The order ≤deg plays an important role in modern algebraic geometry and module theory. Applications of our technique and experimental tests for particular classes of algebras are presented. The results show that a computer algebra technique and algorithmic computer calculations provide important tools in solving theoretical mathematics problems of high computational complexity. The algorithms are implemented and published as a part of an open source GAP package called QPA.

8

Tresses of polygons

Łupiński A., Petelczyc K., Prażmowski K.

Demonstratio Mathematica

|

2007

|

Vol. 40, nr 2

419-439

EN

A class of configurations which can be considered as series of suitably inscribed closed polygons is introduced and some fundamental properties of them are established.