Fundamenta Informaticae - Volume 39, issue 3

Authors: Düntsch, Ivo | Wang, Hui | McCloskey, Stephen

Article Type: Research Article

Abstract: The formalization of the “part – of” relationship goes back to the mereology of S. Leśniewski, subsequently taken up by Leonard & Goodman (1940), and Clarke (1981). In this paper we investigate relation algebras obtained from different notions of “part-of”, respectively, “connectedness” in various domains. We obtain minimal models for the relational part of mereology in a general setting, and when the underlying set is an atomless Boolean algebra.

DOI: 10.3233/FI-1999-39301

Citation: Fundamenta Informaticae, vol. 39, no. 3, pp. 229-248, 1999

Authors: Dudakov, Sergey M.

Article Type: Research Article

Abstract: In this paper we investigate computational complexity of the PERF-consistency and PERF-entailment problems for ground normal logic programs. In [3] it is proved that these problems belong to Σ2 P and II2 P correspondingly. The question of obtaining more accurate results was left as open. We prove that both problems belong to Δ2 P . Lower bounds on the complexity of these problems are also established in terms of a new complexity class D2 which is a subset of Δ2 P . It is shown that PERF-consistency is a D2 -complete problem and PERF-entailment is co-D2 -complete.

DOI: 10.3233/FI-1999-39302

Citation: Fundamenta Informaticae, vol. 39, no. 3, pp. 249-258, 1999

Authors: Heinemann, Bernhard

Article Type: Research Article

Abstract: In the present note we determine the complexity of the satisfiability problem of a certain modal logic of subset spaces which was proposed in [6]. The corresponding semantics is defined w.r.t. binary ramified subset trees consisting of a set X and a distinguished set 𝒪 of subsets of X such that the relation of reverse set inclusion makes 𝒪 a binary ramified tree. It turns out that the satisfiability problem of the logic is complete in NP.

Keywords: modal logic of subset spaces, binary ramified subset trees, satisfiability problem, complexity

DOI: 10.3233/FI-1999-39303

Citation: Fundamenta Informaticae, vol. 39, no. 3, pp. 259-272, 1999

Authors: Intrigila, B. | Inverardi, P. | Venturini Zilli, M.

Article Type: Research Article

Abstract: Terms finitely representing infinite sequences of finite first-order terms have received attention by several authors. In this paper, we consider the class of recurrent terms proposed by H. Chen and J. Hsiang, and we extend it to allow infinite terms. This extension helps in clarifying the relationships between matching and unification over the class of terms we consider, that we call iterative terms. In fact, it holds that if a term s matches a term t by a substitution Γ, then the limit of iterations of the matching Γ, if it exists, is a most general unifier of s and …t. A crucial feature of iterative terms is the notion of maximally-folded normal form that allows for a comprehensive treatment of both finite and infinite iterative terms. In this setting, infinite terms can be simply characterized as limits of sequences of finite terms. For finite terms we positively settle an open problem of H. Chen and J. Hsiang on the number of most general unifiers for a pair of terms. Show more

Keywords: Infinite sequences of terms, infinite terms, normal forms, matching, unification, most general unifiers

DOI: 10.3233/FI-1999-39304

Citation: Fundamenta Informaticae, vol. 39, no. 3, pp. 273-304, 1999

Authors: Knapik, Teodor | Calbrix, Hugues

Article Type: Research Article

Abstract: This paper introduces oriented Thue specifications and their models which are simple directed edge-labeled graphs. The monadic second-order theory of these models is investigated and shown decidable for the class of suffix-bounded rational oriented Thue specifications. In addition, a characterization of prefix-closed context-free languages is given in terms of oriented Thue specifications.

Keywords: string-rewriting, infinite graphs, automata, monadic second-order logic

DOI: 10.3233/FI-1999-39305

Citation: Fundamenta Informaticae, vol. 39, no. 3, pp. 305-325, 1999

Authors: Müller, Heike | Hilbrich, Torsten | Kühnel, Ralf

Article Type: Research Article

Abstract: The paper describes an application of agent oriented programming: an assistant program for everyday computer tasks like printing, converting, extracting etc. The assistant looks for services matching the users query, possibly delegates queries to other agents, loads new services over the net and offers its own services to other agents. We use Java as implementing language.

Keywords: Personal Assistant, Agent Oriented Techniques

DOI: 10.3233/FI-1999-39306

Citation: Fundamenta Informaticae, vol. 39, no. 3, pp. 327-336, 1999