Fundamenta Informaticae - Volume 119, issue 2

Authors: Bourguiba, Imen | Moa, Belaid

Article Type: Research Article

Abstract: Tabular expressions are one of the most important table-based techniques used to formally specify software requirements. The power of tabular expressions stems from their visual structure, and concise representation of mathematical functions and relations. Towards using tabular expressions as a programming language, we propose a tabular expression language in which tabular expressions are first class citizens. The language is built upon atomic tabular expressions and operators. As such, tabular expressions are viewed as a stack of atomic expressions and operators that we apply on them. This view enhances building tools supporting the semantics of tabular expressions, and using them directly …during the implementation. The tabular operators introduced are used to compose and decompose tabular expressions in a modular way, which improves their semantics. Show more

DOI: 10.3233/FI-2012-730

Citation: Fundamenta Informaticae, vol. 119, no. 2, pp. 121-147, 2012

Authors: Kosakowska, Justyna

Article Type: Research Article

Abstract: We describe combinatorial algorithms that compute the Dynkin type (resp. Euclidean type) of any positive (resp. principal) unit quadratic form q : $\mathbb{N}$n → $\mathbb{N}$ and of any positive (resp. principal) edge-bipartite connected graph Δ. The study of the problem is inspired by applications of the algorithms in the representation theory, in solving a class of Diophantine equations, in the study of mesh geometries of roots, in the spectral analysis of graphs, and in the Coxeter-Gram classification of edge-bipartite graphs.

Keywords: edge-bipartite graphs, Dynkin graphs, Euclidean graphs, quadratic forms, equivalence of quadratic forms, combinatorial algorithms

DOI: 10.3233/FI-2012-731

Citation: Fundamenta Informaticae, vol. 119, no. 2, pp. 149-162, 2012

Authors: Mrozek, Ireneusz | Yarmolik, Vyacheslav

Article Type: Research Article

Abstract: Antirandom testing has proved useful in a series of empricial evaluations. It improves the fault-detection capability of random testing by employing the location information of previously executed test cases. In antirandom testing we select test pattern (test vector) such that it is as different as possible from all the previous executed test cases. Unfortunately, this method essentially requires enumeration of the input space and computation of each input vector when used on an arbitrary set of existing test data. This avoids scale-up to large test sets and (or) long input vectors. In this paper, we propose a new algorithm for …antirandom test generation that is computationally feasible for BIST (Built In Self Test) tests. As the fitness function we use Maximal Minimal Hamming Distance (MMHD) rather than standard Hamming distance as is used in the classical approach. This allows to generate the most efficient test vectors in term of weighted number of generated k-bits tuples. Experimental results are given to evaluate the performance of the new approach. Show more

Keywords: Antirandom testing, Failure pattern, Random testing, Software testing, Hardware testing

DOI: 10.3233/FI-2012-732

Citation: Fundamenta Informaticae, vol. 119, no. 2, pp. 163-185, 2012

Authors: Tan, Henry | Hadzic, Fedja | Dillon, Tharam S.

Article Type: Research Article

Abstract: The increasing need for representing information through more complex structures where semantics and relationships among data objects can be more easily expressed has resulted in many semi-structured data sources. Structure comparison among semi-structured data objects can often reveal valuable information, and hence tree mining has gained a considerable amount of interest in areas such as XML mining, Bioinformatics, Web mining etc. We are primarily concerned with the task of mining frequent ordered induced and embedded subtrees from a database of rooted ordered labeled trees. Our previous contributions consist of the efficient Tree Model Guided (TMG) candidate enumeration approach for which …we developed a mathematical model that provides an estimate of the worst case complexity for embedded subtree mining. This potentially reveals computationally impractical situations where one would be forced to constrain the mining process in some way so that at least some patterns can be discovered. This motivated our strategy of tackling the complexity of mining embedded subtrees by introducing the Level of Embedding constraint. Thus, when it is too costly to mine all frequent embedded subtrees, one can decrease the level of embedding constraint gradually down to 1, from which all the obtained frequent subtrees are induced subtrees. In this paper we develop alternative implementations and propose two algorithms MB3-R and iMB3-R , which achieve better efficiency in terms of time and space. Furthermore, we develop a mathematical model for estimating the worst case complexity for induced subtree mining. It is accompanied with a theoretical analysis of induced-embedded subtree relationships in terms of complexity for frequent subtree mining. Using synthetic and real world data we practically demonstrate the space and time efficiency of our new approach and provide some comparisons to the two well know algorithms for mining induced and embedded subtrees. Show more

Keywords: Algorithms, Performance, Experimentation, Tree Mining, TreeMiner, FREQT, TMG, Tree Model Guided

DOI: 10.3233/FI-2012-733

Citation: Fundamenta Informaticae, vol. 119, no. 2, pp. 187-231, 2012