5 papers
A Computation Model with Automatic Functions and Relations as Primitive Operations
Ziyuan Gao, Sanjay Jain, Li Zeyong +2
Prior work of Hartmanis and Simon (Hartmanis and Simon, 1974) and Floyd and Knuth (Floyd and Knuth, 1990) investigated what happens if a device uses primitive steps more natural th…
An Exact Algorithm for finding Maximum Induced Matching in Subcubic Graphs
Gordon Hoi, Ammar Fathin Sabili, Frank Stephan
The Maximum Induced Matching problem asks to find the maximum such that, given a graph , can we find a subset of vertices of size for which every vertices …
Addition Machines, Automatic Functions and Open Problems of Floyd and Knuth
Sanjay Jain, Xiaodong Jia, Ammar Fathin Sabili +1
Floyd and Knuth investigated in 1990 register machines which can add, subtract and compare integers as primitive operations. They asked whether their current bound on the number of…
Alternating Automatic Register Machines
Ziyuan Gao, Sanjay Jain, Zeyong Li +2
This paper introduces and studies a new model of computation called an Alternating Automatic Register Machine (AARM). An AARM possesses the basic features of a conventional registe…
Induction Models on \mathbb{N}
A. Dileep, Kuldeep S. Meel, Ammar F. Sabili
Mathematical induction is a fundamental tool in computer science and mathematics. Henkin initiated the study of formalization of mathematical induction restricted to the setting wh…