The language equivalence problem for HD0L systems having D0L growths

We show that language equivalence is decidable for HD0L systems having D0L growths. By definition, an HD0L system H has D0L growth if the length sequence of H is a D0L length sequence.     

On some decidability problems for HDOL systems with nonsingular Parikh matrices

The problem of decidability of ultimate equivalence, emptiness of intersection and finiteness of intersection for HD0L sequences the generating morphisms of which have nonsingular Parikh matrices is investigated. The first and the third of these decidability problems are shown to be closely connected with the equivalence problem for these sequences. In certain special cases the problems are proved to be solvable. A connection between the problem of effective findability of zeros in Z-rational sequences and the above problems is established (cf. [10]).     

Isomorphism,form equivalence and sequence equivalence of PD0L forms

It is shown that if two PD0L forms F₁ and F₂ are form equivalent, i.e., generate the same family of languages, then the PD0L sequences E(F₁) and E(F₂) are isomorphic, provided one of the sequences contains a word of length greater than one. This result leads to a simple algorithm of deciding the form equivalence of two PD0L forms F₁ and F₂. Moreover, we obtain the rather surprising result that F₁ and F₂ are form equivalent if and only if they are sequence equivalent, i.e., generate the same family of PD0L sequences (excluding again the trivial case that F₁ and F₂ generate only words of length one).     

A direct algorithm for checking equivalence of LL(k) grammars

We deal with the problem of testing equivalence of two LL(k) grammars. The problem had been shown to be decidable for general k by Rosenkrantz and Stearns [2], who solved it by reduction into an equivalence problem for special DPDA's. In a paper by Korenjak and Hopcroft [1] the equivalence problem for LL(1) grammars is solved by a branching algorithm operating directly on the grammars. Our work presents a direct branching algorithm for the general LL(k) grammars equivalence problem.     

Invariants and canonical forms for systems structural and parametric identification

The basic definitions regarding invariant functions and canonical forms for an equivalence relation on a generic set are first recalled.With reference to observable state space models and to the equivalence relation induced by a change of basis it is then shown how the image of a complete set of independent invariants for the considered equivalence relation can be used to parametrize a subset of canonical forms in the given set.Then the set of polynomial input-output models of the type P(z)y(t)=Q(z)u(t) and the equivalence relation induced by the premultiplication of P and Q by a unimodular matrix are considered and canonical forms parametrized by a complete set of independent invariants introduced.Since the two sets of canonical forms share common sets of complete independent invariants, very simple algebraical links between state space and input-output canonical forms can be deduced.The previous results are used to design efficient algorithms solving the problem of the canonical structural and parametric realization and identification of generic input-output sequences generated by a linear, discrete, time-invariant multivariable system.The results obtained in the identification of a real process are then reported.     

A polynomial algorithm testing partial confluence of basic semi-Thue systems

We give a polynomial algorithm solving the problem “is S partially confluent on the rational set R?” for finite, basic, noetherian semi-Thue systems. The algorithm is obtained by a polynomial reduction of this problem to the equivalence problem for deterministic 2-tape finite automata, which has been shown to be polynomially decidable in Friedman and Greibach (1982).     

Trace,failure and testing equivalences for communicating processes

A basic question in the theory of communicating processes is “When should two processes be considered equivalent?”. Attempts to answer this question have led to the concepts of observation equivalence, bisimulations, testing equivalence, failure equivalence, etc. The main point of this paper is to increase the understanding and motivation for two of these equivalences, namely failure and testing equivalences. The approach starts with the idea that the equivalence of processes should be reducible to the visible sequences of actions which a process performs in various contexts. This idea is implemented by a string-based semantic order for communicating processes where divergence is catastrophic. Under some assumptions about contexts, the resulting semantics is shown to be equivalent to theimproved failure semantics of Brookes and Roscoe⁽¹⁾ and also to themust testing-semantics of Hennessy and DeNicola.^(2–4) This characterization gives independent support for the appropriateness of failures and testing.     

A new bound for the D0L sequence equivalence problem

The D0L sequence equivalence problem consists of deciding, given two morphisms , and a word , whether or not g ⁱ (w) = h ⁱ (w) for all i ≥ 0. We show that in case of smooth and loop-free morphisms, to decide the D0L sequence equivalence problem, it suffices to consider the terms of the sequences with , where n is the cardinality of X.     

A dynamic programming solution to a generalized LCS problem

In this paper, we consider a generalized longest common subsequence problem, the string-excluding constrained LCS problem. For the two input sequences X and Y of lengths n and m, and a constraint string P of length r, the problem is to find a common subsequence Z of X and Y excluding P as a substring and the length of Z is maximized. The problem and its solution were first proposed by Chen and Chao (2011) [1], but we found that their algorithm cannot solve the problem correctly. A new dynamic programming solution for the STR-EC-LCS problem is then presented in this paper. The correctness of the new algorithm is proved. The time complexity of the new algorithm is $O(nmr)$.     

Balls in sequence spaces

A new metric on a space of right-sided infinite sequences drawn from a finite alphabet is proposed. This metric was introduced in the problem of estimating the entropy of discrete stationary processes. It has a number of interesting properties. For example, the measure of a ball is discontinuous at any binary rational value of logr, where r is the radius of the ball.     

Infinite arrays and controlled deterministic table 0L array systems

Deterministic table 0L array systems with control are considered for the generation of infinite arrays. Rewriting of a rectangular array is done in parallel by a table of rules, the rightmost edge horizontally or the lowermost edge vertically downwards. The application of the tables is controlled by a control set. Cube-free and square-free infinite arrays are obtained as an application of this model. The adherence of the array language of a controlled deterministic table 0L array system is related to the adherence of its control set. The limit language equivalence problem and the adherence equivalence problem are shown to be undecidable for this system.     

A simple approach to the problem of 3-D reconstruction

A relatively simple mathematical procedure for the reconstruction of the 3-dimensional (3D) image of the left ventricle (LV) of the heart is presented. The method is based on the assumption that every ray whoch emanates from the midpoint of the long axis of the 3D body crosses the surface boundary of the ventricle at one and only one point. The coordinates r_i, φ_i, θ_i of the data points on, say, the outer boundary, (i.e., the epicardium) are calculated in a spherical coordinate system having its origin in the midpoint of the long axis. The problem of defining the coordinates of a prescribed grid point on the boundary is treated as an interpolation problem for the function r = r(φ, θ), defined in the rectangle 0 ≤ φ ≤ 2π; 0 ≤ θ ≤ π with r_i given in the points (φ_i, θ_i).     

On identifying codes in the hexagonal mesh

It is shown that, if r?2, there exists an (r,?2)-identifying code in the infinite hexagonal mesh with density (5r+2)/((r+2)(2r+1)) for even r and (5r+1)/((r+1)(2r+1)) for odd r. The optimal density of a (1,?2)-identifying code in the infinite hexagonal mesh is shown to be 2/3 and the optimal densities of (1,?3)- and (2,?3)-identifying codes are shown to be 1.     

The Equivalence Problem of Polynomially Bounded D0L Systems— a Bound Depending Only on the Size of the Alphabet

Abstract. We give a bound for the sequence equivalence problem of polynomially bounded D0L systems which depends only on the size of the underlying alphabet.     

The Complexity of the Empire Colouring Problem

We investigate the computational complexity of the empire colouring problem (as defined by Percy Heawood in Q. J. Pure Appl. Math. 24:332–338, 1890) for maps containing empires formed by exactly r>1 countries each. We prove that the problem can be solved in polynomial time using s colours on maps whose underlying adjacency graph has no induced subgraph of average degree larger than s/r. However, if s≥3, the problem is NP-hard even if the graph is a for forests of paths of arbitrary lengths (for any r≥2, provided $s < 2r - \sqrt{2r + \frac{1}{4}}+ \frac{3}{2}$ ). Furthermore we obtain a complete characterization of the problem’s complexity for the case when the input graph is a tree, whereas our result for arbitrary planar graphs fall just short of a similar dichotomy. Specifically, we prove that the empire colouring problem is NP-hard for trees, for any r≥2, if 3≤s≤2r?1 (and polynomial time solvable otherwise). For arbitrary planar graphs we prove NP-hardness if s<7 for r=2, and s<6r?3, for r≥3. The result for planar graphs also proves the NP-hardness of colouring with less than 7 colours graphs of thickness two and less than 6r?3 colours graphs of thickness r≥3.     

Computing (r, Q) policy for an inventory system with limited sharable resource

This paper deals with inventory systems with limited resource for a single item or multiple items under continuous review (r, Q) policies. For the single-item system with a stochastic demand and limited resource, it is shown that an existing algorithm can be applied to find an optimal (r, Q) policy that minimizes the expected system costs. For the multi-item system with stochastic demands and limited resource commonly shared among all items, an optimization problem is formulated for finding optimal (r, Q) policies for all items, which minimize the expected system costs. Bounds on the parameters (i.e., r and Q) of the optimal policies and bounds on the minimum expected system costs are obtained. Based on the bounds, an algorithm is developed for finding an optimal or near-optimal solution. A method is proposed for evaluating the quality of the solution. It is shown that the algorithm proposed in this paper finds a solution that is (i) optimal/near-optimal and/or (ii) significantly better than the optimal solution with unlimited resource.     

On an equivalence checking technique for algebraic models of programs

In the paper, the equivalence checking problem for program schemas in balanced semigroup models of programs is studied. A method for constructing algorithms to resolve this problem is proposed in the case where a semigroup model of programs possesses the left cancellation property h ₁ h ₂ = h ₁ h ₃ ? h ₂ = h ₃. The equivalence checking problem is shown to be decidable in time that polynomially depends on size of the schema being checked if the balanced semigroup model of programs possesses additionally the right cancellation property h ₂ h ₁ = h ₃ h ₁ ? h ₂ = h ₃.     

de Bruijn序列查寻表标签的k位修正构造法

de Bruijn序列的结构是一个查寻表,其核心是它的表标签。因此构造出查寻表标签对于生成de Bruijn序列十分重要。给出两种k位修正构造法。方法1为k位提升构造法,即对大部分节点将其第k（k=1,2,…,n-1）位提升一个定值c（1≤c≤m）,来作为该节点的标签。方法2为k位收缩构造法,即对大部分节点将其第k（k=1,2,…,n-1）位向定值r（0≤r≤m）收缩,来作为该节点的标签。这些方法构造的查寻表标签数随着m,n增长而成指数式增长。与定值构造法一样,在局部看是有效的,但与查寻表标签本身数目的惊人增长比较起来就很渺小。方法2与定值标签构造法比较其速度提高了关于m,n的指数式倍。     

The Equivalence Problem of Polynomially Bounded D0L Systems— a Bound Depending Only on the Size of the Alphabet

Abstract. We give a bound for the sequence equivalence problem of polynomially bounded D0L systems which depends only on the size of the underlying alphabet.