Fundamenta Informaticae - Volume 104, issue 3

Authors: Hromkovič, Juraj | Šuster, Borislav | Toman, Eduard

Article Type: Research Article

DOI: 10.3233/FI-2010-342

Citation: Fundamenta Informaticae, vol. 104, no. 3, pp. i-i, 2010

Authors: Ablayev, Farid | Ablayeva, Svetlana

Article Type: Research Article

Abstract: In function theory the superposition problem is known as the problem of representing a continuous function f(x1 , … ,xk ) in k variables as the composition of “simpler” functions. This problem stems from the Hilbert's thirteenth problem. In computer science good formalization for the notion of composition of functions is formula. In the paper we consider real-valued continuous functions in k variables in the cube [0,1]k from the class ℋk ωp with ωp a special modulus of continuity (measure the smoothness of a function) defined in the paper. ℋk ωp is a superset of Hölder class of …functions. We present an explicit function f ∈ ℋk ωp which is hard in the sense that it cannot be represented in the following way as a formula: zero level (input) gates associated with variables {x1 , … ,xk } (different input gates can be associated with the same variable xi ∈ {x1 , … ,xk }), on the first level of the formula, arbitrary number s ≥ 1 of t variable functions from ℋt ωp for t < k are allowed, while the second (output) level may compute any s variable Hölder function. We apply communication complexity for constructing such hard explicit function. Notice that one can show the existence of such function using the “non constructive” proof method known in function theory as Kolmogorov's entropy method. Show more

Keywords: Hilbert 13th problem, superposition of continuous functions, communication complexity

DOI: 10.3233/FI-2010-343

Citation: Fundamenta Informaticae, vol. 104, no. 3, pp. 185-200, 2010

Authors: Albrecht, Andreas A. | Chashkin, Alexander V. | Iliopoulos, Costas S. | Kasim-Zade, Oktay M. | Lappas, Georgios | Steinhöfel, Kathleen K.

Article Type: Research Article

Abstract: The paper aims at tight upper bounds on the size of pattern classification circuits that can be used for a priori parameter settings in a machine learning context. The upper bounds relate the circuit size S(C) to nL := [log2 mL ], where mL is the number of training samples. In particular, we show that there exist unbounded fan-in threshold circuits with less than (a) SRcc := 2·√2nL + 3 gates for unbounded depth, (b) SLcc := 34.8 · √2nL + 14 · nL − 11 · log2 nL …+ 2 gates for small bounded depth, where in both cases all mL samples are classified correctly. We note that the upper bounds do not depend on the length n of input (sample) vectors. Since nL << n in real-world problem settings, the upper bounds return values that are suitable for practical applications. We provide experimental evidence that the circuit size estimations work well on a number of pattern classification tasks. As a result, we formulate the conjecture that [1.25 · SRcc or [0.07 · SLcc ] gates are sufficient to achieve a high generalization rate of bounded-depth classification circuits. Show more

Keywords: Threshold circuits, neural network synthesis, pattern classification, circuit complexity, sample size

DOI: 10.3233/FI-2010-344

Citation: Fundamenta Informaticae, vol. 104, no. 3, pp. 201-217, 2010

Authors: Alekhina, Marina An.

Article Type: Research Article

Abstract: We consider the realization of Boolean functions by combinatorial circuits with unreliable gates computing the functions from a complete final basis B. We assume that all gates of the basis can have inverse faults on the outputs independently with probability ε (ε ∈ (0, 1/2)). We describe a set Mk (k ≥ 3) of Boolean functions, presence even by one of which in basis B guarantees the computing of almost all Boolean functions by asymptotically optimal circuits with unreliability ε at ε → 0. We prove that, for almost all functions, the complexity of asymptotically circuits with unreliable gates …exceeds the complexity of the minimal circuits constructed from absolutely reliable gates by a multiplicative factor of 3(1 + b) for any b > 0. Show more

Keywords: Boolean function, synthesis, complexity, reliability of combinatorial circuits

DOI: 10.3233/FI-2010-345

Citation: Fundamenta Informaticae, vol. 104, no. 3, pp. 219-225, 2010

Authors: Gashkov, Sergej B. | Gashkov, Igor B.

Article Type: Research Article

Abstract: We prove some improvements for well-known upper bound of complexity of testing irreducibility of polynomials over finite fields. Also the fast modification of well-known probabilistic algorithm finding a normal bases in special finite fields is presented.

Keywords: Finite fields, irreducible polynomials, normal bases, addition chains

DOI: 10.3233/FI-2010-346

Citation: Fundamenta Informaticae, vol. 104, no. 3, pp. 227-238, 2010

Authors: Lozhkin, Sergei A. | Shiganov, Alexander E.

Article Type: Research Article

Abstract: In this paper we study the representation of Boolean functions by general binary decision diagrams (BDDs). We investigate the size L(Σ) (number of inner nodes) of BDD Σ with different constraints on the number M(Σ) of its merged nodes. Furthermore, we introduce a weighted complexity measure W(Σ) = L(Σ) + ωM(Σ), where ω > 0. For the hardest Boolean function on n input variables we define the weight WBDD (n) and the size LBDD (n,t), where t limits the number of merged nodes. By using a new synthesis method and appropriate restrictions for the number t of merged nodes, we …are able to prove tight upper and lower asymptotic bounds: WBDD (n) = 2n /n (1 + log n ± O(1)/n), LBDD (n,t) = 2n /log nt (1 ± O(1/n)), which have a relative error of O(1/n). Our results show how weight and structural restrictions of general BDDs influence the complexity of the hardest function in terms of high accuracy asymptotic bounds. Show more

Keywords: Boolean function, circuit, binary decision diagram, complexity, high accuracy asymptotic bound

DOI: 10.3233/FI-2010-347

Citation: Fundamenta Informaticae, vol. 104, no. 3, pp. 239-253, 2010

Authors: Melnikov, Boris

Article Type: Research Article

Abstract: We consider a new expansion of nondeterministic finite automata. The goals of this consideration are: to apply some algorithms of such expansion for various problems of minimization of classical nondeterministic automata; to use such automata for describing practical anytime algorithms for the same problems of minimization; using such automata, we often can simplify some proofs for algorithms of simplification of usual nondeterministic automata.

Keywords: Nondeterministic finite automata, extended automata, basic automaton, algorithms of simplification

DOI: 10.3233/FI-2010-348

Citation: Fundamenta Informaticae, vol. 104, no. 3, pp. 255-265, 2010

Authors: Melnikov, Boris

Article Type: Research Article

Abstract: We consider in this paper the problem of edge-minimization for nondeterministic finite automata and some connected questions. We shall formulate a new algorithm solving this problem; this algorithm is a simplification of two ones published before. The connected problems include at first algorithms of combining states. We formulate some new sufficient conditions for the possibility of such combining.

Keywords: Nondeterministic finite automata, basic automaton, algorithms of simplification, algorithms of combining states, edge-minimization

DOI: 10.3233/FI-2010-349

Citation: Fundamenta Informaticae, vol. 104, no. 3, pp. 267-283, 2010

Authors: Moshkov, Mikhail Ju.

Article Type: Research Article

Abstract: An approximate algorithm for minimization of weighted depth of decision trees is considered. A bound on accuracy of this algorithm is obtained which is unimprovable in general case. Under some natural assumptions on the class NP, the considered algorithm is close (from the point of view of accuracy) to best polynomial approximate algorithms for minimization of weighted depth of decision trees.

Keywords: Decision table, decision tree, weight, greedy algorithm

DOI: 10.3233/FI-2010-350

Citation: Fundamenta Informaticae, vol. 104, no. 3, pp. 285-292, 2010