Title :
Restarting automata for insertion languages
Author :
Kuppusamy, Lakshmanan ; Midya, A.
Author_Institution :
Sch. of Comput. Sci. & Eng., VIT Univ., Vellore, India
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.
Keywords :
automata theory; rewriting systems; 1-normal DRA; DEL operation; analysis by reduction; clearing restarting automaton; insertion grammar; insertion languages; insertion rule; membership problem; normal restarting automaton; regulated rewriting system; restarting automaton with delete; Analytical models; Automata; Computational modeling; Context; Educational institutions; Grammar; Pragmatics;
Conference_Titel :
Engineering (NUiCONE), 2013 Nirma University International Conference on
Conference_Location :
Ahmedabad
Print_ISBN :
978-1-4799-0726-7
DOI :
10.1109/NUiCONE.2013.6780082
