Fundamenta Informaticae - Volume 45, issue 4

Authors: Barrera, Junior | Hasimoto, Ronaldo Fumio

Article Type: Research Article

Abstract: It is well known that any W-operator can be represented as the supremum (respectively, infimum) of sup-generating and (respectively, inf-generating) operators, that is, the families of sup-generating and inf-generating operators constitute the building blocks for representing W-operators. Here, we present two new families of building blocks to represent W-operators: compositions of sup-generating operators with dilations and compositions of inf-generating operators with erosions. The representations based on these new families of operators are …called, respectively, sup-compact and inf-compact representations, since they may use less building blocks than the classical sup-generating and inf-generating representations. Considering the W-operators that are both anti-extensive and idempotent –in a strict sense–, we have also gotten a simplification of the sup-compact representation. We have also shown how the inf-compact representation can be simplified for any W-operator such that it is extensive and its dual operator is idempotent –in a strict sense–. Furthermore, if the W-operators are openings (respectively, closings), we have shown that this simplified sup-compact (respectively, inf-compact) representation reduces to a minimal realization of the classical Matheron's representations for translation invariant openings (respectively, closings). Show more

Keywords: Mathematical Morphology, W-Operators, Compact Representation, Openings and Closings

Citation: Fundamenta Informaticae, vol. 45, no. 4, pp. 283-294, 2001

Authors: Engelbrecht, Andries P.

Article Type: Research Article

Abstract: Research on improving the performance of feedforward neural networks has concentrated mostly on the optimal setting of initial weights and learning parameters, sophisticated optimization techniques, architecture optimization, and adaptive activation functions. An alternative approach is presented in this paper where the neural network dynamically selects training patterns from a candidate training set during training, using the network's current attained knowledge about the target concept. Sensitivity analysis of the neural network output with …respect to small input perturbations is used to quantify the informativeness of candidate patterns. Only the most informative patterns, which are those patterns closest to decision boundaries, are selected for training. Experimental results show a significant reduction in the training set size, without negatively influencing generalization performance and convergence characteristics. This approach to selective learning is then compared to an alternative where informativeness is measured as the magnitude in prediction error. Show more

Keywords: Sensitivity Analysis, Dynamic Pattern Selection, Decision Boundaries, Pattern Informativeness, Feedforward Neural Networks

Citation: Fundamenta Informaticae, vol. 45, no. 4, pp. 295-328, 2001

Authors: Fernau, Henning | Stiebe, Ralf

Article Type: Research Article

Abstract: We investigate four variants of valence regulations incorporated in (limited) Lindenmayer systems, focussing on hierarchical relations and closure properties. Strong connections to well-known families of languages obtained by regulated rewriting are established. We prove several new results on valence transducers and valence generalized sequential machines (gsm). In this way, we can show new properties of ET0L languages, namely the non-closure under quasiintersection, valence gsm mappings and intersection with regular valence languages. Moreover, …we solve a question marked as open in [36] by proving that the uniformly k-limited ET0L languages form a full semi-AFL for all k≥1. Show more

Keywords: Formal languages, Lindenmayer systems, limited Lindenmayer systems, valence grammars

Citation: Fundamenta Informaticae, vol. 45, no. 4, pp. 329-358, 2001

Authors: Gruska, Damas P. | Maggiolo-Schettini, Andrea

Article Type: Research Article

Abstract: Critical issues that arise when process algebras are used for protocol specifications are discussed. To overcome some of these problems, a process algebra for protocol specifications is presented. It is based on Milner's Calculus of Communicating Systems, which is enriched by time and network reasoning. Several bisimulation based semantics for the calculus are defined and their properties are discussed.

Keywords: Concurrency, Specification, Process Algebras, Protocols

Citation: Fundamenta Informaticae, vol. 45, no. 4, pp. 359-378, 2001

Authors: Salibra, Antonino

Article Type: Research Article

Abstract: The variety (equational class) of lambda abstraction algebras was introduced to algebraize the untyped lambda calculus in the same way cylindric and polyadic algebras algebraize the first-order predicate logic. In this paper we prove that the lattice of lambda theories is not modular and that the variety generated by the term algebra of a semi-sensible lambda theory is not congruence modular. Another result of the paper is that the Mal'cev condition for congruence modularity is inconsistent …with the lambda theory generated by equating all the unsolvable λ-terms. Show more

Keywords: Lambda calculus, lambda abstraction algebras, combinatory algebras, lattice of lambda theories, modularity, commutator

Citation: Fundamenta Informaticae, vol. 45, no. 4, pp. 379-392, 2001

Authors: Zhao, Xishun | Ding, Decheng

Article Type: Research Article

Abstract: This paper is concerned with the complexity of default reasoning with 2CNF default theories (D,W) in which W is a set of literals and D is a set of 2CNF defaults. It is proved that the problem whether a literal occurs in at least one extension can be solved in polynomial time. But the problem whether a literal appears in all extensions is proved to be co-NP-complete. The complexity of some subclasses of 2CNF default theories is also …analyzed. Show more

Keywords: 2CNF default theory, credulous reasoning, skeptical reasoning, complexity

Citation: Fundamenta Informaticae, vol. 45, no. 4, pp. 393-404, 2001