The complexity of homomorphisms and renamings for minimal unsatisfiable formulas

We investigate the complexity of deciding whether for minimal unsatisfiable formulas F and H there exists a variable renaming, a literal renaming or a homomorphism such that (F)=H. A variable renaming is a permutation of variables. A literal renaming is a permutation of variables which additionally replaces some of the variables by its complements. A homomorphism can be considered as a literal renaming which can map different literals to one literal.     

An Efficient Fixed Parameter Tractable Algorithm for 1-Sided Crossing Minimization

We give an O(^k · n²) fixed parameter tractable algorithm for the 1-Sided Crossing Minimization. The constant in the running time is the golden ratio = (1+5)/2 1.618. The constant k is the parameter of the problem: the number of allowed edge crossings.     

Three-valued representative systems

A representative system defined onn voters or propositionsi = 1,,n is a functionF: {1,0, -1} ⁿ {1,0, -1} which is monotonic (D E F(D) F(E)), unanimous (F(1,, 1) = 1), dual (F(-D) = -F(D)), and satisfies a positivity property which says that the set of all non-zero vectors in {1, 0, -1} ⁿ for whichF(D) = 0 can be partitioned into two dual subsets each of which has the property that ifD andE are in the subset thenD _i+E _i > 0 for somei. Representative systems can be defined recursively from the coordinate projectionsS _i (D) = D _i using sign functions, and in this format they are interpreted as hierarchical voting systems in which outcomes of votes in lower levels act as votes in higher levels of the system. For each positive integern, (n) is defined as the smallest positive integer such that all representative systems defined on {1, 0, -1} ⁿ can be characterized by(n) or fewer hierarchical levels. The function is nondecreasing inn, unbounded above, and satisfies(n) n–1 for alln. In addition,(n) = n–1 forn {1, 2, 3, 4}, and it is conjectured that does not continue to grow linearly asn increases.     

Best Huffman trees

Summary Given a sequence of positive weights, W=w ₁...w _n >0, there is a Huffman tree, T (T-up) which minimizes the following functions: max{d(w_i)}; d(w_i); f(d(w_i)) w _i(here d(w _i) represents the distance of a leaf of weight w _i to the root and f is a function defined for nonnegative integers having the property that g(x) = f(x + 1) – f(x) is monotone increasing) over the set of all trees for W having minimal expected length. Minimizing the first two functions was first done by Schwartz [5]. In the case of codes where W is a sequence of probabilities, this implies that the codes based on T have all their absolute central moments minimal. In particular, they are the least variance codes which were also described by Kou [3]. Furthermore, there exists a Huffman tree T, (T-down) which maximizes the functions considered above.However, if g(x) is monotone decreasing, T and T, respectively maximize and minimize f(d(w_i) w _i) over the set of all trees for W having minimal expected length. In addition, we derive a number of interesting results about the distribution of labels within Huffman trees. By suitable modifications of the usual Huffman tree construction, (see [1]) T and T can also be constructed in time O(n log n).     

Constructing strongly convex hulls using exact or rounded arithmetic

One useful generalization of the convex hull of a setS ofn points is the -strongly convex -hull. It is defined to be a convex polygon with vertices taken fromS such that no point inS lies farther than outside and such that even if the vertices of are perturbed by as much as , remains convex. It was an open question as to whether an -strongly convexO()-hull existed for all positive . We give here anO(n logn) algorithm for constructing it (which thus proves its existence). This algorithm uses exact rational arithmetic. We also show how to construct an -strongly convexO( + )-hull inO(n logn) time using rounded arithmetic with rounding unit . This is the first rounded-arithmetic convex-hull algorithm which guarantees a convex output and which has error independent ofn.     

Undirecteds-t connectivity in polynomial time and sublinear space

Thes-t connectivity problem for undirected graphs is to decide whether two designated vertices,s andt, are in the same connected component. This paper presents the first known deterministic algorithms solving undirecteds-t connectivity using sublinear space and polynomial time. Our algorithms provide a nearly smooth time-space tradeoff between depth-first search and Savitch's algorithm. Forn vertex,m edge graphs, the simplest of our algorithms uses spaceO(s),n ^1/2log₂ nsnlog₂ n, and timeO(((m+n)n ² log² n)/s). We give a variant of this method that is faster at the higher end of the space spectrum. For example, with space (nlogn), its time bound isO((m+n)logn), close to the optimal time for the problem. Another generalization uses less space, but more time: spaceO(n ^1/logn), for 2log₂ n, and timen ^O(). For constant the time remains polynomial.     

Correlation structure of training data and the fitting ability of back propagation networks: Some experimental results

White [6–8] has theoretically shown that learning procedures used in network training are inherently statistical in nature. This paper takes a small but pioneering experimental step towards learning about this statistical behaviour by showing that the results obtained are completely in line with White's theory. We show that, given two random vectorsX (input) andY (target), which follow a two-dimensional standard normal distribution, and fixed network complexity, the network's fitting ability definitely improves with increasing correlation coefficient r_XY (0r_XY1) betweenX andY. We also provide numerical examples which support that both increasing the network complexity and training for much longer do improve the network's performance. However, as we clearly demonstrate, these improvements are far from dramatic, except in the case r_XY=+ 1. This is mainly due to the existence of a theoretical lower bound to the inherent conditional variance, as we both analytically and numerically show. Finally, the fitting ability of the network for a test set is illustrated with an example.Nomenclature X Generalr-dimensional random vector. In this work it is a one-dimensional normal vector and represents the input vector - Y Generalp-dimensional random vector. In this work it is a one-dimensional normal vector and represents the target vector - Z Generalr+p dimensional random vector. In this work it is a two-dimensional normal vector - E Expectation operator (Lebesgue integral) - g(X)=E(Y¦X) Conditional expectation - Experimental random error (defined by Eq. (2.1)) - y Realized target value - o Output value - f Network's output function. It is formally expressed asf: R ^r×WR ^p, whereW is the appropriate weight space - Average (or expected) performance function. It is defined by Eq. (2.2) as (w)=E[(Yf(X,w)],w W - Network's performance - w ^* Weight vector for optimal solution. That is, the objective of network is such that (w ^*) is minimum - C ₁ Component one - C ₂ Component two - Z Matrix of realised values of the random vectorZ overn observations - Z _t Transformed matrix version ofZ in such a way thatX andY have values in [0,1] - X _t ,Y _t Transformed versions ofX andY and both are standard one-dimensional normal vectors - n _h Number of hidden nodes (neurons) - r _XY Correlation coefficient between eitherX andY orX _t andY _t - _s and _k in Eq. (3.1) and afterwards _s is average value of 100 differentZ _t matrices. _k is the error function ofkthZ _t , matrix. In Eq. (3.1), the summation is fromk=1 to 100, and in Eq. (3.2) fromi=1 ton. In Eq. (3.2)o _ki andy _ki are the output and target values for the kthZ _t matrix and ith observation, respectively - ^1/2(w ^*) and _k (w_n) k(w_n) is the sample analogue of ^1/2(w ^*) - _Y ² In Eq. (4.1) and afterwards, _Y ² is the variance ofY - _Y ² variance ofY _t . In Sect. 4.3 the transformation isY _t=a Y+b - Y _max,Y _min the maximum and minimum values ofY - R Correlation matrix ofX andY - Covariance matrix ofX andY - Membership symbol in set theory     

Cardinality problems of compositions of morphisms and inverse morphisms

We show that we cannot effectively determine whether, for morphisms _i , _i ,card (u ₀ ^–1 ₁) =card(u ₀ ^–1 ₁) for all wordsu over the domain alphabets of the two given compositions. In contrast it is decidable for morphisms _i , _i and a regular setR whethercard(u _{0 1} ^–1 ) =card(u _{0 1} ^–1 ) for all wordsu inR. In order to prove the latter result we give a characterization of the multiplicity functions of simple finite automata by using cardinalities of compositions of the above form. Finally, we show that the above decidability result also holds when we consider rational functions rather than morphisms.     

Learning-theoretic perspectives of acceptable numberings

A class of recursive functionsC islimiting standardizable, in a programming system , iff there is an effective procedure which, given any -program (in the -system), synthesizes in the limit acanonical -program which is equivalent to the former. It can arguably be expected that notions similar to the above one would be relevant toGold-style function learning, which features, among other things, the effective limiting synthesis of programs for input recursive functions. Many learning classes have been characterized in terms of variants of the above notion. In this paper, we focus on the limiting standardizability of the entire class of recursive functions inEffective programming systems. To start with, we prove the independence of this notionvis-à-vis finitary recursion theorems. Secondly, we show that this motion does not entail acceptability, in the spirit of the results of Case, Riccardi and Royer on characterizations of the samevis-à-vis programming language control structures.     

Proof Reflection in Coq

We formalize natural deduction for first-order logic in the proof assistant Coq, using de Bruijn indices for variable binding. The main judgment we model is of the form d[:], stating that d is a proof term of formula under hypotheses it can be viewed as a typing relation by the Curry–Howard isomorphism. This relation is proved sound with respect to Coq's native logic and is amenable to the manipulation of formulas and of derivations. As an illustration, we define a reduction relation on proof terms with permutative conversions and prove the property of subject reduction.