1-Normal DRA for insertion languages

Title

1-Normal DRA for insertion languages

Creator

Midya A.; Kuppusamy L.; Sumitha V.S.; Pani A.K.

Description

Restarting automaton is a type of regulated rewriting system, introduced as a model for analysis by reduction. It is a linguistically motivated method for checking the correctness of a sentence. In this paper, we introduce a new definition of normal restarting automaton in which only one substring is removed using the DEL operation in a cycle. This DEL operation is applied to reverse the insertion operation in an insertion grammar. We use this 1-normal restarting automaton to solve the membership problem of insertion languages. Further, we introduce some interesting closure properties of 1-normal restarting automata. 2017, Springer International Publishing AG.

Source

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol-10398 LNCS, pp. 10-19.

Date

2017-01-01

Publisher

Springer Verlag

Subject

Insertion grammars; Membership problem; Restarting automaton

Coverage

Midya A., Computer Science & Engineering, ICFAI Tech School, Hyderabad, 501203, India; Kuppusamy L., Theoretical Computer Science Lab, School of Computer Science and Engineering, VIT University, Vellore, 632014, India; Sumitha V.S., Computer Science and Engineering, Christ University Faculty of Engineering, Bangalore, 560074, India; Pani A.K., Computer Science and Engineering, Christ University Faculty of Engineering, Bangalore, 560074, India

Rights

Restricted Access

Relation

ISSN: 3029743; ISBN: 978-331964418-9

Format

Online

Language

English

Type

Conference paper

Identifier

https://doi.org/10.1007/978-3-319-64419-6_2

https://www.scopus.com/inward/record.uri?eid=2-s2.0-85028697411&doi=10.1007%2f978-3-319-64419-6_2&partnerID=40&md5=70f792a8a44928c48f915f1ea5a38353