Combining insertion and deletion in RNA-editing preserves regularity

E.P. Vink, de; H. Zantema; D. Bosnacki

doi:10.4204/EPTCS.100.4

Combining insertion and deletion in RNA-editing preserves regularity

E.P. Vink, de, H. Zantema, D. Bosnacki

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

2 Downloads (Pure)

Abstract

Inspired by RNA-editing as occurs in transcriptional processes in the living cell, we introduce an abstract notion of string adjustment, called guided rewriting. This formalism allows simultaneously inserting and deleting elements. We prove that guided rewriting preserves regularity: for every regular language its closure under guided rewriting is regular too. This contrasts an earlier abstraction of RNA-editing separating insertion and deletion for which it was proved that regularity is not preserved. The particular automaton construction here relies on an auxiliary notion of slice sequence which enables to sweep from left to right through a completed rewrite sequence.

Original language	English
Title of host publication	Proceedings of the 6th Workshop on Membrane Computing and Biologically Inspired Process Calculi (McCBIC 2012, Newcastle, UK, September 8, 2012)
Editors	G. Ciobanu
Publisher	EPTCS
Pages	48-62
DOIs	https://doi.org/10.4204/EPTCS.100.4
Publication status	Published - 2012
Event	conference; 6th Workshop on Membrane Computing and Biologically Inspired Process Calculi - Duration: 1 Jan 2012 → …

Publication series

Name	Electronic Proceedings in Theoretical Computer Science
Volume	100
ISSN (Print)	2075-2180

Conference

Conference	conference; 6th Workshop on Membrane Computing and Biologically Inspired Process Calculi
Period	1/01/12 → …
Other	6th Workshop on Membrane Computing and Biologically Inspired Process Calculi

Access to Document

10.4204/EPTCS.100.4

Cite this

Vink, de, E. P., Zantema, H., & Bosnacki, D. (2012). Combining insertion and deletion in RNA-editing preserves regularity. In G. Ciobanu (Ed.), Proceedings of the 6th Workshop on Membrane Computing and Biologically Inspired Process Calculi (McCBIC 2012, Newcastle, UK, September 8, 2012) (pp. 48-62). (Electronic Proceedings in Theoretical Computer Science; Vol. 100). EPTCS. https://doi.org/10.4204/EPTCS.100.4

@inproceedings{3fa6724721ce4c0f8070ee82100b2be1,

title = "Combining insertion and deletion in RNA-editing preserves regularity",

abstract = "Inspired by RNA-editing as occurs in transcriptional processes in the living cell, we introduce an abstract notion of string adjustment, called guided rewriting. This formalism allows simultaneously inserting and deleting elements. We prove that guided rewriting preserves regularity: for every regular language its closure under guided rewriting is regular too. This contrasts an earlier abstraction of RNA-editing separating insertion and deletion for which it was proved that regularity is not preserved. The particular automaton construction here relies on an auxiliary notion of slice sequence which enables to sweep from left to right through a completed rewrite sequence.",

author = "{Vink, de}, E.P. and H. Zantema and D. Bosnacki",

year = "2012",

doi = "10.4204/EPTCS.100.4",

language = "English",

series = "Electronic Proceedings in Theoretical Computer Science",

publisher = "EPTCS",

pages = "48--62",

editor = "G. Ciobanu",

booktitle = "Proceedings of the 6th Workshop on Membrane Computing and Biologically Inspired Process Calculi (McCBIC 2012, Newcastle, UK, September 8, 2012)",

note = "conference; 6th Workshop on Membrane Computing and Biologically Inspired Process Calculi ; Conference date: 01-01-2012",

}

Vink, de, EP , Zantema, H & Bosnacki, D 2012, Combining insertion and deletion in RNA-editing preserves regularity. in G Ciobanu (ed.), Proceedings of the 6th Workshop on Membrane Computing and Biologically Inspired Process Calculi (McCBIC 2012, Newcastle, UK, September 8, 2012). Electronic Proceedings in Theoretical Computer Science, vol. 100, EPTCS, pp. 48-62, conference; 6th Workshop on Membrane Computing and Biologically Inspired Process Calculi, 1/01/12. https://doi.org/10.4204/EPTCS.100.4

Combining insertion and deletion in RNA-editing preserves regularity. / Vink, de, E.P.; Zantema, H.; Bosnacki, D.
Proceedings of the 6th Workshop on Membrane Computing and Biologically Inspired Process Calculi (McCBIC 2012, Newcastle, UK, September 8, 2012). ed. / G. Ciobanu. EPTCS, 2012. p. 48-62 (Electronic Proceedings in Theoretical Computer Science; Vol. 100).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Combining insertion and deletion in RNA-editing preserves regularity

AU - Vink, de, E.P.

AU - Zantema, H.

AU - Bosnacki, D.

PY - 2012

Y1 - 2012

N2 - Inspired by RNA-editing as occurs in transcriptional processes in the living cell, we introduce an abstract notion of string adjustment, called guided rewriting. This formalism allows simultaneously inserting and deleting elements. We prove that guided rewriting preserves regularity: for every regular language its closure under guided rewriting is regular too. This contrasts an earlier abstraction of RNA-editing separating insertion and deletion for which it was proved that regularity is not preserved. The particular automaton construction here relies on an auxiliary notion of slice sequence which enables to sweep from left to right through a completed rewrite sequence.

AB - Inspired by RNA-editing as occurs in transcriptional processes in the living cell, we introduce an abstract notion of string adjustment, called guided rewriting. This formalism allows simultaneously inserting and deleting elements. We prove that guided rewriting preserves regularity: for every regular language its closure under guided rewriting is regular too. This contrasts an earlier abstraction of RNA-editing separating insertion and deletion for which it was proved that regularity is not preserved. The particular automaton construction here relies on an auxiliary notion of slice sequence which enables to sweep from left to right through a completed rewrite sequence.

U2 - 10.4204/EPTCS.100.4

DO - 10.4204/EPTCS.100.4

M3 - Conference contribution

T3 - Electronic Proceedings in Theoretical Computer Science

SP - 48

EP - 62

BT - Proceedings of the 6th Workshop on Membrane Computing and Biologically Inspired Process Calculi (McCBIC 2012, Newcastle, UK, September 8, 2012)

A2 - Ciobanu, G.

PB - EPTCS

T2 - conference; 6th Workshop on Membrane Computing and Biologically Inspired Process Calculi

Y2 - 1 January 2012

ER -

Vink, de EP , Zantema H , Bosnacki D. Combining insertion and deletion in RNA-editing preserves regularity. In Ciobanu G, editor, Proceedings of the 6th Workshop on Membrane Computing and Biologically Inspired Process Calculi (McCBIC 2012, Newcastle, UK, September 8, 2012). EPTCS. 2012. p. 48-62. (Electronic Proceedings in Theoretical Computer Science). doi: 10.4204/EPTCS.100.4

Combining insertion and deletion in RNA-editing preserves regularity

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this