Fundamenta Informaticae - Volume 118, issue 3

Authors: Başkent, Can

Article Type: Research Article

Abstract: In this paper, we introduce public announcement logic in different geometric frameworks. First, we consider topological models, and then extend our discussion to a more expressive model, namely, subset space models. Furthermore, we prove the completeness of public announcement logic in those frameworks. After that, we apply our results to different issues: announcement stabilization, backward induction and persistence.

Keywords: Public Announcement Logic, Topological Semantics, Subset Space Logic, Backward Induction

DOI: 10.3233/FI-2012-710

Citation: Fundamenta Informaticae, vol. 118, no. 3, pp. 207-223, 2012

Authors: Blazewicz, Jacek | Kasprzak, Marta

Article Type: Research Article

Abstract: The results presented in the paper are threefold. Firstly, a new class of reduced-by-matching directed graphs is defined and its properties studied. The graphs are output from the algorithm which, for a given 1-graph, removes arcs which are unnecessary from the point of view of searching for a Hamiltonian circuit. In the best case, the graph is reduced to a quasi-adjoint graph, what results in polynomial-time solution of the Hamiltonian circuit problem. Secondly, the systematization of several classes of digraphs, known from the literature and referring to directed line graphs, is provided together with the proof of its correctness. Finally, …computational experiments are presented in order to verify the effectiveness of the reduction algorithm. Show more

Keywords: Hamiltonian circuit problem, directed line graphs, quasi-adjoint graphs, graph reduction, digraphs

DOI: 10.3233/FI-2012-711

Citation: Fundamenta Informaticae, vol. 118, no. 3, pp. 225-244, 2012

Authors: Bortolussi, Luca | Dinu, Liviu P. | Sgarro, Andrea

Article Type: Research Article

Abstract: Spearman distance is a permutation distance which might be used for codes in permutations beside Kendall distance. However, Spearman distance gives rise to a geometry of strings, which is rather unruly from the point of view of error correction and error detection. Special care has to be taken to discriminate between the two notions of codeword distance and codeword distinguishability. This stresses the importance of rejuvenating the latter notion, extending it from Shannon's zero-error information theory to the more general setting of metric string distances.

Keywords: Shannon theory, codeword distinguishability, Spearman footrule distance, rank distance

DOI: 10.3233/FI-2012-712

Citation: Fundamenta Informaticae, vol. 118, no. 3, pp. 245-252, 2012

Authors: Grzecza, Marcin | Kasjan, Stanisław | Mróz, Andrzej

Article Type: Research Article

Abstract: Inspired by the bimodule matrix problem technique and various classification problems in poset representation theory, finite groups and algebras, we study the action of Belitskii algorithm on a class of square n by n block matrices M with coefficients in a field K. One of the main aims is to reduce M to its special canonical form M∞ with respect to the conjugation by elementary transformations defined by a class of matrices chosen in a subalgebra of the full matrix algebra $\mathbb{M}_n$(K). The algorithm can be successfully applied in the study of indecomposable linear representations of finite posets by …a computer search using numeric and symbolic computation. We mainly study the case when the di-graph (quiver) associated to the output matrix M∞ of the algorithm is a disjoint union of trees. We show that exceptional representations of any finite poset are determined by tree matrices. This generalizes a theorem of C.M. Ringel proved for linear representations of di-graphs. Show more

DOI: 10.3233/FI-2012-713

Citation: Fundamenta Informaticae, vol. 118, no. 3, pp. 253-279, 2012

Authors: Liao, Xin | Wen, Qiao-yan | Zhao, Ze-li | Zhang, Jie

Article Type: Research Article

Abstract: To improve the stego-image quality and provide a larger embedding capacity, a novel steganographic method based on four-pixel differencing and modulus function is presented. We process a block of four neighboring pixels, and form three two-pixel groups to record the information of secret data. In each group, the difference value between two pixels is exploited to estimate how many secret bits will be embedded. Two pixels will be adjusted so that the sum of the remainders of them is equal to secret data. In order to extract the secret data exactly, four pixel values in a block are adjusted synchronously …by using modulus function. An optimization problem is formulated to minimize the embedding distortion. A theoretical proof is given to ensure the solvability of the problem. The experimental results show the proposed method not only has a larger embedding capacity but also provides better stego-image quality. Show more

Keywords: Steganography, Pixel-value differencing, Four-pixel differencing, Modulus function

DOI: 10.3233/FI-2012-714

Citation: Fundamenta Informaticae, vol. 118, no. 3, pp. 281-289, 2012

Authors: Wang, Lidong | Ren, Yan | Liu, Xiaodong

Article Type: Research Article

Abstract: Near sets result from a generalization of rough sets, which introduced by Peters in 2006, and later formally defined in 2007. Near set theory provides a new framework for representation of objects characterized by the features that describe them. AFS (Axiomatic Fuzzy Set) theory was proposed by Liu (1998), which is a semantic methodology relating to the fuzzy theory. In this paper, a new version of near sets based on AFS theory is established, in which every object has an AFS fuzzy description with definitely semantics. The proposed approach to assessing the nearness (closeness) of objects is not defined directly …using a distance metric, but depend on similarity of their fuzzy descriptions. It is also a natural linguistic description that is similar to humans perception. Moreover, an approach to set approximation based on the union of families of objects with similar fuzzy descriptions is given. The near sets based on AFS theory can be viewed as a new development of near sets within the fuzzy context. Show more

Keywords: Near sets, AFS logic, fuzzy description, approximation space

DOI: 10.3233/FI-2012-715

Citation: Fundamenta Informaticae, vol. 118, no. 3, pp. 291-304, 2012

Authors: Widuch, Jacek

Article Type: Research Article

Abstract: This paper proposes a label correcting algorithm for solving the bus routing problem (BRP). The goal of the BRP is finding a route from the start stop to the final stop minimizing the time and the cost of travel. Additionally the time of starting travel at the start stop is given. The problem belongs to the group of multicriteria optimization problems (MOP), whose the solution is a set of non-dominated solutions. The algorithm makes possible to find all routes which belong to the set of non-dominated solutions. Apart from that the results of experimental tests are presented.

Keywords: bus routing problem, multicriteria optimization, relation of dominance, set of non-dominated solutions, bicriterion shortest path problem, directed weighted graph, variable weights, shortest path, label correcting algorithm

DOI: 10.3233/FI-2012-716

Citation: Fundamenta Informaticae, vol. 118, no. 3, pp. 305-326, 2012