Wyniki wyszukiwania - BazTech

1

On some inclusion in the set theory

Ochab Justyna, Ulaszek Marcin

Journal of Mathematics and Applications

|

2022

|

Vol. 45

129--132

EN

This note contains the proof of an inclusion in the set theory. In that proof we use only basic laws appearing in the set theory. More precisely, using some basic laws of the set theory we provide the proof of an inclusion which is applied in the proof of certain theorem of the classical measure theory. The presented paper has an elementary character. Only the basic tools of the set theory are involved.

2

Dwa spojrzenia na nieskończoność

Samulewicz Alicja, Starosolski Andrzej

MINUT Matematyka i Informatyka na Uczelniach Technicznych

|

2021

|

Nr 3

52-60

PL

Z nieskończonością spotykamy się bardzo często w wielu działach matematyki. Celem tego artykułu jest przybliżenie Czytelnikowi, czym właściwie jest ta nieskończoność, a raczej czym są te nieskończoności.

3

Combinatorial Etude

Stoenchev Miroslav, Todorov Venelin

Annals of Computer Science and Information Systems

|

2021

|

Vol. 25

231--234

EN

The purpose of this article is to consider a special class of combinatorial problems, the so called Prouhet-Tarry Escot problem, solution of which is realized by constructing finite sequences of ±1. For example, for fixed p∈N, is well known the existence of np∈N with the property: any set of np consecutive integers can be divided into 2 sets, with equal sums of its p[th] powers. The considered property remains valid also for sets of finite arithmetic progressions of complex numbers.

4

Rodziny zbiorów, zadania wprowadzające do teorii miary

Burzyk Józef, Pochciał Jan

MINUT Matematyka i Informatyka na Uczelniach Technicznych

|

2020

|

Nr 2

92-99

PL

Prezentowany zestaw zadań poprzedzony kilkoma pojęciami wstępnymi ma charakter wprowadzający w problematykę funkcji rzeczywistych, teorii miary i tematyki pokrewnej. Jest wynikiem kilkuletnich doświadczeń autorów związanych z prowadzeniem zajęć z Teorii funkcji rzeczywistych na Wydziale Matematyczno-Fizycznym Politechniki Śląskiej. Może być wykorzystywany zarówno przez studentów jak i prowadzących zajęcia. Autorem przeważającej większości niestandardowych zadań jest pierwszy z autorów, którego wkład w powstanie tej pracy jest absolutnie kluczowy.

5

An Experimental Study on Symmetry Breaking Constraints Impact for the One Dimensional Bin-Packing Problem

Hadj Salem Khadija, Kieffer Yann

Annals of Computer Science and Information Systems

|

2020

|

Vol. 21

317--326

EN

We consider the classical One-Dimensional Bin Packing Problem (1D-BPP), an NP-hard optimization problem, where, a set of weighted items has to be packed into one or more identical capacitated bins. We give an experimental study on using symmetry breaking constraints for strengthening the classical integer linear programming proposed to optimally solve this problem. Our computational experiments are conducted on the data-set found in BPPLib and the results have confirmed the theoretical results.

6

Graphical Partitions and Graphical Relations

Shaheen Tanzeela, Stell John G.

Fundamenta Informaticae

|

2019

|

Vol. 165, nr 1

75--98

EN

We generalize the well-known correspondence between partitions and equivalence relations on a set to the case of graphs and hypergraphs. This is motivated by the role that partitions and equivalence relations play in Rough Set Theory and the results provide some of the foundations needed to develop a theory of rough graphs. We use one notion of a partition of a hypergraph, which we call a graphical partition, and we show how these structures correspond to relations on a hypergraph having additional properties. In the case of a hypergraph with only nodes and no edges these properties are exactly the usual reflexivity, symmetry and transitivity properties required for equivalence relations on a set. We present definitions for upper and lower approximations of a subgraph with respect to a graphical partition. These generalize the well-known approximations in Rough Set Theory. We establish fundamental properties of our generalized approximations and provide examples of these constructions on some graphs.

7

A Minimum set-cover problem with several constraints

Dörpinghaus Jens, Düing Carsten, Weil Vera

Annals of Computer Science and Information Systems

|

2019

|

Vol. 18

115--122

EN

A lot of problems in natural language processing can be interpreted using structures from discrete mathematics. In this paper we will discuss the search query and topic finding problem using a generic context-based approach. This problem can be described as a a Minimum Set Cover Problem with several constraints. The goal is to find a minimum covering of documents with the given context for a fixed weight function. The aim of this problem reformulation is a deeper understanding of both the hierarchical problem using union and cut as well as the non-hierarchical problem using the union. We thus choose a modeling using bipartite graphs and suggest a novel reformulation using an integer linear program as well as novel graph-theoretic approaches.

8

On existence of the support of a Borel measure

Kozarzewski P. A.

Demonstratio Mathematica

|

2018

|

Vol. 51, nr 1

76--84

EN

We present arguments showing that the standard notion of the support of a probabilistic Borel measure is not well defined in every topological space. Our goal is to create a "very inseparable" space and to show the existence of a family of closed sets such that each of them is of full measure, but their intersection is empty. The presented classic construction is credited to Jean Dieudonné and dates back to 1939. We also propose certain, up to our best knowledge, new simplifications.

9

Herbrand-satisfiability of a Quantified Set-theoretic Fragment

Cantone D., Longo C., Nicolosi-Asmundo M.

Fundamenta Informaticae

|

2017

|

Vol. 150, nr 1

49--71

EN

In the last decades, several fragments of set theory have been studied in the context of Computable Set Theory. In general, the semantics of set-theoretic languages differs from the canonical first-order semantics in that the interpretation domain of set-theoretic terms is fixed to a given universe of sets. Because of this, theoretical results and various machinery developed in the context of first-order logic could be not easily applicable in the set-theoretic realm. Recently, the decidability of quantified fragments of set theory which allow one to explicitly handle ordered pairs has been studied, in view of applications in the field of knowledge representation. Among other results, a NEXPTIME decision procedure for satisfiability of formulae in one of these fragments, ∀0π , has been devised. In this paper we exploit the main features of such a decision procedure to reduce the satisfiability problem for the fragment ∀0π to the problem of Herbrand satisfiability for a first-order language extending it. In addition, it turns out that such a reduction maps formulae of the Disjunctive Datalog subset of ∀0π into Disjunctive Datalog formulae.

10

True Concurrent Equivalences in Time Petri Nets

Virbitskaite I., Bushin D., Best E.

Fundamenta Informaticae

|

2016

|

Vol. 149, nr 4

401--418

EN

The intention of the paper is towards a framework for developing, studying and comparing observational equivalences in the setting of a real-time true concurrent model. In particular, we introduce a family of trace and bisimulation equivalences in interleaving, step, partial order and causal net semantics in the setting of time Petri nets (elementary net systems whose transitions are labeled with time firing intervals, can fire only if their lower time bounds are attained, and are forced to fire when their upper time bounds are reached) [3]. We deal with the relationships between the equivalences showing the discriminating power of the approaches of the linear-time - branching-time and interleaving - partial order spectra and construct a hierarchy of equivalent classes of time Petri nets. This allows studying in complete detail the timing behaviour in addition to the degrees of relative concurrency and nondeterminism of processes.

11

Specialized Predictor for Reaction Systems with Context Properties

Barbuti R., Gori R., Levi F., Milazzo P.

Fundamenta Informaticae

|

2016

|

Vol. 147, nr 2/3

173--191

EN

Reaction systems are a qualitative formalism for modeling systems of biochemical reactions characterized by the non-permanency of the elements: molecules disappear if not produced by any enabled reaction. Reaction systems execute in an environment that provides new molecules at each step. Brijder, Ehrenfeucht and Rozemberg introduced the idea of predictors. A predictor of a molecule s, for a given n, is the set of molecules to be observed in the environment to determine whether s is produced or not at step n by the system. We introduced the notion of formula based predictor, that is a propositional logic formula that precisely characterizes environments that lead to the production of s after n steps. In this paper we revise the notion of formula based predictor by defining a specialized version that assumes the environment to provide molecules according to what expressed by a temporal logic formula. As an application, we use specialized formula based predictors to give theoretical grounds to previously obtained results on a model of gene regulation.

12

Lattice Theory for Rough Sets : A Case Study with Mizar

Grabowski A.

Fundamenta Informaticae

|

2016

|

Vol. 147, nr 2/3

223--240

EN

Rough sets offer a well-known approach to incomplete or imprecise data. In the paper I briefly report how this framework was successfully encoded by means of one of the leading computer proof-assistants in the world. The general approach is essentially based on binary relations, and all natural properties of approximation operators can be obtained via adjectives added to underlying relations. I focus on lattice-theoretical aspects of rough sets to enable the application of external theorem provers like EQP or Prover9 as well as to translate them into TPTP format widely recognized in the world of automated proof search. I wanted to have a clearly written, possibly formal, although informal as a rule, paper authored by a specialist from the discipline another than lattice theory. It appeared that Lattice theory for rough sets by Jouni Järvinen (called LTRS for short) was quite a reasonable choice to be a testbed for the current formalisation both of lattices and of rough sets. A popular computerised proof-assistant Mizar was used as a tool, hence all the efforts are available in one of the largest repositories of computer-checked mathematical knowledge, called Mizar Mathematical Library.

13

Core for Large Datasets : Rough Sets on FPGA

Kopczyński M., Grześ T., Stepaniuk J.

Fundamenta Informaticae

|

2016

|

Vol. 147, nr 2/3

241--259

EN

This paper presents FPGA and softcore CPU based device for large datasets core calculation using rough set methods. Presented architectures have been tested on two real datasets by downloading and running presented solutions inside FPGA. Tested datasets had 1 000 to 10 000 000 objects. The same operations were performed in software implementation. Obtained results show the big acceleration in computation time using hardware supporting core generation in comparison to pure software implementation.

14

Combinatorial Geometry and Coding Theory

Raigorodskii A. M.

Fundamenta Informaticae

|

2016

|

Vol. 145, nr 3

359--369

EN

In this paper, we overview three closely related problems: Nelson-Hadwiger problem on coloring spaces with forbidden monochromatics distances; Borsuk's problem on partitioning sets in spaces into parts of smaller diameter; problem of finding codes with forbidden Hamming distances.

15

A Relational Logic for Spatial Contact Based on Rough Set Approximation

Düntsch I., Orłowska E., Wang H.

Fundamenta Informaticae

|

2016

|

Vol. 148, nr 1/2

191--206

EN

In previous work we have presented a class of algebras enhanced with two contact relations representing rough set style approximations of a spatial contact relation. In this paper, we develop a class of relational systems which is mutually interpretable with that class of algebras, and we consider a relational logic whose semantics is determined by those relational systems. For this relational logic we construct a proof system in the spirit of Rasiowa-Sikorski, and we outline the proofs of its soundness and completeness.

16

Efficient similarity measures for texts matching

Akinwale A., Niewiadomski A.

Journal of Applied Computer Science

|

2015

|

Vol. 23, nr 1

7--28

EN

Calculation of similarity measures of exact matching texts is a critical task in the area of pattern matching that needs a great attention. There are many existing similarity measures in literature but the best methods do not exist for closeness measurement of two strings. The objective of this paper is to explore the grammatical properties and features of generalized n-gram matching technique of similarity measures to find exact text in electronic computer applications. Three new similarity measures have been proposed to improve the performance of generalized n-gram method. The new methods assigned high values of similarity measures and performance to price with low values of running time. The experiment with the new methods demonstrated that they are universal and very useful in words that could be derived from the word list as a group and retrieve relevant medical terms from database . One of the methods achieved best correlation of values for the evaluation of subjective examination.

17

Yurii Rogozhin’s Contributions to the Field of Small Universal Turing Machines

Woods D., Neary T.

Fundamenta Informaticae

|

2015

|

Vol. 138, nr 1/2

251--258

EN

In the field of small universal Turing machines, Yurii Rogozhin holds a special prize: he was first to close off an infinite number of open questions by drawing a closed curve that separates the infinite set of Turing machines that are universal from a finite set of small machines for which we don’t yet know. Rogozhin did this by finding the smallest known universal Turing machines at the time, both in terms of number of states and number of symbols. This brief note summarises this and a few of Yurii’s other contributions to the field, including his work with Manfred Kudlek on small circular Post machines.

18

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.

19

Maximizing T-complexity

Clark G., Teutsch J.

Fundamenta Informaticae

|

2015

|

Vol. 139, nr 1

1--19

EN

We investigate Mark Titchener’s T-complexity, an algorithm which measures the information content of finite strings. After introducing the T-complexity algorithm, we turn our attention to a particular class of “simple” finite strings. By exploiting special properties of simple strings, we obtain a fast algorithm to compute the maximum T-complexity among strings of a given length, and our estimates of these maxima show that T-complexity differs asymptotically from Kolmogorov complexity. Finally, we examine how closely de Bruijn sequences resemble strings with high Tcomplexity.

20

Logical Theory of the Monoid of Languages over a Non Tally Alphabet

Choffrut C., Grigorieff S.

Fundamenta Informaticae

|

2015

|

Vol. 138, nr 1/2

159--177

EN

We consider the first-order theory of the monoid P(A*) of languages over a finite or infinite alphabet A (with at least two letters) endowed solely with concatenation lifted to sets: no set theoretical predicate or function, no constant. Coding a word u by the submonoid u* it generates, we prove that the operation (u*, v*) → (uv)* and the predicate {(u*,X) | ε ∈ X, u ∈ X} are definable in P(A*); •,=i. This allows to interpret the second-order theory of A*; •,=i in the first-order theory of P(A*); •,=i and prove the undecidability of the Π8 fragment of this last theory. These results involve technical difficulties witnessed by the logical complexity of the obtained definitions: the above mentioned predicates are respectively Δ5 and Δ7.