Volume 21, 2002, No. 3

Fuzzy Turing machines revised

J. WIEDERMANN   Abstract Fuzzy Turing machines and fuzzy languages were introduced by Zadeh, Lee and Santos in nineteen seventies. Unfortunately, it appears that from computability point of view their model is too powerful --- its nondeterministic version accepts non--recursively enumerable fuzzy languages. Moreover, from the viewpoint of the modern fuzzy logic theory the model is too restrictive since it is defined only for a specific $t$-norm (G\"odel norm). Therefore we propose a generalization of the original model that is based on rigorous mathematical fundamentals of fuzzy logic. Its acceptance criterion is modified so that the resulting model obeys the Church--Turing Thesis.

 

The reconstruction of polyominoes from approximately orthogonal projections

M. GEBALA   Abstract The reconstruction of discrete two-dimensional pictures from their projections is one of the central problems in the areas of medical diagnostics, computer-aided tomography, pattern recognition, image processing, and data compression. In this paper, we determine the computational complexity of the problem of reconstruction of polyominoes from their approximately orthogonal projections. We prove that it is NP-complete to reconstruct polyominoes, horizontal convex polyominoes and vertical convex polyominoes from their approximate orthogonal projections. Moreover we give the algorithm for the reconstruction of hv-convex polyominoes of time complexity $O(m^3n^3)$.

 

On the logical definability of topologically closed recognizable languages of infinite trees

D. JANIN, G. LENZI   Abstract In this paper, we prove that for any language $L$ of finitely branching finite and infinite trees, the following properties are equivalent: (1)~$L$~is definable by an existential MSO sentence which is bisimulation invariant over graphs, (2)~$L$~is definable by a FO-closed existential MSO sentence which is bisimulation invariant over graphs, (3)~$L$~is definable in the nu-level of the modal mu-calculus, (4)~$L$~is the projection of a locally testable tree language and is bisimulation closed, (5)~$L$~is closed in the prefix topology and recognizable by a modal finite tree automaton, (6)~$L$~is recognizable by a modal finite tree automaton of index zero. The equivalence between $(3)$, $(4)$, $(5)$ and $(6)$ is known for quite a long time, although maybe not in such a form, and can be considered as a classical result. The logical characterization of this class of languages given by $(1)$ (and $(2)$) is new. It is an extension of analogous results over finite structures such as words, trees and grids relating full existential MSO and definability by finite automata.

 

Hypermedia systems modelling framework

P. DOLOG, M. BIELIKOVÁ   Abstract Modelling is an important activity in the development of complex systems. Hypermedia modelling is a relatively new direction of research. Based on achieved results in software systems development, the recognition of importance of hypermedia modelling took relatively short time from the time of widespread adoption of hypermedia systems. However, the hypermedia modelling is not that mature as its software counterpart. The aim of this paper is to present a survey of hypermedia systems modelling along proposed five perspectives: hypermedia application perspective, development process perspective, aspect (static or dynamic) perspective, degree of formality, and notation perspective. First, a categorisation of hypermedia related models is proposed. According to this categorisation, the multidimensional modelling space is established. The space leads to a schema that is capable to support decisions about the reuse of methods and techniques for hypermedia systems modelling. Additionally, selected hypermedia modelling methods and techniques with their mutual dependencies are studied according to the proposed categorisation.

 

Automatic finding of good classifiers following a biologically inspired metaphor

F. FERNÁNDEZ, P. ISASI   Abstract The design of nearest neighbour classifiers can be seen as the partitioning of the whole domain in different regions that can be directly mapped to a~class. The definition of the limits of these regions is the goal of any nearest neighbour based algorithm. These limits can be described by the location and class of a reduced set of prototypes and the nearest neighbour rule. The nearest neighbour rule can be defined by any distance metric, while the set of prototypes is the matter of design. To compute this set of prototypes, most of the algorithms in the literature require some crucial parameters as the number of prototypes to use, and a smoothing parameter. In this work, an evolutionary approach based on Nearest Neighbour Classifiers (ENNC) is introduced where no parameters are involved, thus overcoming all the problems derived from the use of the above mentioned parameters. The algorithm follows a biological metaphor where each prototype is identified with an animal, and the regions of the prototypes with the territory of the animals. These animals evolve in a competitive environment with a limited set of resources, emerging a population of animals able to survive in the environment, i.e.~emerging a~right set of prototypes for the above classification objectives. The approach has been tested using different domains, showing successful results, both in the classification accuracy and the distribution and number of the prototypes achieved.

 

Efficient deadlock-free multidimensional interval routing in hypercube-like networks

R. KRÁLOVIČ et al.   Abstract We present deadlock-free packet/wormhole routing algorithms ba\-sed on multidimensional interval schemes for certain hypercube related multiprocessor interconnection networks and give their analysis in terms of the compactness (i.e.~the maximum number of intervals per link) and the buffer-size (i.e.~the ma\-xi\-mum number of buffers per node/link). The issue of a simultaneous reduction of the compactness and the buffer-size is fundamental, worth to investigate and of practical importance, since the interval routing and wormhole routing have been industrially realized in INMOS Transputer C104 Router chips. In this paper we give an evidence that for some well-known interconnection networks there are efficient deadlock-free multidimensional interval routing schemes (DFMIRS) despite of a provable non-existence of efficient deterministic shortest path interval routing schemes (IRS). For $d$-dimensional hypercubes (tori) we present a $d$-dimensional DFMIRS of compactness $1$ and size $2$ (of compactness $1$ and size $4$), while for shortest path IRS we can achieve the reduction to $2$ (to at most $5$) buffers per node with compactness $2^{d-1}$ (with compactness $O(n^{d-1})$). For $d$-dimensional generalized butterflies we give a $d$-dimensional DFMIRS with compactness $2$ and size $3$, while each shortest path IRS is of the compactness at least superpolynomial in $d$. For $d$-dimensional cube-connected cycles we show a $d$-dimensional DFMIRS with compactness and size polynomial in $d$, while each shortest path IRS needs compactness at least $2^{d/2}$. We also present a nonconstant lower bound (in the form $\sqrt{d}$) on the size of deadlock-free packet routing (based on acyclic orientation covering) for a set of monotone routing paths on $d$-dimensional hypercubes.

 

Volume 21, 2002, No. 3