Header menu link for other important links
X
Restarting automata for insertion languages
Kuppusamy L, , Midya A.
Published in IEEE
2013
Abstract
Restarting automaton is a type of regulated rewriting system, introduced as a model for analysis by reduction. It is linguistically motivated method for checking correctness of a sentence. In this paper, we introduce a new definition of normal restarting automaton, called 1-normal DRA in which only one substring can be removed using DEL operation in a cycle. This DEL operation is used to reverse the insertion of an insertion rule in an insertion grammar. We use this 1-normal restarting automaton to solve the membership problem of insertion languages. Also the comparison of the power of 1-normal DRA and clearing restarting automaton is addressed in this paper. Index Terms: Insertion grammars, membership problem, Restarting automaton. © 2013 IEEE.
About the journal
JournalData powered by Typeset2013 Nirma University International Conference on Engineering (NUiCONE)
PublisherData powered by TypesetIEEE
Open Access0