1. Hierarchies in Regular Languages
Prerequisites:
1) Theory of Computation (CS F351) course.
2) Solve the following problem:
Consider a restricted model of a Deterministic Turing Machine (we call it DTM(1, 1)) which works in two phases. In the first phase, DTM(1, 1) continuously moves to the right, possibly scanning the cells, overwriting the cells, and changing states according to its transition function like a normal DTM, until it reaches the end of its input. Now phase 2 starts in which DTM(1, 1) continuously moves to the left, possibly scanning the cells, overwriting the cells, and changing states according to its transition function like a normal DTM, until it reaches the start of its input. Prove or disprove:
The set of languages accepted by DTM(1, 1) is exactly the set of Regular languages.
References:
[1] J. E. Pin, Open Problems About Regular Languages, 35 Years Later, The Role of Theory in Computer Science, 153--175 (2017).
2. Fault Tolerant Task Scheduling
This project is a joint work with Prof. Kamal Sheel Mishra of School of Management Sciences, Varanasi.
Prerequisites:
1) Data Structures and Algorithms (CS F211) course.
2) Correct implementation of the ``Optimal Clustering Algorithm'' as given in Chapter 5 of the following Thesis:
https://drive.google.com/file/d/1YdAIFvKe9iIY4sEo95iHykB1ULuhGHEB/view?usp=sharing
References:
[1] K.S. Mishra, A.K. Tripathi, ``Task Scheduling of a Distributed Computing Software in the Presence of Faults'', International Journal of Computer Applications (0975 - 8887) Volume 72 - No. 13, June 2013.
https://research.ijcaonline.org/volume72/number13/pxc3888925.pdf
[2] K.S. Mishra, A.K. Tripathi, Task Scheduling of Special Types of Distributed Software in the Presence of Communication and Computation Faults, International Journal Of Engineering And Computer Science, ISSN:2319-7242, Volume 3, Issue 10, October,2014, Page No.8752-8764.
http://www.ijecs.in/index.php/ijecs/article/view/1892/1752
An Institute of Eminence
