Codes defined by multiple sets of trajectories

We investigate the use of shuffle on trajectories to model certain classes of languages arising in the theory of codes. In particular, for each finite set of sets of trajectories, which we call a hyperset of trajectories, we define a class of languages induced by that hyperset of trajectories. We investigate the properties of hypersets of trajectories and the associated classes of languages, including the problem of decidability of membership and the problem of equivalence of hypersets of trajectories.     

Shuffle languages are in P

In this paper we show that shuffle languages are contained in one-way-NSPACE(log n) thus in P. We consider the class of shuffle languages which emerges from the class of finite languages through regular operations (union, concatenation, Kleene star) and shuffle operations (shuffle and shuffle closure). For every shuffle expression E we construct a shuffle automaton which accepts the language generated by E and we show that the automaton can be simulated by a one-way nondeterministic Turing machine in logarithmic space.     

Control of a three-link manipulator with inequality constraints on the trajectories of its joints

This work deals with the control of a three-link planar manipulator whose motion is subjected to inequality constraints on the trajectories of its joints, and to other constraints on the trajectory of its end-effector.     

Equations over sets of integers with addition only

Systems of equations of the form $X=Y+Z$ and $X=C$ are considered, in which the unknowns are sets of integers, the plus operator denotes element-wise sum of sets, and C is an ultimately periodic constant. For natural numbers, such equations are equivalent to language equations over a one-symbol alphabet using concatenation and regular constants. It is shown that such systems are computationally universal: for every recursive (r.e., co-r.e.) set $S\subseteq \mathbb{N}$ there exists a system with a unique (least, greatest) solution containing a component T with $S=\{n|16n+13\in T\}$. Testing solution existence for these equations is ${\mathrm{\Pi }}_1^0$-complete, solution uniqueness is ${\mathrm{\Pi }}_2^0$-complete, and finiteness of the set of solutions is ${\mathrm{\Sigma }}_3^0$-complete. A similar construction for integers represents any hyper-arithmetical set $S\subseteq \mathbb{Z}$ by a set $T\subseteq \mathbb{Z}$ satisfying $S=\{n|16n\in T\}$, whereas testing solution existence is ${\mathrm{\Sigma }}_1^1$-complete.     

Lagrange-type extremal trajectories in differential inclusions

Necessary conditions for optimal, or boundary solutions of differential inclusions usually state that such solutions are extremal in some sense. There are several possible concepts of extremality, which lead to different, often difficult to compare necessary conditions. In this paper, we give a complete comparison of three classes of extremal trajectories: two different Lagrange-type extremals, and Hamiltonian extremals. In the second part, we consider a nonconvex differential inclusion, and prove that every boundary trajectory is a Lagrangian extremal.     

海量活动轨迹相似查询

活动轨迹的近似查询是在带关键词信息的轨迹集中,检索与查询点集距离最近且满足查询点集关键词要求的活动轨迹的过程。因为GAT（Grid index for Activity Trajectories）不能查询海量活动轨迹,将GAT扩展到适用于海量活动轨迹的近似查询技术GATH（GAT on Hadoop）。和GAT相比,GATH使用两种新的索引结构进行剪枝;其网格索引依照海量数据的特点从底层单元格开始进行基于空间的剪枝;其倒排索引用于进行基于关键词的剪枝。实验结果证实GATH比GAT能有效缩短索引建立时间及提高剪枝效率。     

Equality sets of prefix morphisms and regular star languages

We consider equality sets of prefix morphisms, that is, sets E(g₁,g₂)={w|g₁(w)=g₂(w)}, where g₁ and g₂ are prefix morphisms. Recall that a morphism g is prefix if, for all different letters a and b, g(a) is not a prefix of g(b). We prove a rather surprising equality on families of languages, namely, that the family of regular star languages coincides with the family of languages of form πA(E(g₁,g₂)) for some prefix morphisms g₁ and g₂, and a projection πA which deletes the letters not in A.     

Regular patterns, regular languages and context-free languages

In this paper we consider two questions. First we consider whether every pattern language which is regular can be generated by a regular pattern. We show that this is indeed the case for extended (erasing) pattern languages if alphabet size is at least four. In all other cases, we show that there are patterns generating a regular language which cannot be generated by a regular pattern. Next we consider whether there are pattern languages which are context-free but not regular. We show that, for alphabet size 2 and 3, there are both erasing and non-erasing pattern languages which are context-free but not regular. On the other hand, for alphabet size at least 4, every erasing pattern language which is context-free is also regular. It is open at present whether there exist non-erasing pattern languages which are context-free but not regular for alphabet size at least 4.