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能有效缩短索引建立时间及提高剪枝效率。     

移动对象轨迹时空相似性度量方法

在分析移动对象行为时,移动对象轨迹因包含大量的信息而具有重要的作用。在实际应用中移动对象常受限于空间网络而无法利用现有欧氏空间中轨迹及其距离处理技术。分析了道路网络空间轨迹相似性性质,提出一种移动对象轨迹建模的时空表示方法,能有效地将轨迹从道路网络空间转化到欧氏空间;同时提出了一种基于兴趣点POI（Points Of Interesting）距离的轨迹间相似性测量方法,有效地对轨迹进行化简并减少轨迹中节点的数目,从而降低算法时间复杂度。该方法不仅可以用于搜索相似轨迹,还可方便地应用到轨迹聚类的相关工作中。     

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.