Fundamenta Informaticae - Volume 81, issue 1-3

Article Type: Other

Citation: Fundamenta Informaticae, vol. 81, no. 1-3, pp. i-iv, 2007

Authors: Krajewski, Stanisław | Woleński, Jan

Article Type: Research Article

Citation: Fundamenta Informaticae, vol. 81, no. 1-3, pp. 1-17, 2007

Authors: Arnold, André | Niwiński, Damian

Article Type: Research Article

Abstract: We show that a family of tree languages W_{(l,k)} , previously used by J. Bradfield, and by the first author to show the strictness of the Rabin¨CMostowski index hierarchy of alternating tree automata, forms a hierarchy w.r.t. theWadge reducibility. That is, W_{(l,k) ⩽_W W_{(l',k')} if and only if the index (l', k') is above (l, k). This is one of the few separation results known so far, concerning the …topological complexity of non-deterministically recognizable tree languages, and one of the few results about finite-state recognizable non-Borel sets of trees. Show more

Keywords: Wadge reducibility, infinite trees, automata, Rabin-Mostowski index

Citation: Fundamenta Informaticae, vol. 81, no. 1-3, pp. 19-28, 2007

Authors: Balbiani, Philippe | Tinchev, Tinko | Vakarelov, Dimiter

Article Type: Research Article

Abstract: We dedicate this paper to Professor Andrzej Grzegorczyk. His paper "Axiomatization of geometry without points" [20] is one of the first contributions to the region-based theory of space.

Keywords: Modal logic of space, region-based theory of space, contact relations, discrete models of space, continuous models of space

Citation: Fundamenta Informaticae, vol. 81, no. 1-3, pp. 29-82, 2007

Authors: Cégielski, Patrick | Richard, Denis | Vsemirnov, Maxim

Article Type: Research Article

Abstract: The undecidability of the additive theory of prime numbers (with identity) as well as the theory Th(N, +, n ↦ p_n ), where pn denotes the (n + 1)-th prime, are open questions. In a first part, we show the undecidability of Th(N, +, n ↦ nf(n)) where f is a good approximation of the enumeration n ↦ p_n /n. In a second part, as a possible approach, we extend the former theory by adding some …extra function. In this direction we show the undecidability of the existential part of the theory Th(N, +, n ↦ p_n , n ↦ r_n ), where r_n is the remainder of pn divided by n in the euclidian division. L'indécidabilité de la théorie additive des nombres premiers ainsi que de la théorie Th(N, +, n ↦ p_n ), où p_n désigne le (n+1)-ième premier, sont deux questions ouvertes. Dans une première partie, nous montrons l'indécidabilité de Th(N, +, n ↦ nf(n)) où f est une bonne approximation de la fonction n ↦ p_n /n des nombres premiers. Dans une seconde partie, nous étendons la première théorie en lui ajoutant une fonction supplémentaire et nous montrons l'indécidabilité de la théorie Th(N, +, n ↦ p_n , n ↦ r_n ), où r_n désigne le reste de p_n dans la division euclidienne de p_n par n, et même de sa seule partie existentielle. Show more

Citation: Fundamenta Informaticae, vol. 81, no. 1-3, pp. 83-96, 2007

Authors: Czelakowski, Janusz

Article Type: Research Article

Citation: Fundamenta Informaticae, vol. 81, no. 1-3, pp. 97-122, 2007

Authors: Gottwald, Siegfried

Article Type: Research Article

Abstract: The paper discusses some core topics which present open problems in the field of mathematical fuzzy logic and in the foundations of fuzzy set theory. It may reasonably be assumed that these problems shall have great influence for the future development of fuzzy logic within the next decade.

Citation: Fundamenta Informaticae, vol. 81, no. 1-3, pp. 123-137, 2007

Authors: Gruszczyński, Rafał | Pietruszczak, Andrzej

Article Type: Research Article

Abstract: We present basic notions of Pier's system of geometry in an intuitive way and from a heuristic point of view, trying to focus on the "essence" of Italian mathematician's constructions. However, it is done without the detriment for formal precision of the presentation, we hope. We also point to some important metamathematical dependencies between Pieri's and Hilbert's approach to Euclidean geometry.

Keywords: Pieri's structures, Metamathematics of Euclidean geometry

Citation: Fundamenta Informaticae, vol. 81, no. 1-3, pp. 139-154, 2007

Authors: Hájek, Petr

Article Type: Research Article

Abstract: A weak variant of Robinson's arithmetic Q where the binary operations of addition and multiplication are replaced by ternary relations (not necessarily defining total crisp functions) is formulated and investigated over the mathematical fuzzy logic BL∀. Essential undecidability of this fuzzy arithmetic is proved by a careful analysis of the classical proof of essential undecidability of arithmetic.

Citation: Fundamenta Informaticae, vol. 81, no. 1-3, pp. 155-163, 2007

Authors: Kossak, Roman

Article Type: Research Article

Citation: Fundamenta Informaticae, vol. 81, no. 1-3, pp. 165-172, 2007

Authors: Krajewski, Stanisław

Article Type: Research Article

Abstract: The so called Lucas argument, and more recently that put forward by Penrose, attempt to use Gödel's incompleteness theorems to demonstrate the non-mechanical nature of the mind, or in other words, that mind is not computational. Generalizing and strengthening the criticism of those arguments that have been made by mathematical logicians, it is proved that all possible variants of the argument must lead to a vicious circle or to inconsistency or to unsoundness (acceptance of a …false statement). This defeats Lucas, who assumes his consistency and Penrose, who assumes his soundness. As Gödel has remarked, the existence of a robot, whom we will call Luke, equivalent to the humanmind as far as mathematical capacities go, is not excluded by his incompleteness theorem. Show more

Citation: Fundamenta Informaticae, vol. 81, no. 1-3, pp. 173-181, 2007

Authors: Krynicki, Michał | Mostowski, Marcin | Zdanowski, Konrad

Article Type: Research Article

Abstract: The paper presents the current state of knowledge in the field of logical investigations of finite arithmetics. This is an attempt to summarize the ideas and results in this area. Some new results are presented – these are mainly generalizations of the earlier results related to properties of sl-theories and some nontrivial cases of FM-representability theorem.

Keywords: finite models, arithmetic, finite arithmetic, interpretations, complete sets, FM-representability, truth definitions

Citation: Fundamenta Informaticae, vol. 81, no. 1-3, pp. 183-202, 2007

Authors: Maksimova, Larisa

Article Type: Research Article

Abstract: In 1964-68 Andrzej Grzegorczyk investigated relational and topological semantics for the intuitionistic logic [15]–[18] . In this connection, following to McKinsey and Tarski, he also considered a semantics for modal logics. It is well known that there is a translation of the intuitionistic logic into the modal S4 logic. This translation was suggested by Gödel in order to find an interpretation of the intuitionistic logic via provability operator. A. Grzegorczyk found a modal formula G …valid in all partially ordered frames with descending chain condition but not in all topological spaces. It follows that this formula is not valid in S4 but one can translate the intuitionistic logic into the calculus arising from S4 by adding Grzegorczyk's formula as a new axiom schema. The resulting logic was called the Grzegorczyk logic in later papers and books on modal logic. There are a lot of investigations devoted to the Grzegorczyk logic. In this paper we give a short overview of results on the Grzegorczyk logic and its extensions. Show more

Citation: Fundamenta Informaticae, vol. 81, no. 1-3, pp. 203-210, 2007

Authors: Marek, Victor W. | Remmel, Jeffrey B.

Article Type: Research Article

Abstract: Logic programming with stable logic semantics (SLP) is a logical formalism that assigns to programs, i.e. sets of clauses where we allow both atoms and their negations in the body of clause, a special class of models of the program, called stable models. We show that stable logic semantics does not satisfy the natural analogue of the compactness theorem. However, we show that there are a variety of conditions which will ensure that a program satisfies …the analogue of the compactness theorem. Show more

Citation: Fundamenta Informaticae, vol. 81, no. 1-3, pp. 211-239, 2007

Authors: Mostowski, Marcin

Article Type: Research Article

Abstract: In this paper we consider a "mathematical" proof of the Church Thesis. The proof is based on very weak assumptions about intuitive computability and the FM-representability theorem from [11]. It develops and improves the argument mentioned in [12]. Our argument essentially depends on the mathematical model of the world we are in.

Citation: Fundamenta Informaticae, vol. 81, no. 1-3, pp. 241-248, 2007

Authors: Murawski, Roman

Article Type: Research Article

Citation: Fundamenta Informaticae, vol. 81, no. 1-3, pp. 249-256, 2007

Authors: Romanowska, Anna B. | Smith, Jonathan D.H. | Orłowska, Ewa

Article Type: Research Article

Abstract: This paper presents a new approach to the study of (real) barycentric algebras, in particular convex subsets of real affine spaces. Barycentric algebras are cast in the setting of two-sorted algebras. The real unit interval indexing the set of basic operations of a barycentric algebra is replaced by an LΠ-algebra, the algebra of Łukasiewicz Product Logic. This allows one to define barycentric algebras abstractly, independently of the choice of the unit real interval. It reveals an …unexpected connection between barycentric algebras and (fuzzy) logic. The new class of abstract barycentric algebras incorporates barycentric algebras over any linearly ordered field, the B-sets of G. M. Bergman, and E. G. Manes' if-then-else algebras over Boolean algebras. Show more

Keywords: affine space, barycentric algebra, mode, cancellative mode, LΠ-algebra, Łukasiewicz Product Logic, heterogeneous algebra, B-set, if-then-else algebra, rectangular algebra

Citation: Fundamenta Informaticae, vol. 81, no. 1-3, pp. 257-273, 2007

Authors: Orłowska, Ewa | Rewitzky, Ingrid

Article Type: Research Article

Abstract: Discrete dualities are presented for Heyting algebras with various modal operators, for Heyting algebras with an external negation, for symmetric Heyting algebras, and for Heyting-Brouwer algebras.

Keywords: Discrete duality, Heyting algebra, modal operator, negation, symmetric Heyting algebra, Heyting-Brouwer algebra

Citation: Fundamenta Informaticae, vol. 81, no. 1-3, pp. 275-295, 2007

Authors: Rybakov, Vladimir V.

Article Type: Research Article

Abstract: This paper aims to prove that the linear temporal logic LTL^{u,s}_{n,n-1} (N), which is an extension of the standard linear temporal logic LTL by operations Since and Previous (LTL itself, as standard, uses only Until and Next) and is based on the frame of all natural numbers N, as generating Kripke/Hintikka structure, is decidable w.r.t. admissible consecutions (inference rules). We find an algorithm recognizing consecutions admissible in LTL^{u,s}_{n,n-1} (N). As a …consequence this algorithm solves satisfiability problem and shows that LTL^{u,s}_{n,n-1} (N) itself is decidable, despite LTL^{u,s}_{n,n-1} (N) does not have the finite model property. Show more

Keywords: decidability, algorithms, inference rules, temporal logic, linear temporal logic, admissible inference rules

Citation: Fundamenta Informaticae, vol. 81, no. 1-3, pp. 297-313, 2007

Authors: Salwicki, Andrzej

Article Type: Research Article

Abstract: The paper of Andrzej Grzegorczyk [19] on hierachy of the primitive recursive classes dates for 1953. This is the most frequently cited article of Polish author in computer science literature, having some hundreds citations. Moreover, many citations are in the papers of eminent computer scientists e.g. [10,24,33,34,31], sometimes the laureates of prestigious awards. In this paper we make an attempt to present Andrzej Grzegorczyk as a computer scientist.

Citation: Fundamenta Informaticae, vol. 81, no. 1-3, pp. 315-323, 2007

Authors: Srebrny, Marian | St�pień, Lidia

Article Type: Research Article

Abstract: In this paper we present an application of the propositional SATisfiability environment to computing bases of some vector spaces. As a motivation we refer to certain computational tasks in the area of the algebraic theory of quadratic forms; more precisely, in the theory of Witt rings of quadratic forms. As known in algebra, the problem of finding all automorphisms of an elementary Witt ring can be reduced to searching for some special kind of bases of …certain vector space over the two-element Galois field. We show how one can code a search for some kind of bases as a propositional formula in such a way that its satisfying valuations code the desired bases. Some encouraging experimental results are reported for the proposed propositional search procedure using the currently best SAT solvers. Show more

Citation: Fundamenta Informaticae, vol. 81, no. 1-3, pp. 325-345, 2007

Authors: Švejdar, Vítězslav

Article Type: Research Article

Abstract: Q^- is a weaker variant of Robinson arithmetic Q in which addition and multiplication are partial functions, i.e. ternary relations that are graphs of possibly non-total functions. We show that Q is interpretable in Q^- . This gives an alternative answer to a question of A. Grzegorczyk whether Q^- is essentially undecidable.

Citation: Fundamenta Informaticae, vol. 81, no. 1-3, pp. 347-354, 2007

Authors: Woleński, Jan

Article Type: Research Article

Citation: Fundamenta Informaticae, vol. 81, no. 1-3, pp. 355-365, 2007