Electronic Thesis and Dissertation Repository

Degree

Doctor of Philosophy

Program

Computer Science

Supervisor

Lila Kari

Abstract

In this thesis, we consider several research questions related to language operations in the following areas of automata and formal language theory: reversibility of operations, generalizations of (comma-free) codes, generalizations of basic operations, language equations, and state complexity.

Motivated by cryptography applications, we investigate several reversibility questions with respect to the parallel insertion and deletion operations. Among the results we obtained, the following result is of particular interest. For languages L1, L2 ⊆ Σ∗, if L2 satisfies the condition L2ΣL2 ∩ Σ+L2Σ+ = ∅, then any language L1 can be recovered after first parallel-inserting L2 into L1 and then parallel-deleting L2 from the result. This property reminds us of the definition of comma-free codes. Following this observation, we define the notions of comma codes and k-comma codes, and then generalize them to comma intercodes and k-comma intercodes, respectively. Besides proving all these new codes are indeed codes, we obtain some interesting properties, as well as several hierarchical results among the families of the new codes and some existing codes such as comma-free codes, infix codes, and bifix codes.

Another topic considered in this thesis are some natural generalizations of basic language operations. We introduce block insertion on trajectories and block deletion on trajectories, which properly generalize several sequential as well as parallel binary language operations such as catenation, sequential insertion, k-insertion, parallel insertion, quotient, sequential deletion, k-deletion, etc. We obtain several closure properties of the families of regular and context-free languages under the new operations by using some relationships between these new operations and shuffle and deletion on trajectories. Also, we obtain several decidability results of language equation problems with respect to the new operations.

Lastly, we study the state complexity of the following combined operations: L1L2∗, L1L2R, L1(L2 ∩ L3), L1(L2 ∪ L3), (L1L2)R, L1∗L2, L1RL2, (L1 ∩ L2)L3, (L1 ∪ L2)L3, L1L2 ∩ L3, and L1L2 ∪ L3 for regular languages L1, L2, and L3. These are all the combinations of two basic operations whose state complexities have not been studied in the literature.

Download

Share

COinS