Parallelisable Regular Languages Recognisability and Properties

Abstract

Parallel programming is an attractive solution approach for certain types of computing problems that are best handled by the use of multiprocessors. The main idea behind parallel programming is to save time by enabling the execution of applications in a shorter time. We have introduced the process of parallelisation on sequential strings and languages. Parallelisation of a string is a process by which a string is divided into a finite number of substrings and this happens only on strings of length greater than one. We have defined parallelisable string and parallelisable language over an alphabet or symbols. Parallelisable languages have been arrived at by finding common substrings of length more than one.Regular expression for parallelisable languages has been defined by including parallelismof regular expressions. Parallelisable regular languages have also been introduced and defined. Finite automaton is an abstract model to accept strings and languages. newlineWe have defined a parallelisable finite automaton to accept parallelisable languages newlineand studied their properties. Parallelisable finite automaton incorporates a new newlinetransition function called fork-join transition within a finite automaton to read parallel newlinestrings. Equivalence between finite automaton and parallelisable finite automaton hasbeen established.We have extended finite parallelisable regular languages to infinite parallelisable regular languages. Parallelisable B¨uchi automaton has been introduced by combining B¨uchi automaton and parallelisable finite automaton. We have derived the closure and language theoretical properties of infinite parallelisable regular languages.Another way of describing regular languages is by means of certain grammars. Whenever a language family is defined through an automaton, we are interested in knowing the grammar that is associated with the family. We have defined Parallelisable grammar and parallelisable derivation trees for parallelisable languages.We have introduced parallelisable string-based SP- languages as the u