DSpace Collection: Volume 9 Number 2
http://hdl.handle.net/10525/2474
The Collection's search engineSearch the Channelsearch
http://sci-gems.math.bas.bg/jspui/simple-search
On the Time Complexity of the Problem Related to Reducts of Consistent Decision Tables
http://hdl.handle.net/10525/2490
Title: On the Time Complexity of the Problem Related to Reducts of Consistent Decision Tables<br/><br/>Authors: Janos, Demetrovics; Thi, Vu Duc; Giang, Nguyen Long; Duong, Tran Huy<br/><br/>Abstract: In recent years, rough set approach computing issues concerningreducts of decision tables have attracted the attention of many researchers.In this paper, we present the time complexity of an algorithmcomputing reducts of decision tables by relational database approach. LetDS = (U, C ∪ {d}) be a consistent decision table, we say that A ⊆ C is arelative reduct of DS if A contains a reduct of DS. Let s = <C ∪ {d} , F>be a relation schema on the attribute set C ∪ {d}, we say that A ⊆ C isa relative minimal set of the attribute d if A contains a minimal set of d.Let Qd be the family of all relative reducts of DS, and Pd be the family ofall relative minimal sets of the attribute d on s.We prove that the problem whether Qd ⊆ Pd is co-NP-complete.However, the problem whether Pd ⊆ Qd is in P .Lower Bounds on the Directed Sweepwidth of Planar Shapes
http://hdl.handle.net/10525/2489
Title: Lower Bounds on the Directed Sweepwidth of Planar Shapes<br/><br/>Authors: Markov, Minko; Haralampiev, Vladislav; Georgiev, Georgi<br/><br/>Abstract: We investigate a recently introduced width measure of planarshapes called sweepwidth and prove a lower bound theorem on the sweepwidth.Distance Distributions and Energy of Designs in Hamming Spaces
http://hdl.handle.net/10525/2488
Title: Distance Distributions and Energy of Designs in Hamming Spaces<br/><br/>Authors: Boyvalenkov, Peter; Marinova, Tanya; Stoyanova, Maya; Sukalinska, Mila<br/><br/>Abstract: We obtain new combinatorial upper and lower bounds for thepotential energy of designs in q-ary Hamming space. Combined with resultson reducing the number of all feasible distance distributions of such designsthis gives reasonable good bounds. We compute and compare our lowerbounds to recently obtained universal lower bounds. Some examples in thebinary case are considered.On the Remainders Obtained in Finding the Greatest Common Divisor of Two Polynomials
http://hdl.handle.net/10525/2487
Title: On the Remainders Obtained in Finding the Greatest Common Divisor of Two Polynomials<br/><br/>Authors: Akritas, Alkiviadis; Malaschonok, Gennadi; Vigklas, Panagiotis<br/><br/>Abstract: In 1917 Pell (1) and Gordon used sylvester2, Sylvester’s littleknown and hardly ever used matrix of 1853, to compute(2)the coefficients of a Sturmian remainder — obtained in applying in Q[x],Sturm’s algorithm on two polynomials f, g ∈ Z[x] of degree n — in terms ofthe determinants (3) of the corresponding submatrices of sylvester2.Thus, they solved a problem that had eluded both J. J. Sylvester, in 1853,and E. B. Van Vleck, in 1900. (4)In this paper we extend the work by Pell and Gordon and show how to compute (2)the coefficients of an Euclidean remainder — obtained in finding in Q[x],the greatest common divisor of f, g ∈ Z[x] of degree n — in terms ofthe determinants (5) of the corresponding submatrices of sylvester1,Sylvester’s widely known and used matrix of 1840.(1) See the link http://en.wikipedia.org/wiki/Anna_Johnson_Pell_Wheeler for her biography(2) Both for complete and incomplete sequences, as defined in the sequel.(3) Also known as modified subresultants.(4) Using determinants Sylvester and Van Vleck were able to compute the coefficientsof Sturmian remainders only for the case of complete sequences.(5) Also known as (proper) subresultants.An Algorithm to Mine Normalized Weighted Sequential Patterns Using a Prefix-projected Database
http://hdl.handle.net/10525/2486
Title: An Algorithm to Mine Normalized Weighted Sequential Patterns Using a Prefix-projected Database<br/><br/>Authors: Demetrovics, Janos; Thi, Vu Duc; Duong, Tran Huy<br/><br/>Abstract: Sequential pattern mining is an important subject in data mining with broadapplications in many different areas. However, previous sequential miningalgorithms mostly aimed to calculate the number of occurrences (the support)without regard to the degree of importance of different data items.In this paper, we propose to explore the search space of subsequenceswith normalized weights. We are not only interested in the numberof occurrences of the sequences (supports of sequences), but also concernedabout importance of sequences (weights). When generating subsequencecandidates we use both the support and the weight of the candidates whilemaintaining the downward closure property of these patterns which allowsto accelerate the process of candidate generation.