Deterministic finite H-Automata and $omega$-regular partial languages

Print   Print  

Authors :

R. Arulprakasama,* V.R. Dareb and S. Gnanasekaranc

Author Address :

aDepartment of Mathematics, SRM University, Kattankulathur-603 203, Kancheepuram-Dt, Tamilnadu, India.
bDepartment of Mathematics, Madras Christian College, Tambaram, Chennai-600 059, Tamilnadu, India.
cDepartment of Mathematics, Periyar Arts College, Cuddalore-607 001, Tamilnadu, India.

*Corresponding author.

Abstract :

Partial words, that is, finite words with holes, were introduced in the 70s by Fischer and Paterson, with respect to bioinformatics applications. Infinite partial words were introduced later. Recently, Dassow et al.’s connected partial words and regular languages. In this paper, we extend the local partial languages to local $omega$-partial languages and study their closure properties. We introduce the subclass of $omega$-regular partial languages called B$ddot{u}$chi local $omega$-partial languages and we define deterministic finite H-automaton with acceptance condition on $omega$-partial words and deterministic finite H-local automaton. Further, we establish relationships between deterministic finite H-local automaton, local $omega$-partial languages and B$ddot{u}$chi local $omega$-partial languages. Finally, we show that every $omega$-regular partial languages is a projection of a B$ddot{u}$chi local $omega$-partial languages.

Keywords :

Partial word, infinite partial word, local partial languages, partial finite automaton, regular partial languages.

DOI :

Article Info :

Received : August 15, 2013; Accepted : September 01, 2013.