Fundamenta Informaticae - Volume 36, issue 4

Authors: Burago, Dmitri | de Rougemont, Michel

Article Type: Research Article

Abstract: We introduce classes of narrow graphs (including grid strips of fixed width), for which the graph reliability problem admits a polynomial time algorithm. Using this algorithm, we show that graph reliability is computable in polynomial time for the average complexity with respect to a Gaussian distribution. The latter is defined as follows: the vertices are numbered by integers {1,2, ...n}, and the probability that an edge between i and j is present is e−|i−j|2 .

Keywords: graph reliability, average complexity

DOI: 10.3233/FI-1998-3641

Citation: Fundamenta Informaticae, vol. 36, no. 4, pp. 307-315, 1998

Authors: Czech, Zbigniew J. | Mikanik, Wojciech

Article Type: Research Article

Abstract: The parallel random access machine (PRAM) is the most commonly used general-purpose machine model for describing parallel computations. Unfortunately the PRAM model is not physically realizable, since on large machines a parallel shared memory access can only be accomplished at the cost of a significant time delay. A number of PRAM simulation algorithms are known. The algorithms allow execution of PRAM programs on more realistic parallel machines. We study the randomized simulation of an exclusive read, exclusive write (EREW) PRAM on a module parallel computer (MPC). The simulation is based on utilizing universal hashing. The optimally efficient simulation involving parallel …slackness is also investigated. The results of our experiments performed on the MPC built upon IMS T9000 transputers throw some light on the question whether using the PRAM model in parallel computations is practically viable given the present state of transputer technology. Show more

DOI: 10.3233/FI-1998-3642

Citation: Fundamenta Informaticae, vol. 36, no. 4, pp. 317-336, 1998

Authors: Ostravský, Jan

Article Type: Research Article

Abstract: Prelanguages and pregrammars introduced in [8] present a generalization of languages and pure grammars. Relation of domination and double domination may be easily transferred from languages to prelanguages. In the present paper submonoids of a commutative monoid are characterized by means of their relations of domination; subgroups of a commutative group are characterized by means of their relations of double domination. The submonoid generated by a subset of a commutative monoid is constructed using a suitable pregrammar.

Keywords: monoid, submonoid, pregrammar, prelanguage, relation of domination of a prelanguage, relation of double domination of a prelanguage

DOI: 10.3233/FI-1998-3643

Citation: Fundamenta Informaticae, vol. 36, no. 4, pp. 337-343, 1998

Authors: Skarbek, Władysław | Pietrowcew, Adam | Sikora, Radosław

Article Type: Research Article

Abstract: The results of theoretical analysis for stochastic convergence of the modified Oja-RLS learning rule are presented. The rule is used to find Karhunen Loeve Transform. Based on this algorithm, an image compression scheme is developed by combining approximated 2D KLT transform and JPEG standard quantization and entropy coding stages. Though 2D KLT transform is of higher complexity than 2D DCT, the resulting PSNR quality of reconstructed images is better even by 2[dB].

Keywords: Image compression, JPEG standard, KLT transform, Principal Component Analysis, Oja neural algorithm

DOI: 10.3233/FI-1998-3644

Citation: Fundamenta Informaticae, vol. 36, no. 4, pp. 345-365, 1998

Authors: Vágvölgyi, Sándor

Article Type: Research Article

Abstract: A ground term equation system (gtes for short) E is simple if there is no gtes E′ equivalent to E consisting of less equations than E has. Moreover, a gtes E is minimal if for each equation e ∈ E, the congruence generated by E – {e} is a proper subset of the congruence generated by E. Given a reduced ground term rewriting system R, we describe all simple gtes' E and minimal gtes' F equivalent to R. We show that for a reduced ground term rewriting system R, it is decidable whether or not there exist infinitely many simple …(minimal) gtes' equivalent to R. Finally, we show that for a reduced ground term rewriting system R, and a gtes E, it is decidable if there is a simple gtes F equivalent to R such that E ⊆ F. Show more

Keywords: ground term equation system, reduced ground term rewrite system

DOI: 10.3233/FI-1998-3645

Citation: Fundamenta Informaticae, vol. 36, no. 4, pp. 367-413, 1998