| 1. |
- Doherty, Patrick, et al.
(författare)
-
Preface
- 2003
-
Ingår i: Fundamenta Informaticae. - : IOS Press. - 0169-2968 .- 1875-8681. ; 57:2-4, s. i-iii
-
Tidskriftsartikel (övrigt vetenskapligt/konstnärligt)
|
|
| 2. |
- Doherty, Patrick, 1957-, et al.
(författare)
-
The PMA and relativizing minimal change for action update
- 2000
-
Ingår i: Fundamenta Informaticae. - : IOS Press. - 0169-2968 .- 1875-8681. ; 44:1-2, s. 95-131
-
Tidskriftsartikel (refereegranskat)abstract
- Recently, a great deal of progress has been made using nonmonotonic temporal logics to formalize reasoning about action and change. In particular, much focus has been placed on the proper representation of non-deterministic actions and the indirect effects of actions. For the latter the use of causal or fluent dependency rule approaches has been dominant. Although much recent effort has also been spent applying the belief revision/update (BR/U) approach to the action and change domain, there has been less progress in dealing with nondeterministic update and indirect effects represented as integrity constraints. We demonstrate that much is to be gained by cross-fertilization between the two paradigms and we show this in the following manner. We first propose a generalization of the PMA, called the modified MPMA which uses intuitions from the TL paradigm to permit representation of nondeterministic update and the use of integrity constraints interpreted as causal or fluent dependency rules. We provide several syntactic characterizations of MPMA, one of which is in terms of a simple temporal logic and provide a representation theorem showing equivalence between the two. In constructing the MPMA, we discovered a syntactic anomaly which we call the redundant atom anomaly that many TL approaches suffer from. We provide a method for avoiding the problem which is equally applicable across paradigms. We also describe a syntactic characterization of MPMA in terms of Dijkstra semantics. We set up a framework for future generalization of the BR/U approach and conclude with a formal comparison of related approaches.
|
|
| 3. |
- Doherty, Patrick, et al.
(författare)
-
Towards a framework for approximate ontologies
- 2003
-
Ingår i: Fundamenta Informaticae. - : IOS Press. - 0169-2968 .- 1875-8681. ; 57:2-4, s. 147-165
-
Tidskriftsartikel (refereegranskat)abstract
- Currently, there is a great deal of interest in developing tools for the generation and use of ontologies on the WWW. These knowledge structures are considered essential to the success of the semantic web, the next phase in the evolution of the WWW. Much recent work with ontologies assumes that the concepts used as building blocks are crisp as opposed to approximate. It is a premise of this paper that approximate concepts and ontologies will become increasingly more important as the semantic web becomes a reality. We propose a framework for specifying, generating and using approximate ontologies. More specifically, (1) a formal framework for defining approximate concepts, ontologies and operations on approximate concepts and ontologies is presented. The framework is based on intuitions from rough set theory, (2) algorithms for automatically generating approximate ontologies from traditional crisp ontologies or from large data sets together with additional knowledge are presented. The knowledge will generally be related to similarity measurements between individual objects in the data sets, or constraints of a logical nature which rule out particular constellations of concepts and dependencies in generated ontologies. The techniques for generating approximate ontologies are parameterizable. The paper provides specific instantiations and examples.
|
|
| 4. |
- Madalinska-Bugaj, E, et al.
(författare)
-
Formalizing defeasible logic in CAKE
- 2003
-
Ingår i: Fundamenta Informaticae. - : IOS Press. - 0169-2968 .- 1875-8681. ; 57:2-3, s. 193-213
-
Tidskriftsartikel (refereegranskat)abstract
- Due to its efficiency, defeasible logic is one of the most interesting non-monotonic formalisms. Unfortunately, the logic has one major limitation: it does not properly deal with cyclic defeasible rules. In this paper, we provide a new variant of defeasible logic, using CAKE method. The resulting formalism is tractable and properly deals with circular defeasible rules.
|
|
| 5. |
- Vitoria, Aida, et al.
(författare)
-
From Rough Sets to Rough Knowledge Bases
- 2003
-
Ingår i: Fundamenta Informaticae. - 0169-2968 .- 1875-8681. ; 57:2-4, s. 215-246
-
Tidskriftsartikel (refereegranskat)abstract
- This paper presents an expressive language for representing knowledge about vague concepts. It is based on the rough set formalism and it caters for implicit definition of rough relations by combining different regions (e.g. upper approximation, lower approximation, boundary) of other rough relations. The semantics of the proposed language is obtained by translating it to the language of extended logic programs whose meaning is captured by paraconsistent stable models. A query language is also discussed to retrieve information about the defined rough relations. Motivating examples illustrating the use of the language are described.
|
|
| 6. |
|
|
| 7. |
- Jansson, Jesper, et al.
(författare)
-
A fast algorithm for optimal alignment between similar ordered trees
- 2003
-
Ingår i: Fundamenta Informaticae. - 0169-2968. ; 56:1-2, s. 105-120
-
Tidskriftsartikel (refereegranskat)abstract
- We present a fast algorithm for optimal alignment between two similar ordered trees with node labels. Let S and T be two such trees with S and T nodes, respectively. If there exists an optimal alignment between S and T which uses at most d blank symbols and d is known in advance, it can be constructed in O(n log n (.) (maxdeg)(3) (.) d(2)) time, where n = max{S, T} and maxdeg is the maximum degree of all nodes in S and T. If d is not known in advance, we can construct an optimal alignment in O(n log n (.) (maxdeg)(3 .) f(2)) time, where f is the difference between the highest possible score for any alignment between two trees having a total of S + T nodes and the score of an optimal alignment between S and T, if the scoring scheme satisfies some natural assumptions. In particular, if the degrees of both input trees are bounded by a constant, the running times reduce to o(n log n (.) d(2)) and O(n log n (.) f(2)), respectively.
|
|
| 8. |
- Karpinski, M, et al.
(författare)
-
Approximation algorithms for MAX-BISECTION on low degree regular graphs
- 2004
-
Ingår i: Fundamenta Informaticae. - 0169-2968. ; 62:3-4, s. 369-375
-
Tidskriftsartikel (refereegranskat)abstract
- The max-bisection problem is to find a partition of the vertices of a graph into two equal size subsets that maximizes the number of edges with endpoints in both subsets. We obtain new improved approximation ratios for the max-bisection problem on the low degree k-regular graphs for 3 less than or equal to k less than or equal to 8, by deriving some improved transformations from a maximum cut intofrom a maximum bisection. In the case of three regular graphs we obtain an approximation ratio of 0.854, and in the case of four and five regular graphs, approximation ratios of 0.805, and 0.812, respectively.
|
|
