Fundamenta Informaticae - Volume 146, issue 2

Authors: Mróz, Andrzej

Article Type: Research Article

Abstract: We study edge-bipartite graphs (bigraphs), a class of signed graphs, by means of the inflation algorithm which relies on performing certain elementary transformations on a given bigraph Δ, or equivalently, on the associated integral quadratic form q Δ : ℤn → ℤ, preserving Gram ℤ-congruence. The ideas are inspired by classical results of Ovsienko and recent studies of Simson started in [SIAM J. Discr. Math . 27 (2013), 827-854], concerning classifications of integral quadratic and bilinear forms, and their Coxeter spectral analysis. We provide few modifications of the inflation algorithm and new estimations of its complexity for …positive and principal loop-free bigraphs. We discuss in a systematic way the behavior and computational aspects of inflation techniques. As one of the consequences we obtain relatively simple proofs of several interesting properties of quadratic forms and their roots, extending known facts. On the other hand, the results are a first step of a solution of a variant of Grothendieck group recognition, a difficult combinatorial problem arising in representation theory of finite dimensional algebras and their derived categories, which we discuss in Part II of this two parts article with the same main title. Show more

DOI: 10.3233/FI-2016-1377

Citation: Fundamenta Informaticae, vol. 146, no. 2, pp. 121-144, 2016

Authors: Mróz, Andrzej

Article Type: Research Article

Abstract: In this two parts article with the same main title we study a problem of Coxeter-Gram spectral analysis of edge-bipartite graphs (bigraphs), a class of signed graphs. We ask for a criterion deciding if a given bigraph Δ is weakly or strongly Gram-congruent with a graph. The problem is inspired by recent works of Simson et al. started in [SIAM J. Discr. Math . 27 (2013), 827-854], and by problems related to integral quadratic forms, bilinear lattices, representation theory of algebras, algebraic methods in graph theory and the isotropy groups of bigraphs. In this Part II we develop general combinatorial …techniques, with the use of inflation algorithm discussed in Part I, morsifications and the isotropy group of a bigraph, and we provide a constructive solution of the problem for the class of all positive connected loop-free bigraphs. Moreover, we present an application of our results to Grothendieck group recognition problem: deciding if a given bilinear lattice is the Grothendieck group of some category. Our techniques are tested in a series of experiments for so-called Nakayama bigraphs, illustrating the applications in practice and certain related phenomena. The results show that a computer algebra technique and discrete mathematical computing provide important tools in solving theoretical problems of high complexity. Show more

DOI: 10.3233/FI-2016-1378

Citation: Fundamenta Informaticae, vol. 146, no. 2, pp. 145-177, 2016

Authors: Dulio, Paolo | Frosini, Andrea | Rozenberg, Grzegorz

Article Type: Other

DOI: 10.3233/FI-2016-1379

Citation: Fundamenta Informaticae, vol. 146, no. 2, pp. 179-183, 2016

Authors: Brunetti, Sara | Peri, Carla

Article Type: Research Article

Abstract: In this paper we consider the uniqueness issues in Discrete Tomography. A special class of geometric objects, widely considered in the literature, is represented by additive sets. These sets are uniquely determined by their X -rays, and they are also reconstructible in polynomial time by use of linear programming. Recently, additivity has been extended to J-additivity to provide a more general treatment of known concepts and results. A further generalization of additivity, called bounded additivity is obtained by restricting to sets contained in a given orthogonal box. In this work, we investigate these two generalizations from a …geometrical point of view and analyze the interplay between them. Show more

Keywords: Additive set, weakly bad configuration, uniqueness problem, X-ray

DOI: 10.3233/FI-2016-1380

Citation: Fundamenta Informaticae, vol. 146, no. 2, pp. 185-195, 2016

Authors: Gambini, Ian | Vuillon, Laurent

Article Type: Research Article

Abstract: We investigate minimal polycubes in terms of volume that tile the ℝ3 space like the Fedorov’s polyhedra. In fact the 5 Fedorov’s polyhedra are convex polyhedra that tile the space by translation and we construct geometrical discrete objects formed by union of cubes with the same number of faces than the Fedorov’s polyhedra.

Keywords: Tilings of ℝ3, polycubes, tilings by translation, Fedorov’s polyhedra, lattice periodic tilings

DOI: 10.3233/FI-2016-1381

Citation: Fundamenta Informaticae, vol. 146, no. 2, pp. 197-209, 2016

Authors: Smaglichenko, Tatyana A. | Bjarnason, Ingi Th. | Smaglichenko, Alexander V. | Jacoby, Wolfgang R.

Article Type: Research Article

Abstract: The changes in the state of a geophysical medium before a strong earthquake can be found by studying of 3D seismic velocity images constructed for consecutive time windows. A preliminary step is to see changes with time in a minimum 1D model. In this paper we develop a method that finds the parameters of the minimum linear gradient model by applying a two-dimensional Taylor series of the observed data for the seismic ray and by performing least-square minimization for all seismic rays. This allows us to obtain the mean value of the discrete observed variable, close to zero value.

Keywords: local earthquake tomography, minimum 1D model, linear gradient of velocity

DOI: 10.3233/FI-2016-1382

Citation: Fundamenta Informaticae, vol. 146, no. 2, pp. 211-217, 2016

Authors: Viganò, Nicola | Batenburg, Kees Joost | Ludwig, Wolfgang

Article Type: Research Article

Abstract: Diffraction contrast tomography (DCT) is an X-ray full-field imaging technique that allows for the non-destructive three-dimensional investigation of polycrystalline materials and the determination of the physical and morphological properties of their crystallographic domains, called grains. This task is considered more and more challenging with the increasing intra-granular deformation, also known as orientation-spread. The recent introduction of a six-dimensional reconstruction framework in DCT (6D-DCT) has proven to be able to address the intra-granular crystal orientation for moderately deformed materials. The approach used in 6D-DCT, which is an extended sampling of the six-dimensional combined position-orientation space, has a linear scaling between …the number of sampled orientations, which determine the orientation-space resolution of the problem, and computer memory usage. As a result, the reconstruction of more deformed materials is limited by their high resource requirements from a memory and computational point of view, which can easily become too demanding for the currently available computer technologies. In this article we propose a super-sampling method for the orientation-space representation of the six-dimensional DCT framework that enables the reconstruction of more deformed cases by reducing the impact on system memory, at the expense of longer reconstruction times. The use of super-sampling can further improve the quality and accuracy of the reconstructions, especially in cases where memory restrictions force us to adapt to inadequate (undersampled) orientation-space sampling. Show more

DOI: 10.3233/FI-2016-1383

Citation: Fundamenta Informaticae, vol. 146, no. 2, pp. 219-230, 2016