Fundamenta Informaticae - Volume 34, issue 1-2

Authors: Ferrari, Gian Luigi | Montanari, Ugo

Article Type: Research Article

Abstract: A generalization of De Simone format, where labels of transitions are structured actions, is presented. This provides a parameterized SOS framework where several paradigms of the observational semantics of process calculi can be uniformly handled. Moreover, standard algebraic techniques provide the formal machineries to relate the different semantics. It is also shown that much of the meta results developed for standard SOS format extend to this parameterized context.

Keywords: Process Calculi, Structured Operational Semantics (SOS), SOS Formats, Bi-simulation Equivalence, Complete Axiomatizations, Interleaving and Truly Concurrent Semantics

DOI: 10.3233/FI-1998-341201

Citation: Fundamenta Informaticae, vol. 34, no. 1-2, pp. 1-31, 1998

Authors: Gomolińska, Anna

Article Type: Research Article

Abstract: Credibility of information is investigated for the purpose of modelling belief state and its change.

Keywords: credibility of information, belief change

DOI: 10.3233/FI-1998-341202

Citation: Fundamenta Informaticae, vol. 34, no. 1-2, pp. 33-51, 1998

Authors: van Linder, B. | van der Hoek, W. | Meyer, J.-J. Ch.

Article Type: Research Article

Abstract: We present a formal system to reason about and specify the behavior of multiple intelligent artificial agents. Essentially, each agent can perform certain actions, and it may possess a variety of information in order to reason about its and other agent's actions. Thus, our KARO-framework tries to deal formally with the notion of Knowledge, possessed by the agents, and their possible execution of actions. In particular, each agent may reason about its —or, alternatively, other's— Abilities to perform certain actions, the possible Results of such an execution and the availability of the Opportunities to take a particular action. Formally, we …combine dynamic and epistemic logic into one modal system, and add the notion of ability to it. We demonstrate that there are several options to define the ability to perform a sequentially composed action, and we outline several properties under two alternative choices. Also, the agents' views on the correctness and feasibility of their plans are highlighted. Finally, the complications in the completeness proof for both systems indicate that the presence of abilities in the logic makes the use of infinite proof rules useful, if not inevitable. Show more

DOI: 10.3233/FI-1998-341203

Citation: Fundamenta Informaticae, vol. 34, no. 1-2, pp. 53-101, 1998

Authors: La Torre, Salvatore | Napoli, Margherita | Parente, Domenico

Article Type: Research Article

Abstract: We are given a line of n identical processors (finite automata) that work synchronously. Each processor can transmit just one bit of information to the adjacent processors (if any) to the left and to the right. The computation starts at time 1 with the leftmost processor in an initial state and all other processors in a quiescent state. Given the time f(n), the problem is to set (synchronize) all the processors in a particular state for the first time, at the very same instant f(n). This problem is also known as the Firing Squad Synchronization Problem and was introduced by …Moore in 1964. Mazoyer has given a minimal time solution with the least number of different states (six) and very recently he has given a minimal time solution for the constrained problem in which adjacent processors can exchange only one bit. In this paper we present solutions that synchronize the line at a given time, expressed as a function of n. In particular we give solutions that synchronize at the times nlogn, n√n, n2 and 2n . Moreover we also show how to compose solutions in such a way to obtain synchronizing solutions for all times expressed by polynomials with nonnegative coefficients. Clearly all such solutions work also in the general case when the bit constraint is relaxed. Show more

Keywords: Cellular Automata, Synchronization

DOI: 10.3233/FI-1998-341204

Citation: Fundamenta Informaticae, vol. 34, no. 1-2, pp. 103-128, 1998

Authors: Nguyen, Sinh Hoa | Nguyen, Hung Son

Article Type: Research Article

Abstract: Searching for patterns is one of the main goals in data mining. Patterns have important applications in many KDD domains like rule extraction or classification. In this paper we present some methods of rule extraction by generalizing the existing approaches for the pattern problem. These methods, called partition of attribute values or grouping of attribute values, can be applied to decision tables with symbolic value attributes. If data tables contain symbolic and numeric attributes, some of the proposed methods can be used jointly with discretization methods. Moreover, these methods are applicable for incomplete data. The optimization problems for grouping of …attribute values are either NP-complete or NP-hard. Hence we propose some heuristics returning approximate solutions for such problems. Show more

DOI: 10.3233/FI-1998-341205

Citation: Fundamenta Informaticae, vol. 34, no. 1-2, pp. 129-144, 1998

Authors: Son, Nguyen Hung

Article Type: Research Article

Abstract: We present an optimal hyperplane searching method for decision tables using Genetic Algorithms. This method can be used to construct a decision tree for a given decision table. We also present some properties of the set of hyperplanes determined by our methods and evaluate an upper bound on the depth of the constructed decision tree.

Keywords: Boolean reasoning, discretization, oblique hyperplanes, decision tree

DOI: 10.3233/FI-1998-341206

Citation: Fundamenta Informaticae, vol. 34, no. 1-2, pp. 145-174, 1998

Authors: Vágvölgyi, Sandor

Article Type: Research Article

Abstract: We introduce the ground tree transducer game (gtt game) played by Alpha and Beta. We deduce from the possibility of embedding gtt games into abstract games that for any gtt game there is either a winning Alpha-strategy or a winning Beta-strategy. We present several examples for the game, and show that any abstract game can be simulated by some gtt game 𝒢, a set S1 of Alpha-strategies for 𝒢, and a set S2 of Beta-strategies for 𝒢. Among several decidability and undecidability results, we show the following. It is decidable, given gtt games 𝒢1 and 𝒢2 , …whether 𝒢1 and 𝒢2 are equivalent. There is no algorithm to determine, given a gtt game 𝒢 and an Alpha-strategy π, whether π is a winning Alpha-strategy. There is no algorithm to determine, given a recursive set S of gtt games, whether or not there exists a game 𝒢 ∈,; S such that Alpha has a winning strategy for 𝒢. Show more

Keywords: ground tree transducer, tree automaton, game

DOI: 10.3233/FI-1998-341207

Citation: Fundamenta Informaticae, vol. 34, no. 1-2, pp. 175-201, 1998