Wyniki wyszukiwania - Biblioteka Nauki

1

Neighbourhood and Lattice Models of Second-Order Intuitionistic Propositional Logic

100%

Kurata T. , Fujita K.-e.

|

2019

|

tom Vol. 170, nr 1-3

223--240

EN

We study a version of the Stone duality between the Alexandrov spaces and the completely distributive algebraic lattices. This enables us to present lattice-theoretical models of second-order intuitionistic propositional logic which correlates with the Kripke models introduced by Sobolev. This can be regarded as a second-order extension of the well-known correspondence between Heyting algebras and Kripke models in the semantics of intuitionistic propositional logic.

2

Length P Systems

88%

Alhazov A. , Freund R. , Ivanov S.

|

tom Vol. 134, nr 1/2

17--37

EN

In this paper, we examine P systems with a linear membrane structure, i.e., P systems in which only one membrane is elementary and the output of which is read out as the sequence of membrane labels in the halting configuration or vectors/numbers represented by this sequence. We investigate the computational power of such systems, depending on the number of membrane labels, kinds of rules used, and some other possible restrictions. We prove that two labels, elementary membrane creation and dissolution, together with the usual send-in and send-out rules, suffice to achieve computational completeness, even with the restriction that only one object is allowed to be present in any configuration of the system. On the other hand, limiting the number of labels to one reduces the computational power to the regular sets of non-negative integers. We also consider other possible variants of such P systems, e.g., P systems in which all membranes but one have the same label, P systems with membrane duplication rules, or systems in which multiple objects are allowed to be present in a configuration, and we describe the computational power of all these models.

3

Truth in the limit

88%

Mostowski M.

Reports on Mathematical Logic

|

2016

|

tom Vol. 51

75--89

EN

We consider sl–semantics in which first order sentences are interpreted in potentially infinite domains. A potentially infinite domain is a growing sequence of finite models. We prove the completeness theorem for first order logic under this semantics. Additionally we characterize the logic of such domains as having a learnable, but not recursive, set of axioms. The work is a part of author’s research devoted to computationally motivated foundations of mathematics.

4

Variants of Small Universal P Systems with Catalysts

88%

Alhazov A. , Freund R.

Fundamenta Informaticae

|

2015

|

tom Vol. 138, nr 1/2

227--250

EN

Computational completeness is known for P systems with two catalysts and purely catalytic P systems with three catalysts as well as for P systems with one bi-stable catalyst. We complete this picture by showing computational completeness for purely catalytic P systems with one bi-stable catalyst and one catalyst. Moreover, we present some concrete universal P systems, e.g., for P systems with one multi-stable catalyst and for P systems with multiple catalysts. Furthermore, we optimize the descriptional complexity of Minsky’s reduction from register machines with an arbitrary number of registers to register machines with only two registers. In that way, we are able to transformthe universalmachines U22 and U20 of Korec into weakly universal register machines with only two decrementable registers, one even with unencoded output. Based on these universal register machines, we then construct small universal P systems with one bi-stable catalyst and one catalyst as well as small universal purely catalytic P systems with three catalysts. With respect to the number of rules, the smallest universal P systems can be obtained with multi-stable catalysts and with multiple catalysts. The number of rules in all these systems can be further reduced by adding the concept of toxic objects (a specified subset of objects), where all computation branches not evolving all toxic objects in every computation step do not yield a result.

5

A propositional logic of temporal connectives

88%

Epstein R. L. , Buitrago-Díaz E.

Logic and Logical Philosophy

|

2015

|

tom 24

|

nr 2

155–200

EN

We investigate how to formalize reasoning that takes account of time by using connectives like “before” and “after.” We develop semantics for a formal logic, which we axiomatize. In proving that the axiomatization is strongly complete we show how a temporal ordering of propositions can yield a linear timeline. We formalize examples of ordinary language sentences to illustrate the scope and limitations of this method. We then discuss ways to deal with some of those limitations.

6

Natural Deduction System for Some Three-valued Propositional Logic

75%

Zbrzezny A.

Scientific Issues of Jan Długosz University in Częstochowa. Mathematics

|

1999

|

tom Vol. 6

148--152

7

Reasoning about resources and information : a linear logic approach

75%

Kamide N. , Kaneiwa K.

Fundamenta Informaticae

|

2013

|

tom Vol. 125, nr 1

51--70

EN

A logic called sequence-indexed linear logic (SLL) is proposed to appropriately formalize resource-sensitive reasoning with sequential information. The completeness and cut-elimination theorems for SLL are proved, and SLL and a fragment of SLL are shown to be undecidable and decidable, respectively. As an application of SLL, some specifications of secure password authentication systems are discussed.