Fundamenta Informaticae - Volume 68, issue 1-2

Authors: Boryczka, Mariusz

Article Type: Research Article

Abstract: Ant Colony Programming is a relatively new paradigm based on Genetic Programming and Ant Colony System. We discuss the problemof eliminating introns in Ant Colony Programming. The approach is tested on several approximation problems. The test results demonstrate that the proposed method simplifies significantly the achieved solutions and shortens their evaluation time.

Keywords: automatic programming, approximation problems, Ant Colony System, Ant Colony Programming, introns

Citation: Fundamenta Informaticae, vol. 68, no. 1-2, pp. 1-19, 2005

Authors: Burrieza, Alfredo | Ojeda-Aciego, Manuel

Article Type: Research Article

Abstract: Non-classical logics have proven to be an adequate framework to formalize knowledge representation. In this paper we focus on a multimodal approach to formalize order-of-magnitude qualitative reasoning, extending the recently introduced system MQ, by means of a certain notion of negligibility relation which satisfies a number of intuitively plausible properties, as well as a minimal axiom system allowing for interaction among the different qualitative relations. The main aim is to show the completeness of the formal …system introduced. Moreover, we consider some definability results and discuss possible directions for further research. Show more

Keywords: multimodal logics, non-classical logics, order-of-magnitude qualitative reasoning

Citation: Fundamenta Informaticae, vol. 68, no. 1-2, pp. 21-46, 2005

Authors: Eberbach, Eugene

Article Type: Research Article

Abstract: This paper presents a novel model for resource bounded computation based on process algebras. Such model is called the $-calculus (cost calculus). Resource bounded computation attempts to find the best answer possible given operational constraints. The $-calculus provides a uniform representation for optimization in the presence of limited resources. It uses cost-optimization to find the best quality solutions while using a minimal amount of resources. A unique aspect of the approach is to propose a resource bounded …process algebra as a generic problem solving paradigm targeting interactive AI applications. The goal of the $-calculus is to propose a computational model with built-in performance measure as its central element. This measure allows not only the expression of solutions, but also provides the means to incrementally construct solutions for computationally hard, real-life problems. This is a dramatic contrast with other models like Turing machines, λ-calculus, or conventional process algebras. This highly expressive model must therefore be able to express approximate solutions. This paper describes the syntax and operational cost semantics of the calculus. A standard cost function has been defined for strongly and weakly congruent cost expressions. Example optimization problems are given which take into account the incomplete knowledge and the amount of resources used by an agent. The contributions of the paper are twofold: firstly, some necessary conditions for achieving global optimization by performing local optimization in time and/or space are found. That deals with incomplete information and complexity during problem solving. Secondly, developing an algebra which expresses current practices, e.g., neural nets, cellular automata, dynamic programming, evolutionary computation, or mobile robotics as limiting cases, provides a tool for exploring the theoretical underpinnings of these methods. As the result, hybrid methods can be naturally expressed and developed using the algebra. Show more

Keywords: resource bounded computation, process algebra, problem solving, search, complete-ness, optimization, total optimization

Citation: Fundamenta Informaticae, vol. 68, no. 1-2, pp. 47-102, 2005

Authors: Fecher, Harald | Majster-Cederbaum, Mila

Article Type: Research Article

Abstract: In process algebras that allow for some form of disruption, it is important to state when a process terminates. One option is to include a termination action √. Another approach is that the 'final' executed action of a process terminates the process. The semantics of the former approach has been investigated in the literature in detail, e.g. by providing consistent true-concurrency and operational descriptions. The 'final' executed action termination approach, which is more adequate for modelling, …still lacks the existence of a detailed true concurrent description. In order to give a true concurrency model of such a termination view, we introduce a new class of event structures. This type of event structures models disabling by indicating sets of precursor events. We show that the introduced class of event structures has more expressive power with respect to event traces than the common event structures. We also give a classification of the expressive power in terms of sets of event traces. A consistency result of an operational and a denotational semantics is shown. Show more

Keywords: event structures, disruption, termination, expressive power, process algebra

Citation: Fundamenta Informaticae, vol. 68, no. 1-2, pp. 103-130, 2005

Authors: Stehr, Mark-Oliver

Article Type: Research Article

Abstract: The open calculus of constructions integrates key features of Martin-Löf's type theory, the calculus of constructions, membership equational logic, and rewriting logic into a single uniform language. The two key ingredients are dependent function types and conditional rewriting modulo equational theories. We explore the open calculus of constructions as a uniform framework for programming, specification and interactive verification in an equational higher-order style. By having equational logic and rewriting logic as executable …sublogics we preserve the advantages of a first-order semantic and logical framework and we provide a foundation for a broad spectrum of applications ranging from what could be called executable mathematics, involving symbolic computations and logical proofs, to software and system engineering applications, involving symbolic execution and analysis of nondeterministic and concurrent systems. Show more

Keywords: Equational Specification, Rewriting Logic, Type Theory

Citation: Fundamenta Informaticae, vol. 68, no. 1-2, pp. 131-174, 2005

Authors: Winkowski, Józef

Article Type: Research Article

Abstract: The paper is concerned with modelling distributed systems by specifying their states and processes. Processes are defined as activities in a universe of objects, each object with a set of possible internal states, each activity changing states of some objects and establishing or destroying relations among objects. Partial operations of composing processes sequenially and in parallel are defined. It is shown that certain sets of processes form together with these operations categories with additional structures and …special properties, that processes of a system can be represented as morphisms of such categories, and that independence of processes can be characterized in a natural, purely algebraic way. Show more

Keywords: Distributed systems, states, processes, structures, sequential composition, parallel composition, category, independence

Citation: Fundamenta Informaticae, vol. 68, no. 1-2, pp. 175-206, 2005