Fundamenta Informaticae - Volume 104, issue 4

Authors: Dapoigny, Richard | Barlatier, Patrick

Article Type: Research Article

Abstract: In the area of knowledge representation, a challenging topic is the formalization of context knowledge on the basis of logical foundations and ontological semantics. However, most attempts to provide a formal model of contexts suffer from a number of difficulties, such as limited expressiveness of representation, restricted variable quantification, lack of (meta) reasoning about properties, etc. In addition, type theory originally developed for formal modeling of mathematics has also been successfully applied to the correct specification of programs and in the semantics of natural language. In this paper, we suggest a type theoretical approach to the problem of context and …action modeling. Type theory is used both for representing the system's knowledge of the discourse domain and for reasoning about it. For that purpose, we extend an existing dependent type theory having nice properties, with context-based rules and appropriate inductive types. We claim that the resulting theory exploiting the power of dependent types is able to provide a very expressive system together with a unified theory allowing higher-order reasoning. Show more

Keywords: Context, Action, Type Theory, Dependent Types, Subtyping, Subsumption, Partonomies

DOI: 10.3233/FI-2010-351

Citation: Fundamenta Informaticae, vol. 104, no. 4, pp. 293-327, 2010

Authors: Jeż, Artur | Okhotin, Alexander

Article Type: Research Article

Abstract: It is shown that equations of the form �(X) = ψ(X), in which the unknown X is a set of natural numbers and �, ψ use the operations of union, intersection and addition of sets S + T = {m + n |, m ∈ S, n ∈ T}, can simulate systems of equations �j (X1 , …, Xn ) = �j (X1 , …, Xn ) with 1 ≤ j ≤ ℓ, in the sense that solutions of any such system are encoded in the solutions of the corresponding equation. This implies computational universality of least and greatest solutions …of equations �(X) = ψ(X), as well as undecidability of their basic decision problems. It is sufficient to use only singleton constants in the construction. All results equally apply to language equations over a one-letter alphabet Σ = {a}. Show more

Keywords: Language equations, unary alphabet, univariate equations

DOI: 10.3233/FI-2010-352

Citation: Fundamenta Informaticae, vol. 104, no. 4, pp. 329-348, 2010

Authors: Nguyen, Linh Anh

Article Type: Research Article

Abstract: Developing a good formalism and an efficient decision procedure for the instance checking problem is desirable for practical application of description logics. The data complexity of the instance checking problem is coNP-complete even for Horn knowledge bases in the basic description logic ALC. In this paper, we present and study weakenings with PTIME data complexity of the instance checking problem for Horn knowledge bases in regular description logics. We also study cases when the weakenings are an exact approximation. In contrast to previous related work of other authors, our approach deals with the case when the constructor ∀ is allowed …in premises of program clauses that are used as terminological axioms. Show more

Keywords: Horn knowledge bases, description logics, regular grammar logics

DOI: 10.3233/FI-2010-353

Citation: Fundamenta Informaticae, vol. 104, no. 4, pp. 349-384, 2010

Authors: Shao, Zuhua

Article Type: Research Article

Abstract: In 2006, Pomykala and Barabasz proposed an elliptic curve based threshold proxy signature scheme with known signers. They claimed that their scheme was relatively simple in construction, had the properties of unforgeability and non-repudiation, and admitted the proactive security. Later, Li and Hu pointed out that the scheme of Pomykala and Barabasz was insecure against the conspiracy attack. And then, they proposed an improved scheme. In this paper, we not only show that the threshold proxy signature scheme of Pomykala and Barabasz is universal forgeable, but also show that the improvement of Li and Hu suffers from the rogue key …attack. Show more

Keywords: elliptic curve cryptosystems, threshold proxy signature scheme, secret sharing, rogue key attack

DOI: 10.3233/FI-2010-354

Citation: Fundamenta Informaticae, vol. 104, no. 4, pp. 385-392, 2010