Deletion operations: closure properties

Abstract

The paper studies some variants of deletion operations which generalize the left/right quotient of languages. The main emphasis is put on how these deletions can be expressed as a combination of other operations, and on closure properties of various language families under deletion. Some results are the expected ones: the sequential (iterated sequential, dipolar) deletion from a regular language produces a regular set regardless of the complexity of the deleted language. On the other hand, it still remains a challenging open problem whether or not the family of regular languages is closed under iterated parallel deletion with singletons

Keywords:

• Right/left quotient
• sequential deletion
• parallel deletion

C.R Categories:

• F 4.3 [Mathematical Logic and Formal Languages]
• Formal Languages: Operations on languages
• F.4.2 [Mathematical Logic and Formal Languages]
• Grammars and other Rewriting Systems:Grammar types
• D.3.1 [Formal Definitions and Theory]

¹The work reported here is part of the project 11281 of the Academy of Finland

¹The work reported here is part of the project 11281 of the Academy of Finland

Notes

¹The work reported here is part of the project 11281 of the Academy of Finland