Fundamenta Informaticae - Volume 166, issue 4

Authors: Lopez Pombo, Carlos G. | Castro, Pablo F. | Aguirre, Nazareno M. | Maibaum, Thomas S.E.

Article Type: Research Article

Abstract: The theory of institutions, introduced by Goguen and Burstall in 1984, can be thought of as an abstract formulation of model theory. This theory has been shown to be particularly useful in computer science, as a mathematical foundation for formal approaches to software construction. Institution theory was extended by a number of researchers, José Meseguer among them, who, in 1989, presented General Logics , wherein the model theoretical view of institutions is complemented by providing (categorical) structures supporting the proof theory of any given logic. In other words, Meseguer introduced the notion of proof calculus as a formalisation of syntactical …deduction, thus “implementing” the entailment relation of a given logic. In this paper we follow the approach initiated by Goguen and introduce the concept of Satisfiability Calculus . This concept can be regarded as the semantical counterpart of Meseguer’s notion of proof calculus, as it provides the formal foundations for those proof systems that resort to model construction techniques to prove or disprove a given formula, thus “implementing” the satisfiability relation of an institution. These kinds of semantic proof methods have gained a great amount of interest in computer science over the years, as they provide the basic means for many automated theorem proving techniques. Show more

Keywords: Institution Theory, Semantic Proof Systems, Formal Methods

DOI: 10.3233/FI-2019-1804

Citation: Fundamenta Informaticae, vol. 166, no. 4, pp. 297-347, 2019

Authors: Rauch, Jan | Šimůnek, Milan

Article Type: Research Article

Abstract: An approach to data mining with histograms is introduced. Several examples of applying data mining for various types of histogram are presented. The problem of filtering out uninteresting histograms is described. It is shown that no suitable, logically correct deduction rules to solve this problem exist. Expert deduction rules are introduced as deduction rules supported by indisputable facts, however, incorrect according to mathematical logic. A method for deciding whether a given expert deduction rule is correct according to a given indisputable fact is developed. Applied examples of correct expert deduction rules are described.

Keywords: histograms, logical calculus of histograms, expert deduction rules, GUHA procedure CF-Miner

DOI: 10.3233/FI-2019-1805

Citation: Fundamenta Informaticae, vol. 166, no. 4, pp. 349-378, 2019

Authors: Turacı, Tufan | Aytaç, Aysun

Article Type: Research Article

Abstract: Let G = (V (G ), E (G )) be a simple undirected graph. The domination and average lower domination numbers are vulnerability parameters of a graph. We have investigated a refinement that involves the residual domination and average lower residual domination numbers of these parameters. The lower residual domination number , denoted by γ v k R ( G ) , is the minimum cardinality of dominating set in G that received from the graph G where the vertex vk and all links of the vertex …vk are deleted. The residual domination number of graphs G is defined as γ R ( G ) = min v k ∈ V ( G ) { γ v k R ( G ) } . The average lower residual domination number of G is defined by γ a v R ( G ) = 1 | V ( G ) | ∑ v k ∈ V ( G ) γ V k R ( G ) . In this paper, we define the residual domination and the average lower residual domination numbers of a graph and we present the exact values, upper and lower bounds for some graph families. Show more

Keywords: Network Design and Communication, Graph vulnerability, Domination number, Residual domination number, Average lower residual domination number

DOI: 10.3233/FI-2019-1806

Citation: Fundamenta Informaticae, vol. 166, no. 4, pp. 379-392, 2019