International Journal of Foundations of Computer Science

Wave simulation is an important problem in engineering. Wave simulation models play significant roles in environmental protection. Wave simulations have thus far been done mostly serially. In order to meet the demand for increased spatial and temporal resolution and uncertainty analysis in environmental models for ecological assessments and water resource managements, it is essential to develop high-performance hydrodynamics and water quality models using parallel techniques. In this paper, algorithms for parallelizing 1-D wave simulation models are proposed. In particular, we introduce a paradigm called Less Talk for reducing communication costs in parallel computing. Our wave models have been implemented using Parallel Virtual Machine (PVM) and Multithreading. The experiments show that these algorithms that employ Less Talk are efficient and the parallel wave simulation models have excellent speedup performances.

In a recent paper, Altenbernd, Thomas and Wöhrle have considered acceptance of languages of infinite two-dimensional words (infinite pictures) by finite tiling systems, with the usual acceptance conditions, such as the Büchi and Muller ones, firstly used for infinite words. The authors asked for comparing the tiling system acceptance with an acceptance of pictures row by row using an automaton model over ordinal words of length ω². We give in this paper a solution to this problem, showing that all languages of infinite pictures which are accepted row by row by Büchi or Choueka automata reading words of length ω² are Büchi recognized by a finite tiling system, but the converse is not true. We give also the answer to two other questions which were raised by Altenbernd, Thomas and Wöhrle, showing that it is undecidable whether a Büchi recognizable language of infinite pictures is E-recognizable (respectively, A-recognizable).

In this paper we introduce a fuzzy version of symport/antiport membrane systems. Our fuzzy membrane systems handle possibly inexact copies of reactives and their rules are endowed with threshold functions that determine whether a rule can be applied or not to a given set of objects, depending of the degree of accuracy of these objects to the reactives specified in the rule. We prove that these fuzzy membrane systems generate exactly the recursively enumerable finite-valued fuzzy subsets of ℕ.

We extend the classic work of R.J. Parikh on context-free languages with operators min and max on unary alphabet. The new theory is called CAN (Compositional Algebra of Numbers) and can be used to model software processes that can be concatenated, concurrently executed, and recursively invoked. We propose and analyze an algorithm which constructs the execution time sets of a CAN in semilinear form. Finally, we consider several interesting variations of CAN whose execution time sets can be constructed with algorithms.

The subtree transfer (STT) distance is one of the distance metric for comparing phylogenies. Previous work on computing the STT distance considered degree-3 trees only. In this paper, we give an approximation algorithm for the STT distance for degree-d trees with arbitrary d and with generalized STT operations. Also, some NP-hardness results related to STT distance are presented.