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