首页 | 本学科首页   官方微博 | 高级检索  
     


Deletion along trajectories
Authors:Michael Domaratzki
Affiliation:

School of Computing, Queen's University, Kingston, Ont., Canada K7L 3N6

Abstract:We describe a new way to model deletion operations on formal languages, called deletion along trajectories. We examine its closure properties, which differ from those of shuffle on trajectories, previously introduced by Mateescu et al. In particular, we define classes of non-regular sets of trajectories such that the associated deletion operation preserves regularity. Our results give uniform proofs of closure properties of the regular languages for several deletion operations.

We also show that deletion along trajectories serves as an inverse to shuffle on trajectories. This leads to results on the decidability of certain language equations, including those of the form LTX=R, where L,R are regular languages and X is unknown.

Keywords:Deletion along trajectories   Shuffle on trajectories   Language equations   Regular languages
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号