Wyniki wyszukiwania - BazTech

1

Matroids And Greedy Algorithms. A Deeper Justification of Using Greedy Approach To Find A Maximal set of a Matroid

Haider S. A.

Annales Universitatis Mariae Curie-Skłodowska. Sectio AI, Informatica

|

2016

|

Vol. 16, no. 2

48--50

EN

Greedy algorithms are used in solving a diverse set of problems in small computation time. However, for solving problems using greedy approach, it must be proved that the greedy strategy applies. The greedy approach relies on selection of optimal choice at a local level reducing the problem to a single sub problem, which actually leads to a globally optimal solution. Finding a maximal set from the independent set of a matroid M(S, I) also uses greedy approach and justification is also provided in standard literature (e.g. Introduction to Algorithms by Cormen et .al.). However, the justification does not clearly explain the equivalence of using greedy algorithm and contraction of M by the selected element. This paper thus attempts to give a lucid explanation of the fact that the greedy algorithm is equivalent to reducing the Matroid into its contraction by selected element. This approach also provides motivation for research on the selection of the test used in algorithm which might lead to smaller computation time of the algorithm.

2

Maximal Weak-Type Inequality for Orthogonal Harmonic Functions and Martingales

Osękowski A.

Bulletin of the Polish Academy of Sciences. Mathematics

|

2013

|

Vol. 61, no 3-4

209--218

EN

Assume that u, v are conjugate harmonic functions on the unit disc of C, normalized so that u(0)=v(0)=0. Let u∗, |v|∗ stand for the one- and two-sided Brownian maxima of u and v, respectively. The paper contains the proof of the sharp weak-type estimate... [formula]. Actually, this estimate is shown to be true in the more general setting of differentially subordinate harmonic functions defined on Euclidean domains. The proof exploits a novel estimate for orthogonal martingales satisfying differential subordination.

3

Computing Maximal Error-detecting Capabilities and Distances of Regular Languages

Konstantinidis S., Silva P.V.

Fundamenta Informaticae

|

2010

|

Vol. 101, nr 4

257-270

EN

A (combinatorial) channel consists of pairs of words representing all possible inputoutput channel situations. In a past paper, we formalized the intuitive concept of "largest amount of errors" detectable by a given language L, by defining the maximal error-detecting capabilities of L with respect to a given class of channels, and we showed how to compute all maximal error-detecting capabilities (channels) of a given regular language with respect to the class of rational channels and a class of channels involving only the substitution-error type. In this paper we resolve the problem for channels involving any combination of the basic error types: substitution, insertion, deletion. Moreover, we consider the problem of finding the inverses of these channels, in view of the fact that L is error-detecting for γif and only if it is error-detecting for the inverse of γ. We also discuss a natural method of reducing the problem of computing (inner) distances of a given regular language L to the problem of computing maximal error-detecting capabilities of L

4

Combinatorics of Unique Maximal Factorization Families (UMFFs)

Daykin D.E., Daykin J.W., Smyth W.F. (Bill)

Fundamenta Informaticae

|

2009

|

Vol. 97, nr 3

295-309

EN

Suppose a set W of strings contains exactly one rotation (cyclic shift) of every primitive string on some alphabet Σ. Then W is a circ-UMFF if and only if every word in Σ+ has a unique maximal factorization over W. The classic circ-UMFF is the set of Lyndon words based on lexicographic ordering (1958). Duval (1983) designed a linear sequential Lyndon factorization algorithm; a corresponding PRAMparallel algorithmwas described by J. Daykin, Iliopoulos and Smyth (1994). Daykin and Daykin defined new circ-UMFFs based on various methods for totally ordering sets of strings (2003), and further described the structure of all circ-UMFFs (2008). Here we prove new combinatorial results for circ-UMFFs, and in particular for the case of Lyndon words. We introduce Acrobat and Flight Deck circ-UMFFs, and describe some of our results in terms of dictionaries. Applications of circ-UMFFs pertain to structured methods for concatenating and factoring strings over ordered alphabets, and those of Lyndon words are wide ranging and multidisciplinary.