Wyniki wyszukiwania - BazTech

1

Q∖Z is diophantine over Q with 32 unknowns

Zhang Geng-Rui, Sun Zhi-Wei

Bulletin of the Polish Academy of Sciences. Mathematics

|

2022

|

Vol. 70, no. 2

93--106

EN

In 2016 J. Koenigsmann refined a celebrated theorem of J. Robinson by proving that Q∖Z is diophantine over Q, i.e., there is a polynomial P(t,x1,…,xn)∈Z[t,x1,…,xn] such that for any rational number t we have t/∈Z⟺∃x1⋯∃xn [P(t,x1,…,xn)=0], where variables range over Q, equivalently t∈Z⟺∀x1⋯∀xn [P(t,x1,…,xn)/=0]. In this paper we prove that we may take n=32. Combining this with a result of Z.-W. Sun, we show that there is no algorithm to decide for any f(x1,…,x41)∈Z[x1,…,x41] whether ∀x1⋯∀x9∃y1⋯∃y32 [f(x1,…,x9,y1,…,y32)=0], where variables range over Q.

2

Precise Sets in Approximation Spaces and Textures

Dost Ş.

Fundamenta Informaticae

|

2018

|

Vol. 158, nr 4

353--368

EN

In this paper, we propose the notion of precise sets in texture spaces. Precise sets are defined by using textural sections and presections under a direlation. We obtain some properties of definability; it is proved that the family of precise sets under reflexive and transitive direlation is an Alexandroff ditopology. It is observed that sections and presections, which are approximation operators in the textural meaning, are Galois connections. Finally, effective results are given for definability by using textural precise sets.

3

Neighborhood Systems : Rough Set Approximations and Definability

Syau Y.-R., Lin E.-B., Liau C.-J.

Fundamenta Informaticae

|

2018

|

Vol. 159, nr 4

429--450

EN

The notions of approximation and definability in classical rough set theory and their generalizations have received much attention. In this paper, we study such generalizations from the perspective of neighborhood systems. We introduce four different types of definability, called interior definability, closure definability, interior-closure (IC) definability, and weak IC definability respectively. We also point out the relationship between IC definability and other types of definability for some special kinds of neighborhood systems. Several examples are presented to illustrate the concepts introduced in this paper.

4

On exactness, definability and vagueness in partial approximation spaces

Ciucci D., Mihálydeák T., Csajbók Z. E.

Technical Sciences / University of Warmia and Mazury in Olsztyn

|

2015

|

nr 18(3)

203--212

EN

In this paper, lower/upper, boundary, and negative regions of set approximations, the fundamental concepts of classical rough set theory, have been considered as primitive ones. Assuming that they are independent of each other, a generalized framework for their investigations is outlined. Its main building blocks are base sets and definable sets. Lower/upper approximations, boundaries and negative sets are all considered as definable sets and their mutual interactions are studied. Lastly exact/rough sets are discussed. In generalized framework, four groups of formulae are defined for representing different variants of rough sets. They emphasize distinct features of roughness, and so it may be of highly importance which one is used in practical applications. Some possible choices appeared in authors’ publications are mentioned.

5

On ordered minimal structures

Jagiella G., Newelski L.

Reports on Mathematical Logic

|

2014

|

Vol. 49

35--46

EN

We investigate minimal first-order structures and consider interpretability and definability of orderings on them. We also prove the minimality of their canonical substructures.

6

Definability and Canonicity for Boolean Logic with a Binary Relation

Balbiani P., Tinchev T.

Fundamenta Informaticae

|

2014

|

Vol. 129, nr 4

301--327

EN

This paper studies the concepts of definability and canonicity in Boolean logic with a binary relation. Firstly, it provides formulas defining first-order or second-order conditions on frames. Secondly, it proves that all formulas corresponding to compatible first-order conditions on frames are canonical.

7

The Monadic Second-order Logic Evaluation Problem on Finite Colored Trees: a Database-theoretic Approach

Foustoucos E., Kalantzi L.

Fundamenta Informaticae

|

2009

|

Vol. 92, nr 3

193-231

EN

We model the monadic second-order logic (MSO) evaluation problem on finite colored trees in a purely database theoretic framework, based on the well-known MSO-automata connection: we reduce the problem to an acyclic conjunctive query evaluation problem on the one hand and to a monadic datalog evaluation problem on the other hand. This approach offers the possibility to solve the MSO problem using optimized evaluation methods for relational algebra expressions and for datalog programs (such as Yannakakis algorithm [27] and the rewriting method using resolutionbased filtering referred to as "magic sets" method in [3]): we use these methods for evaluating our queries and giving estimates of their complexity. This is the first time, to our knowledge, that a solution to the MSO evaluation problem related to relational algebra is given; furthermore, thanks to this reduction, we prove that the automata-based algorithm given in [8] constitutes a particular "instance" of Yannakakis algorithm. Besides the optimized database methods that we propose for solving the MSO evaluation problem, our results prove that MSO-definable queries over colored trees are datalog-definable; this result subsumes the corresponding result in [12] which states that unary MSO queries are monadic datalog-definable and it also subsumes the well-known result that any MSO-definable class of trees is monadic datalog-definable.

8

Rough Sets and Infomorphisms: Towards Approximation of Relations in Distributed Environments

Skowron A., Stepaniuk J., Peters J.F.

Fundamenta Informaticae

|

2003

|

Vol. 54, nr 2,3

263-277

EN

We discuss the relationships between information systems and classifications as well as between infomorphisms and definability of relations (between whole objects and their parts) in information systems. Infomorphisms between information systems (classifications) IS1 and IS2 make it possible to define some formulas over IS2 by means of formulas over IS1. The remaining formulas over IS2 can be approximatively defined by means of formulas over IS1. The approximation operations are defined using the rough set approach. We present definitions and examples of such approximations.

9

Definability and Compression

Afrati F., Leiß H., Rougemont M. de

Fundamenta Informaticae

|

2003

|

Vol. 56, nr 1,2

155-180

EN

A compression algorithm takes a finite structure of a class K as input and produces a finite structure of a different class K' as output. Given a property P on the class K defined in a logic L, we study the definability of property P on the class K'. We consider two compression schemes on unary ordered structures (strings), compression by run-length encoding and the classical Lempel-Ziv-78 scheme. First-order properties of strings are first-order on run-length compressed strings, but this fails for images, i.e. 2-dimensional strings. We present simple first-order properties of strings which are not first-order definable on strings compressed with the Lempel-Ziv-78 compression scheme. We show that all properties of strings that are first-order definable on strings are definable on Lempel-Ziv compressed strings in FO(TC), the extension of first-order logic with the transitive closure operator. We define a subclass F of the first-order properties of strings such that if P is a property in F, it is also first-order definable on the Lempel-Ziv compressed strings. Monadic second-order properties of strings, i.e. regular languages, are dyadic second-order definable on Lempel-Ziv compressed strings.