You are viewing a javascript disabled version of the site. Please enable Javascript for this site to function properly.
Go to headerGo to navigationGo to searchGo to contentsGo to footer
In content section. Select this link to jump to navigation

Fundamenta Informaticae - Volume 28, issue 1-2

Purchase individual online access for 1 year to this journal.

Price: EUR 410.00
ISSN 0169-2968 (P)
ISSN 1875-8681 (E)

Impact Factor 2024: 0.4

Fundamenta Informaticae is an international journal publishing original research results in all areas of theoretical computer science. Papers are encouraged contributing:


- solutions by mathematical methods of problems emerging in computer science
- solutions of mathematical problems inspired by computer science.

Topics of interest include (but are not restricted to): theory of computing, complexity theory, algorithms and data structures, computational aspects of combinatorics and graph theory, programming language theory, theoretical aspects of programming languages, computer-aided verification, computer science logic, database theory, logic programming, automated deduction, formal languages and automata theory, concurrency and distributed computing, cryptography and security, theoretical issues in artificial intelligence, machine learning, pattern recognition, algorithmic game theory, bioinformatics and computational biology, quantum computing, probabilistic methods, & algebraic and categorical methods.

results per page

Logic Programming from the Perspective of Algebraic Semantics

Authors: Plaza, Jan A.

Article Type: Research Article

Abstract: We present an approach to foundations of logic programming in which the connection with algebraic semantics becomes apparent. The approach is based on omega-Herbrand models instead of conventional Herbrand models. We give a proof of Clark's theorem on completeness of SLD-resolution by methods of the algebraic semantics. We prove the existence property for definite programs.

Keywords: Rasiowa-Sikorski lemma, algebraic semantics, logic programming, completeness of SLD-resolution

DOI: 10.3233/FI-1996-281210

Citation: Fundamenta Informaticae, vol. 28, no. 1-2, pp. 153-164, 1996

Get PDF

Satisfiability of Inequalities in a Poset

Authors: Pratt, Vaughan | Tiuryn, Jerzy

Article Type: Research Article

Abstract: We consider tractable and intractable cases of the satisfiability problem for conjunctions of inequalities between variables and constants in a fixed finite poset. We show that crowns are intractable. We study members and closure properties of the class of tractable posets. We define a feasible poset to be one whose potential obstacles to satisfiability are representable by a certain formula of the first-order extended by the least fixed operator. For bipartite posets we give a complete classification of hard posets and feasible ones.

DOI: 10.3233/FI-1996-281211

Citation: Fundamenta Informaticae, vol. 28, no. 1-2, pp. 165-182, 1996

Get PDF

On the Power of Compositional Proofs for Nets: Relationships Between Completeness and Modularity

Authors: Trakhtenbrot, B.A.

Article Type: Research Article

DOI: 10.3233/FI-1996-281212

Citation: Fundamenta Informaticae, vol. 28, no. 1-2, pp. 183-195, 1996

Get PDF

Positive Recursive Type Assignment

Authors: Urzyczyn, Paweł

Article Type: Research Article

Abstract: We consider several different definitions of type assignment with positive recursive types, from the point of view of their typing ability. We discuss the relationships between these systems. In particular, we show that the class of typable pure lambda terms remains the same for different type disciplines involving positive type fixpoints, and that type reconstruction is decidable.

Keywords: Lambda calculus, positive recursive types, type constraints

DOI: 10.3233/FI-1996-281213

Citation: Fundamenta Informaticae, vol. 28, no. 1-2, pp. 197-209, 1996

Get PDF
Show more