Prince Mathew

PhD Scholar, Indian Institute of Technology, Goa

     
  •  
  •  
  •  
  •    
  •  
  •  

I am pursuing my PhD in Theoretical Computer Science under the guidance of Dr. Sreejith A V in the School of Mathematics and Computer Science at Indian Institute of Technology, Goa. Currently, research focused on learning push-down automata by modifying Angluin's L* algorithm. A prior research endeavour established that the problems of Equivalence, Regularity, and Covering of Weighted-one-counter automata (over fields) with counter determinacy can be solved in polynomial time.

Research Interests:
Automata Theory • Formal methods in Computer Science • Machine Learning •

Download CV (updated Feb 2023)

Experience

Junior Research Fellow

Indian Institute of Technology, Goa

Feb 2018 - Dec 2018

Senior Engineer

Tata Elxsi, Trivandrum
Jan 2017 - Jan 2018

Guest Lecturer

Central Polytechnic College, Trivandrum
Jun 2016 - Oct 2016

Education

PhD in Theoretical Computer Science

Indian Institute of Technology, Goa
2019 - Present

PhD Coursework

Chennai Mathematical Institute, Tamil Nadu
2020 - 2020

M.Tech in Computer Science and Engineering

College of Engineering Trivandrum, Kerala
2014 - 2016

B.Tech in Computer Science and Engineering

Saintgits Engineering College, Kottayam, Kerala
2010 - 2014

10+2

Don Bosco Higher Secondary School, Kottayam, Kerala
1995 - 2010

Publications

Abstract:

We introduce weighted one-deterministic-counter automata (odca). These are weighted one-counter automata (oca) with the property of counter-determinacy, meaning that all paths labelled by a given word starting from the initial configuration have the same counter-effect. Weighted odcas are a strict extension of weighted visibly ocas, which are weighted ocas where the input alphabet determines the actions on the counter. We present a novel problem called the co-VS (complement to a vector space) reachability problem for weighted odcas over fields, which seeks to determine if there exists a run from a given configuration of a weighted odca to another configuration whose weight vector lies outside a given vector space. We establish two significant properties of witnesses for co-VS reachability: they satisfy a pseudo-pumping lemma, and the lexicographically minimal witness has a special form. It follows that the co-VS reachability problem is in 𝖯. These reachability problems help us to show that the equivalence problem of weighted odcas over fields is in 𝖯 by adapting the equivalence proof of deterministic real-time ocas [Stanislav Böhm and Stefan Göller, 2011] by Böhm et al. This is a step towards resolving the open question of the equivalence problem of weighted ocas. Finally, we demonstrate that the regularity problem, the problem of checking whether an input weighted odca over a field is equivalent to some weighted automaton, is in 𝖯. We also consider boolean odcas and show that the equivalence problem for (non-deterministic) boolean odcas is in PSPACE, whereas it is undecidable for (non-deterministic) boolean ocas.

See publication
Full version (arXiv)
Abstract:

This paper proposes an efficient classifier based on continuous cellular automata with promising running time and classification accuracy. The classifier model is capable of processing data sets containing large number of numeric as well as non-numeric attributes. It performs effective pre-processing of numeric and nominal attributes to identify the most relevant ones. It also prunes out unnecessary computations by limiting stabilisation of the cellular automata during the training phase. The classifier also employs various techniques to reduce the number of incorrect classifications and overfitting of data. A number of experiments were conducted to evaluate the performance of the proposed classifier by changing various parameters during the training phase. Evaluations show that the classifier out-performs existing rule-based classifiers in terms of accuracy.

See publication
Abstract:

The ability to understand music score is a basic requirement for learning music. This paper proposes a mathematical method to find the pitch of a musical note from digital image of sheet music and a classification-based method for detecting the duration of a music note. In a sheet music, the horizontal direction can be associated with the notes starting time, whilst the vertical direction can be associated with pitch. The symbols used for a note represents its duration. Music scores sometimes need to be transposed or slightly modified, having the score in a digital format greatly reduces the time and effort required to do these. In this paper, we make use of techniques such as Run Length Encoding (RLE), Horizontal projection and Vertical Projection (X & Y projections) for Segmentation and attribute extraction. For note recognition, a classifier based system is used which returns the duration of the given input symbol. The pitch, duration and position of notes are finally given as input to a midi generation module, which generates a MIDI file corresponding to the given input music notation. There are several other applications to Optical Music Recognition (OMR) systems. Converting music scores in Braille code for the blind is yet another application of an OMR system.

See publication
Abstract:

Classification is one among the most studied supervised learning techniques. There are a variety of classifiers and classifying algorithms. Fuzzy Classifiers are classifiers which deals with varying degrees of membership, unlike crisp classifiers which have only a true or false value for membership of an instance to a class. Cellular Automata is one of the ways of performing computations which necessitates extremely the processing of data at a high speed. The use of cellular automata in classification is a promising area of study. Using Continuous Cellular Automata helps us to incorporate the concept of fuzziness into the Classifier using Cellular Automata. This survey studies the basic concept of fuzzy logic, cellular automata and the types of neighbourhood & diffusion rules in use, examines the concept of Continuous cellular automata and describes various defuzzification processes in brief. We also study an existing fuzzy classifier using continuous cellular automata and its working.

See publication

Recorded Talks

Abstract:

We introduce weighted one-deterministic-counter automata (odca). These are weighted one-counter automata (oca) with the property of counter-determinacy, meaning that all paths labelled by a given word starting from the initial configuration have the same counter-effect. Weighted odcas are a strict extension of weighted visibly ocas, which are weighted ocas where the input alphabet determines the actions on the counter. We present a novel problem called the co-VS (complement to a vector space) reachability problem for weighted odcas over fields, which seeks to determine if there exists a run from a given configuration of a weighted odca to another configuration whose weight vector lies outside a given vector space. We establish two significant properties of witnesses for co-VS reachability: they satisfy a pseudo-pumping lemma, and the lexicographically minimal witness has a special form. It follows that the co-VS reachability problem is in 𝖯. These reachability problems help us to show that the equivalence problem of weighted odcas over fields is in 𝖯 by adapting the equivalence proof of deterministic real-time ocas [Stanislav Böhm and Stefan Göller, 2011] by Böhm et al. This is a step towards resolving the open question of the equivalence problem of weighted ocas. Finally, we demonstrate that the regularity problem, the problem of checking whether an input weighted odca over a field is equivalent to some weighted automaton, is in 𝖯. We also consider boolean odcas and show that the equivalence problem for (non-deterministic) boolean odcas is in PSPACE, whereas it is undecidable for (non-deterministic) boolean ocas.

Watch Talk (starts at 2:45:00)
Abstract:

We introduce One-deterministic-counter automata (ODCA), one-counter automata where all runs labeled by a given word exhibit the same counter effect. The talk will specifically focus on weighted ODCAs. We present a novel problem known as the co-VS (complement to a vector space) reachability problem. By leveraging properties of matrices and vector spaces, a pseudo-pumping lemma is established, proving that the Co-VS reachability problem is in P. Furthermore, we demonstrate that the lexicographically minimal witness for this problem has a special form. Consequently, it follows that the equivalence problem of ODCAs is also in P. This is joint work with Dr. Sreejith A.V., Dr. Vincent Penelle, and Dr. Prakash Saivasan.

Watch Talk
Abstract:

We introduce one deterministic-counter automata (ODCA), which are one-counter automata where all runs labelled by a given word have the same counter effect, a property we call counter-determinacy. ODCAs are an extension of visibly one-counter automata - one-counter automata (OCA), where the input alphabet determines the actions on the counter. They are a natural way to introduce non-determinism/weights to OCAs while maintaining the decidability of crucial problems that are undecidable on general OCAs. For example, the equivalence problem is decidable for deterministic OCAs, whereas it is undecidable for non-deterministic OCAs. We consider both non-deterministic and weighted ODCAs. Our work shows that the equivalence problem is decidable in polynomial time for weighted ODCAs over a field and polynomial space for non-deterministic ODCAs. As a corollary, we get that the regularity problem, i.e., the problem of checking whether an input weighted ODCA is equivalent to some weighted automaton, is also in polynomial time. Furthermore, we show that the covering and coverable equivalence problems for uninitialised weighted ODCAs are decidable in polynomial time. We also introduce a few reachability problems that are of independent interest and show that they are in P. These reachability problems later help in solving the equivalence problem.

Watch Talk (starts at 18:50)

Projects

Angluin-style learning algorithm for Deterministic Real-time and Visibly One-Counter Automata. This work was done as a part of my PhD.

Web application for MoES for calculating water discharge in rivers from satellite images. This work was done as a part of a joint project with Dr. Sreejith A.V (IIT Goa) and Dr. Gaurav Kumar (IISER Bhopal).

Web application to manage employee profiles of Tata Elxsi. The application manages project allocation, training, funnel management, performance evaluations, and resume creation. It helps assign projects based on employee skills, plan and track training, search for employees, assess performance, and create resumes.

Project done as part of Masters degree thesis. Developed a Continuous Cellular Automata based fuzzy classifier in Java using Weka.

Thesis: click here
Code: click here

Undergraduate Project. Java based image processing tool to recognize musical notes from image of sheet music and convert it into a MIDI file.

Report: click here
Code: click here

Teaching Assistance

CS101
Introduction to Computing
Spring 2020-21 • Autumn 2023-24
CS525
Randomized Algorithms
Spring 2022-23
CS102
Software Tools
Spring 2022-23
CS220
Data Structures and Algorithms
Autumn 2022-23 • Summer 2022 • Autumn 2021-22 • Autumn 2020-21
CS310
Automata Theory
Spring 2020-21 • Spring 2018-19
CS315
Logic in Computer Science
Autumn 2019-20
CS315
Advanced Algorithms
Spring 2018-19