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 finding better algorithms for active learning of one-counter automata. 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 Nov 2024)

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:

In this paper, we introduce a novel method for active learning of deterministic real-time one-counter automata (DROCA). The existing techniques for learning DROCA rely on observing the behaviour of the DROCA up to exponentially large counter-values. Our algorithm eliminates this need and requires only a polynomial number of queries. Additionally, our method differs from existing techniques as we learn a minimal counter-synchronous DROCA, resulting in much smaller counter-examples on equivalence queries. Learning a minimal counter-synchronous automaton cannot be done in polynomial time unless $P = NP$, even in the case of visibly one-counter automata. We use a SAT solver to overcome this difficulty. The solver is used to compute a minimal separating DFA from a given set of positive and negative samples. We prove that the equivalence of two counter-synchronous DROCAs can be checked significantly faster than that of general DROCAs. For visibly one-counter automata, we have discovered an even faster algorithm for equivalence checking. We implemented the proposed learning algorithm and tested it on randomly generated DROCAs. Our evaluations show that the proposed method outperforms the existing techniques on the test set.

See publication
Abstract:

In this paper, we are interested in weighted one-counter automata whose transitions are assigned a weight from a fixed field. In particular, we consider deterministic weighted real-time one-counter automaton (DWROCA). A DWROCA is a deterministic real-time one-counter automaton whose transitions are assigned a weight. Two DWROCAs are equivalent if every word accepted by one is accepted by the other with the same weight. DWROCA is a sub-class of weighted one-counter automata with counter determinacy. It is known that the equivalence problem for this model is in P. This paper gives a simpler proof for checking the equivalence of two DWROCAs. This gives a better polynomial-time algorithm for checking the equivalence of DWROCAs.

See publication
Full version (arXiv)
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:

In this presentation, we introduce a novel method for active learning of a minimal-sized visibly one-counter automaton (VOCA) using SAT solver. We follow Angluin's L* algorithm. The algorithm uses only a polynomial number of membership or equivalence queries. All the existing literature, including the algorithm presented by Neider and Löding for learning VOCA, requires exponentially many queries relative to the size of a minimal VOCA recognising the given language. Our approach eliminates the necessity to observe the VOCAs behaviour up to exponentially large counter values. This sets it apart from existing techniques that rely on identifying repetitive patterns in behaviour graphs of exponential size. Michaliszyn and Otop observed that the problem of finding the minimal VOCA is NP-Complete. If a polynomial time algorithm for learning the minimal VOCA exists, it could be employed to minimise VOCA in polynomial time. Consequently, a learning algorithm for VOCA that achieves minimal representation in polynomial time does not exist. In the latter part of the work, we looked at learning Deterministic real-time one-counter automata (DROCA). However, we make use of an additional query, called counter-value query - the student gives the teacher a word, and the teacher returns the counter-value reached on traversing the word in the DROCA. We show that learning DROCA can done using polynomially many queries within this framework. This improves the existing result by Bruyère et al. that needed an exponential number of queries, space and time for learning DROCA.

Watch Talk
Slides
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