Fundamenta Informaticae - Volume 123, issue 2

Authors: Mousavi, Hamoon | Shallit, Jeffrey

Article Type: Research Article

Abstract: A filtration of a formal language L by a sequence s maps L to the set of words formed by taking the letters of words of L indexed only by s. We consider the languages resulting from filtering by all arithmetic progressions. If L is regular, it is easy to see that only finitely many distinct languages result; we give bounds on the number of distinct languages in terms of the state complexity of L. By contrast, there exist CFL's that give infinitely many distinct languages as a result. We use our technique to show that two related operations, including …diag (which extracts the diagonal of words of square length arranged in a square array), preserve regularity but do not preserve context-freeness. Show more

Keywords: filtration, arithmetic progression, formal language, regular language, finite automaton, state complexity, context-free language, diagonal, regularity-preserving transformation

DOI: 10.3233/FI-2013-804

Citation: Fundamenta Informaticae, vol. 123, no. 2, pp. 135-142, 2013

Authors: Sikora, Marek | Gudyś, Adam

Article Type: Research Article

Abstract: In the paper we present CHIRA, an algorithm performing decision rules aggregation. New elementary conditions, which are linear combinations of attributes may appear in rule premises during the aggregation, leading to so-called oblique rules. The algorithm merges rules iteratively, in pairs, according to a certain order specified in advance. It applies the procedure of determining convex hulls for regions in a feature space which are covered by aggregated rules. CHIRA can be treated as the generalization of rule shortening and joining algorithms which, unlike them, allows a rule representation language to be changed. Application of presented algorithm allows one to …decrease a number of rules, especially in the case of data in which decision classes are separated by hyperplanes not perpendicular to the attribute axes. Efficiency of CHIRA has been verified on rules obtained by two known rule induction algorithms, RIPPER and q-ModLEM, run on 18 benchmark data sets. Additionally, the algorithm has been applied on synthetic data as well as on a real-life set concerning classification of natural hazards in hard-coal mines. Show more

Keywords: decision rules, rule aggregation, oblique rules, convex hull

DOI: 10.3233/FI-2013-805

Citation: Fundamenta Informaticae, vol. 123, no. 2, pp. 143-170, 2013

Authors: Sikora, Marek

Article Type: Research Article

Abstract: The paper presents an algorithm of decision rules redefinition that is based on evaluation of the importance of elementary conditions occurring in induced rules. Standard and simplified (heuristic) indices of elementary condition importance evaluation are described. There is a comparison of the results obtained by both indices concerning classifiers quality and elementary condition rankings estimated by the indices. The efficiency of the proposed algorithm has been verified on 21 benchmark data sets. Moreover, an analysis of practical applications of the proposed methods for biomedical and medical data analysis is presented. The obtained results show that the redefinition reduces considerably a …rule set needed to describe each decision class. Additionally, after the rule set redefinition negated elementary conditions may also occur in new rules. Show more

Keywords: decision rules, importance of elementary conditions, rule quality measures, knowledge discovery, classification

DOI: 10.3233/FI-2013-806

Citation: Fundamenta Informaticae, vol. 123, no. 2, pp. 171-197, 2013

Authors: van Vliet, Rudy | Hoogeboom, Hendrik Jan

Article Type: Research Article

Abstract: DNA expressions constitute a formal notation for DNA molecules that may contain nicks and gaps. Different DNA expressions may denote the same DNA molecule. We describe an algorithm to rewrite a given DNA expression into a DNA expression of minimal length denoting the same molecule.

Keywords: DNA molecules, formal notation, minimal DNA expressions, algorithm, complexity

DOI: 10.3233/FI-2012-807

Citation: Fundamenta Informaticae, vol. 123, no. 2, pp. 199-226, 2013

Authors: van Vliet, Rudy | Hoogeboom, Hendrik Jan

Article Type: Research Article

Abstract: DNA expressions constitute a formal notation for DNA molecules that may contain nicks and gaps. Different DNA expressions may denote the same DNA molecule. We define a (minimal) normal form for the language of DNA expressions, and describe an algorithm to rewrite a given DNA expression into the normal form.

Keywords: DNA molecules, formal notation, DNA expressions, minimal normal form, algorithm, complexity

DOI: 10.3233/FI-2012-808

Citation: Fundamenta Informaticae, vol. 123, no. 2, pp. 227-243, 2013