Fundamenta Informaticae - Volume 124, issue 3

Authors: Kalyanasundaram, Bala | Velauthapillai, Mahe

Article Type: Research Article

Abstract: We consider the inductive inference model of Gold [15]. Suppose we are given a set of functions that are learnable with certain number of mind changes and errors. What can we consistently predict about those functions if we are allowed fewer mind changes or errors? In [20] we relaxed the notion of exact learning by considering some higher level properties of the input-output behavior of a given function. in this context, a learner produces a program that describes the property of a given function. Can we predict generic properties such as threshold or modality if we allow fewer number of …mind changes or errors? These questions were completely answered in [20] when the learner is restricted to a single IIM. In this paper we allow a team of IIMs to collaborate in the learning process. The learning is considered to be successful if any one of the team member succeeds. A motivation for this extension is to understand and characterize properties that are learnable for a given set of functions in a team environment. Show more

Keywords: Inductive Inference, properties of functions, mind changes, errors, learning, teams

DOI: 10.3233/FI-2013-833

Citation: Fundamenta Informaticae, vol. 124, no. 3, pp. 251-270, 2013

Authors: Ma, Hui | Noack, René | Schewe, Klaus-Dieter | Thalheim, Bernhard | Wang, Qing

Article Type: Research Article

Abstract: A schema algebra comprises operations on database schemata for a given data model. Such algebras are useful in database design as well as in schema integration. In this article we address the necessary theoretical underpinnings by introducing a novel notion of conceptual schema morphism that captures at the same time the conceptual schema and its semantics by means of the set of valid instances. This leads to a category of schemata that is finitely complete and co-complete. This is the basis for a notion of completeness of schema algebras, if it captures all universal constructions in the category of schemata. …We exemplify this notion of completeness for a recently introduced particular schema algebra. Show more

Keywords: database design, schema category, completeness, schema algebra

DOI: 10.3233/FI-2013-834

Citation: Fundamenta Informaticae, vol. 124, no. 3, pp. 271-295, 2013

Authors: Odabaş, Zeynep Nihan | Aytaç, Aysun

Article Type: Research Article

Abstract: Networks are known to be prone to node or link failures. A central issue in the analysis of networks is the assessment of their stability and reliability. The main aim is to understand, predict, and possibly even control the behavior of a networked system under attacks or disfunctions of any type. A central concept that is used to assess stability and robustness of the performance of a network under failures is that of vulnerability. A network is usually represented by an undirected simple graph where vertices represent processors and edges represent links between processors. Different approaches to properly define a …measure for graph vulnerability has been proposed so far. In this paper, we study the vulnerability of cycles and related graphs to the failure of individual vertices, using a measure called residual closeness which provides a more sensitive characterization of the graph than some other well-known vulnerability measures. Show more

Keywords: Graph vulnerability, Closeness, Network design and communication, Stability, Communication network, Cycles

DOI: 10.3233/FI-2013-835

Citation: Fundamenta Informaticae, vol. 124, no. 3, pp. 297-307, 2013

Authors: Simson, Daniel

Article Type: Research Article

Abstract: Following the spectral Coxeter analysis of matrix morsifications for Dynkin diagrams, the spectral graph theory, a graph coloring technique, and algebraic methods in graph theory, we continue our study of the category 𝒰ℬigrn of loop-free edge-bipartite (signed) graphs Δ, with n ≥ 2 vertices, by means of the Coxeter number cΔ , the Coxeter spectrum speccΔ of Δ, that is, the spectrum of the Coxeter polynomial coxΔ (t) ∈ $\mathbb{Z}$[t] and the $\mathbb{Z}$-bilinear Gram form bΔ : $\mathbb{Z}$n × $\mathbb{Z}$n → $\mathbb{Z}$ of Δ [SIAM J. Discrete Math. 27(2013)]. Our main inspiration for the study …comes from the representation theory of posets, groups and algebras, Lie theory, and Diophantine geometry problems. We show that the Coxeter spectral classification of connected edge-bipartite graphs Δ in 𝒰ℬigrn reduces to the Coxeter spectral classification of rational matrix morsifications A ∈ $\widehat{M}$orDΔ for a simply-laced Dynkin diagram DΔ associated with Δ. Given Δ in 𝒰ℬigrn , we study the isotropy subgroup Gl(n,$\mathbb{Z}$)Δ of Gl(n, $\mathbb{Z}$) that contains the Weyl group $\mathbb{W}$Δ and acts on the set $\widehat{M}$orΔ of rational matrix morsifications A of Δ in such a way that the map A $\mapsto$ (speccA , det A, cΔ ) is Gl(n, $\mathbb{Z}$)Δ -invariant. It is shown that, for n ≤ 6, speccΔ is the spectrum of one of the Coxeter polynomials listed in Tables 3.11-3.11(a) (we determine them by computer search using symbolic and numeric computation). The question, if two connected positive edge-bipartite graphs Δ,Δ′ in 𝒰ℬigrn , with speccΔ = speccΔ′ , are $\mathbb{Z}$-bilinear equivalent, is studied in the paper. The problem if any $\mathbb{Z}$-invertible matrix A ∈ Mn ($\mathbb{Z}$) is $\mathbb{Z}$-congruent with its transpose Atr is also discussed. Show more

Keywords: edge-bipartite graph, toroidal mesh algorithm, inflation algorithm, matrix morsification, Dynkin diagram, Coxeter spectrum, Weyl group, Euler bilinear form, mesh geometry of root orbits, toroidal mesh algorithm, sand-glass tube

DOI: 10.3233/FI-2013-836

Citation: Fundamenta Informaticae, vol. 124, no. 3, pp. 309-338, 2013

Authors: Simson, Daniel

Article Type: Research Article

Abstract: By applying symbolic and numerical computation and the spectral Coxeter analysis technique of matrix morsifications introduced in our previous paper [Fund. Inform. 124(2013)], we present a complete algorithmic classification of the rational morsifications and their mesh geometries of root orbits for the Dynkin diagram $\mathbb{D}_4$. The structure of the isotropy group $Gl(4, \mathbb{Z})_{\mathbb{D}_4}$ of $\mathbb{D}_4$ is also studied. As a byproduct of our technique we show that, given a connected loop-free positive edge-bipartite graph Δ, with n ≥ 4 vertices (in the sense of our paper [SIAM J. Discrete Math. 27(2013)]) and the positive definite Gram unit form $q_\Delta : …\mathbb{Z}^n \rightarrow \mathbb{Z}$, any positive integer d ≥ 1 can be presented as d = qΔ (v), with $v \in \mathbb{Z}^n$. In case n = 3, a positive integer d ≥ 1 can be presented as d = qΔ (v), with $v \in \mathbb{Z}^n$, if and only if d is not of the form 4a (16 · b + 14), where a and b are non-negative integers. Show more

Keywords: edge-bipartite graph, toroidal mesh algorithm, inflation algorithm, matrix morsification, Dynkin diagram, Coxeter spectrum, Weyl group, Euler bilinear form, mesh geometry of root orbits

DOI: 10.3233/FI-2013-837

Citation: Fundamenta Informaticae, vol. 124, no. 3, pp. 339-364, 2013