Drawing slicing graphs with face areas

We consider orthogonal drawings of a plane graph G$G$ with specified face areas. For a natural number k$k$, a k$k$-gonal drawing of G$G$ is an orthogonal drawing such that the boundary of G$G$ is drawn as a rectangle and each inner face is drawn as a polygon with at most k$k$ corners whose area is equal to the specified value. In this paper, we show that every slicing graph G$G$ with a slicing tree T$T$ and a set of specified face areas admits a 10-gonal drawing D$D$ such that the boundary of each slicing subgraph that appears in T$T$ is also drawn as a polygon with at most 10 corners. Such a drawing D$D$ can be found in linear time.     

Algorithms for near solutions to polynomial equations

Let F(x,y)$F(x,y)$ be a polynomial over a field K$K$ and m$m$ a nonnegative integer. We call a polynomial g$g$ over K$K$ an m$m$-near solution of F(x,y)$F(x,y)$ if there exists a c∈K$c\in K$ such that F(x,g)=cx^m$F(x,g)=c{x}^m$, and the number c$c$ is called an m$m$-value of F(x,y)$F(x,y)$ corresponding to g$g$. In particular, c$c$ can be 0. Hence, by viewing F(x,y)=0$F(x,y)=0$ as a polynomial equation over K[x]$K\left[x\right]$ with variable y$y$, every solution of the equation F(x,y)=0$F(x,y)=0$ in K[x]$K\left[x\right]$ is also an m$m$-near solution. We provide an algorithm that gives all m$m$-near solutions of a given polynomial F(x,y)$F(x,y)$ over K$K$, and this algorithm is polynomial time reducible to solving one variable equations over K$K$. We introduce approximate solutions to analyze the algorithm. We also give some interesting properties of approximate solutions.     

On semimeasures predicting Martin-Löf random sequences

Solomonoff’s central result on induction is that the prediction of a universal semimeasure M$M$ converges rapidly and with probability 1 to the true sequence generating predictor μ$\mu$, if the latter is computable. Hence, M$M$ is eligible as a universal sequence predictor in the case of unknown μ$\mu$. Despite some nearby results and proofs in the literature, the stronger result of convergence for all (Martin-Löf) random sequences remained open. Such a convergence result would be particularly interesting and natural, since randomness can be defined in terms of M$M$ itself. We show that there are universal semimeasures M$M$ which do not converge to μ$\mu$ on all μ$\mu$-random sequences, i.e. we give a partial negative answer to the open problem. We also provide a positive answer for some non-universal semimeasures. We define the incomputable measure D$D$ as a mixture over all computable measures and the enumerable semimeasure W$W$ as a mixture over all enumerable nearly measures. We show that W$W$ converges to D$D$ and D$D$ to μ$\mu$ on all random sequences. The Hellinger distance measuring closeness of two distributions plays a central role.     

Paths and trails in edge-colored graphs

This paper deals with the existence and search for properly edge-colored paths/trails between two, not necessarily distinct, vertices s$s$ and t$t$ in an edge-colored graph from an algorithmic perspective. First we show that several versions of the s−t$s-t$ path/trail problem have polynomial solutions including the shortest path/trail case. We give polynomial algorithms for finding a longest properly edge-colored path/trail between s$s$ and t$t$ for a particular class of graphs and characterize edge-colored graphs without properly edge-colored closed trails. Next, we prove that deciding whether there exist k$k$ pairwise vertex/edge disjoint properly edge-colored s−t$s-t$ paths/trails in a c$c$-edge-colored graph G^c$G^c$ is NP-complete even for k=2$k=2$ and c=Ω(n²)$c=\Omega \left(n^2\right)$, where n$n$ denotes the number of vertices in G^c$G^c$. Moreover, we prove that these problems remain NP-complete for c$c$-edge-colored graphs containing no properly edge-colored cycles and c=Ω(n)$c=\Omega \left(n\right)$. We obtain some approximation results for those maximization problems together with polynomial results for some particular classes of edge-colored graphs.     

A palindromization map for the free group

We define a self-map Pal:_F2→_F2$Pal:F_2\to F_2$ of the free group on two generators a,b$a,b$, using automorphisms of _F2$F_2$ that form a group isomorphic to the braid group _B3$B_3$. The map Pal$Pal$ restricts to de Luca’s right iterated palindromic closure on the submonoid generated by a,b$a,b$. We show that Pal$Pal$ is continuous for the profinite topology on _F2$F_2$; it is the unique continuous extension of de Luca’s right iterated palindromic closure to _F2$F_2$. The values of Pal$Pal$ are palindromes and coincide with the elements g∈_F2$g\in F_2$ such that abg$abg$ and bag$bag$ are conjugate.     

On the minimum of a positive polynomial over the standard simplex

We present a new positive lower bound for the minimum value taken by a polynomial P$P$ with integer coefficients in k$k$ variables over the standard simplex of R^k${\mathbb{R}}^k$, assuming that P$P$ is positive on the simplex. This bound depends only on the number of variables k$k$, the degree d$d$ and the bitsize τ$\tau$ of the coefficients of P$P$ and improves all the previous bounds for arbitrary polynomials which are positive over the simplex.     

A modified hidden Markov model

This paper considers two discrete time, finite state processes X$X$ and Y$Y$. In the usual hidden Markov model X$X$ modulates the values of Y$Y$. However, the values of Y$Y$ are then i.i.d. given X$X$. In this paper a new model is considered where the Markov chain X$X$ modulates the transition probabilities of the second, observed chain Y$Y$. This more realistically can represent problems arising in DNA sequencing. Algorithms for all related filters, smoothers and parameter estimations are derived. Versions of the Viterbi algorithms are obtained.     

Divergence bounded computable real numbers

A real x$x$ is called h$h$-bounded computable  , for some function h:N→N$h:\mathbb{N}\to \mathbb{N}$, if there is a computable sequence (_xs)$(x_s)$ of rational numbers which converges to x$x$ such that, for any n∈N$n\in \mathbb{N}$, at most h(n)$h(n)$ non-overlapping pairs of its members are separated by a distance larger than 2^-n$2^{-n}$. In this paper we discuss properties of h$h$-bounded computable reals for various functions h$h$. We will show a simple sufficient condition for a class of functions h$h$ such that the corresponding h$h$-bounded computable reals form an algebraic field. A hierarchy theorem for h$h$-bounded computable reals is also shown. Besides we compare semi-computability and weak computability with the h$h$-bounded computability for special functions h$h$.     

Gröbner bases with respect to several orderings and multivariable dimension polynomials

Let D=K[X]$D=K\left[X\right]$ be a ring of Ore polynomials over a field K$K$ and let a partition of the set of indeterminates into p$p$ disjoint subsets be fixed. Considering D$D$ as a filtered ring with the natural p$p$-dimensional filtration, we introduce a special type of reduction in a free D$D$-module and develop the corresponding Gröbner basis technique (in particular, we obtain a generalization of the Buchberger Algorithm). Using such a modification of the Gröbner basis method, we prove the existence of a Hilbert-type dimension polynomial in p$p$ variables associated with a finitely generated filtered D$D$-module, give a method of computation and describe invariants of such a polynomial. The results obtained are applied in differential algebra where the classical theorems on differential dimension polynomials are generalized to the case of differential structures with several basic sets of derivation operators.     

On the parameterized complexity of multiple-interval graph problems

Multiple-interval graphs are a natural generalization of interval graphs where each vertex may have more than one interval associated with it. Many applications of interval graphs also generalize to multiple-interval graphs, often allowing for more robustness in the modeling of the specific application. With this motivation in mind, a recent systematic study of optimization problems in multiple-interval graphs was initiated. In this sequel, we study multiple-interval graph problems from the perspective of parameterized complexity. The problems under consideration are k$k$-Independent Set, k$k$-Dominating Set, and k$k$-Clique, which are all known to be W[1]-hard for general graphs, and NP-complete for multiple-interval graphs. We prove that k$k$-Clique is in FPT, while k$k$-Independent Set and k$k$-Dominating Set are both W[1]-hard. We also prove that k$k$-Independent Dominating Set, a hybrid of the two above problems, is also W[1]-hard. Our hardness results hold even when each vertex is associated with at most two intervals, and all intervals have unit length. Furthermore, as an interesting byproduct of our hardness results, we develop a useful technique for showing W[1]-hardness via a reduction from the k$k$-Multicolored Clique problem, a variant of k$k$-Clique. We believe this technique has interest in its own right, as it should help in simplifying W[1]-hardness results which are notoriously hard to construct and technically tedious.     

Local edge colouring of Yao-like subgraphs of Unit Disk Graphs

The focus of the present paper is on providing a local deterministic algorithm for colouring the edges of Yao-like   subgraphs of Unit Disk Graphs. These are geometric graphs such that for some positive integers l,k$l,k$ the following property holds at each node v$v$: if we partition the unit circle centered at v$v$ into 2k$2k$ equally sized wedges then each wedge can contain at most l$l$ points different from v$v$. We assume that the nodes are location aware, i.e. they know their Cartesian coordinates in the plane. The algorithm presented is local in the sense that each node can receive information emanating only from nodes which are at most a constant (depending on k$k$ and l$l$, but not on the size of the graph) number of hops (measured in the original underlying Unit Disk Graph) away from it, and hence the algorithm terminates in a constant number of steps. The number of colours used is 2kl+1$2kl+1$ and this is optimal for local algorithms (since the maximal degree is 2kl$2kl$ and a colouring with 2kl$2kl$ colours can only be constructed by a global algorithm), thus showing that in this class of graphs the price for locality is only one additional colour.     

Fraction-free algorithm for the computation of diagonal forms matrices over Ore domains using Gröbner bases

This paper is a sequel to “Computing diagonal form and Jacobson normal form of a matrix using Gröbner bases” (Levandovskyy and Schindelar, 2011). We present a new fraction-free algorithm for the computation of a diagonal form of a matrix over a certain non-commutative Euclidean domain over a computable field with the help of Gröbner bases. This algorithm is formulated in a general constructive framework of non-commutative Ore localizations of G$G$-algebras (OLGAs). We use the splitting of the computation of a normal form for matrices over Ore localizations into the diagonalization and the normalization processes. Both of them can be made fraction-free. For a given matrix M$M$ over an OLGA R$R$, we provide a diagonalization algorithm to compute U,V$U,V$ and D$D$ with fraction-free entries such that UMV=D$UMV=D$ holds and D$D$ is diagonal. The fraction-free approach allows to obtain more information on the associated system of linear functional equations and its solutions, than the classical setup of an operator algebra with coefficients in rational functions. In particular, one can handle distributional solutions together with, say, meromorphic ones. We investigate Ore localizations of common operator algebras over K[x]$K\left[x\right]$ and use them in the unimodularity analysis of transformation matrices U,V$U,V$. In turn, this allows to lift the isomorphism of modules over an OLGA Euclidean domain to a smaller polynomial subring of it. We discuss the relation of this lifting with the solutions of the original system of equations. Moreover, we prove some new results concerning normal forms of matrices over non-simple domains. Our implementation in the computer algebra system Singular:Plural follows the fraction-free strategy and shows impressive performance, compared with methods which directly use fractions. In particular, we experience a moderate swell of coefficients and obtain simple transformation matrices. Thus the method we propose is well suited for solving nontrivial practical problems.