PL
 |
EN
Preferencje help
Polish version English version Język
Widoczny [Schowaj] Abstrakt
Liczba wyników

Znaleziono wyników: 8

Liczba wyników na stronie
first rewind previous Strona / 1 next fast forward last
Wyniki wyszukiwania
Wyszukiwano:
w słowach kluczowych:  completeness theorem
help Sortuj według:

help Ogranicz wyniki do:
first rewind previous Strona / 1 next fast forward last
1
Content available remote Neighbourhood and Lattice Models of Second-Order Intuitionistic Propositional Logic
Kurata Toshihiko, Fujita Ken-etsu
Fundamenta Informaticae
|
2019
|
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
Content available remote Truth in the limit
Mostowski M.
Reports on Mathematical Logic
|
2016
|
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.
3
Content available remote 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.
4
Content available remote Variants of Small Universal P Systems with Catalysts
Alhazov A., Freund R.
Fundamenta Informaticae
|
2015
|
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
Content available remote Length P Systems
Alhazov A., Freund R., Ivanov S.
Fundamenta Informaticae
|
2014
|
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.
6
Content available remote Reasoning about resources and information : a linear logic approach
Kamide N., Kaneiwa K.
Fundamenta Informaticae
|
2013
|
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.
7
Content available remote On Completeness and Decidability of Phase Space Invertible Asynchronous Cellular Automata
Wacker S., Worsch T.
Fundamenta Informaticae
|
2013
|
Vol. 126, nr 2-3
157--181
EN
While for synchronous deterministic cellular automata there is an accepted definition of reversibility, this is not the case for asynchronous cellular automata. We first discuss a few possibilities and then investigate what we call phase space invertible asynchronous cellular automata. We will show that for each Turing machine there is a phase space invertible purely asynchronous cellular automaton simulating it and that it is decidable whether an arbitrary-dimensional purely and a one-dimensional fully asynchronous cellular automaton is phase space invertible.
8
Content available remote Natural Deduction System for Some Three-valued Propositional Logic
Zbrzezny A.
Scientific Issues of Jan Długosz University in Częstochowa. Mathematics
|
1999
|
Vol. 6
148--152
first rewind previous Strona / 1 next fast forward last
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.