Fundamenta Informaticae - Volume 132, issue 4

Authors: Choffrut, Christian

Article Type: Research Article

Abstract: Eilenberg and al. introduced and studied in the late sixties the family of n-ary relations over the free monoid recognized by finite n-tape automata where the where the n reading heads tapes move simultaneously from left to right. We call these relations synchronous. In the eighties Angluin and Hoover and then Läuchli and Savioz introduced a proper subfamily which the first authors called regular prefix. Our main result shows that given a synchronous relation it is decidable whether or not it is regular prefix. Incidentally we also show that the family of regular prefix relations is uniformizable in the sense …that all such relations contain a partial function with the same domain whose graph is a regular prefix relation. Show more

DOI: 10.3233/FI-2014-1053

Citation: Fundamenta Informaticae, vol. 132, no. 4, pp. 439-459, 2014

Authors: Kan, Tomohiro | Higuchi, Shoichi | Hirata, Kouichi

Article Type: Research Article

Abstract: In this paper, as variations of a Tai mapping between rooted labeled ordered trees (trees, for short), we introduce a segmental mapping to preserve the parent-children relationship as possible, and also top-down segmengal and bottom-up segmental mappings as the segmental mappings that contain the pair of the roots and the pair of the leaves, respectively. Then, we show that these mappings provide a new hierarchy for the variations of the Tai mapping in addition to a well-known one, in particular, the top-down segmental mapping coincides with a top-down mapping. Also we show that both segmental and bottom-up segmental distances as …the minimum costs of segmental and bottom-up segmental mappings are metrics. Next, we design algorithms to compute the segmental and the bottom-up segmental distances in quadratic time and space. Finally, we give experimental results for the segmental distance. Show more

Keywords: tree edit distance, segmental distance, Tai mapping, rooted labeled ordered trees

DOI: 10.3233/FI-2014-1054

Citation: Fundamenta Informaticae, vol. 132, no. 4, pp. 461-483, 2014

Authors: Koczkodaj, Waldemar W. | Szwarc, Ryszard

Article Type: Research Article

Abstract: This study examines the notion of inconsistency in pairwise comparisons for providing an axiomatization for it. It also proposes two inconsistency indicators for pairwise comparisons. The primary motivation for the inconsistency reduction is expressed by a computer industry concept “garbage in, garbage out”. The quality of the output depends on the quality of the input.

Keywords: pairwise comparisons, inconsistency axiomatization

DOI: 10.3233/FI-2014-1055

Citation: Fundamenta Informaticae, vol. 132, no. 4, pp. 485-500, 2014

Authors: Liu, Jian-Guo | Zeng, Zhi-Fang

Article Type: Research Article

Abstract: In this paper, with the aid of the computerized symbolic computation, we present an extended generalized hyperbolic-function method. Being concise and straightforward, it can be applicable to seek more types of solutions for certain nonlinear evolution equations (NLEES). In illustration, we choose the generalized Hamiltonian equations and the (2 + 1)-dimensional Nizhnik-Novikov-Veselov (NNV) equations to demonstrate the validity and advantages of the method. As a result, abundant new exact solutions are obtained including soliton-like solutions, traveling wave solutions etc. The method can be also applied to other nonlinear partial differential equations (NPDEs).

Keywords: Symbolic computation, Nizhnik-Novikov-Veselov equations, Generalized hyperbolic-function method, Exact analytic solutions

DOI: 10.3233/FI-2014-1056

Citation: Fundamenta Informaticae, vol. 132, no. 4, pp. 501-517, 2014

Authors: Mróz, Andrzej | Zwara, Grzegorz

Article Type: Research Article

Abstract: We present combinatorial algorithms for solving three problems that appear in the study of the degeneration order ≤deg for the variety of finite-dimensional modules over a k-algebra Λ, where M ≤deg N means that a module N belongs to an orbit closure $\overline{\cal{O}(M)}$ of a module M in the variety of Λ-modules. In particular, we introduce algorithmic techniques for deciding whether or not the relation M ≤deg N holds and for determining all predecessors (resp. succesors) of a given module M with respect to ≤deg . The order ≤deg plays an important role in modern algebraic …geometry and module theory. Applications of our technique and experimental tests for particular classes of algebras are presented. The results show that a computer algebra technique and algorithmic computer calculations provide important tools in solving theoretical mathematics problems of high computational complexity. The algorithms are implemented and published as a part of an open source GAP package called QPA. Show more

DOI: 10.3233/FI-2014-1057

Citation: Fundamenta Informaticae, vol. 132, no. 4, pp. 519-532, 2014

Authors: Torres, Gabriela Martín

Article Type: Research Article

Abstract: In this paper we attempt to measure the accuracy of approximations of regular languages by languages in +−varieties (as defined by Eilenberg). These approximations are upper approximations in the sense of Pawlak’s rough set theory with respect to congruences belonging to the variety of congruences corresponding to the given +−variety. In our approach, the accuracy of an approximation is measured by the relative density of the object language in the approximation language and the asymptotic behavior of this quotient. In particular, we apply our measures of accuracy to k-definite, reverse k-definite, i, j-definite and k-testable approximations.

DOI: 10.3233/FI-2014-1058

Citation: Fundamenta Informaticae, vol. 132, no. 4, pp. 533-545, 2014

Article Type: Other

Citation: Fundamenta Informaticae, vol. 132, no. 4, pp. 547-548, 2014