Complexity of guided insertion-deletion in RNA-editing

H. Zantema

doi:10.1007/978-3-642-13089-2_51

Complexity of guided insertion-deletion in RNA-editing

H. Zantema

Formal System Analysis

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

3 Citations (Scopus)

4 Downloads (Pure)

Abstract

Inspired by RNA-editing, we study an elementary formalism of string replacement based on insertion and deletion using a fixed finite set of guides, and in which only occurrences of a single symbol are inserted or deleted. While in this replacement mechanism computation lengths are at most exponential by construction, we show that this exponential upper bound is tight. Moreover, we show that both the class of regular languages and the class of context-free languages are not closed under this replacement mechanism.

Original language	English
Title of host publication	Language and Automata Theory and Applications (4th International Conference, LATA 2010, Trier, Germany, May 24-28, 2010. Proceedings)
Editors	A.H. Dediu, H. Fernau, C. Martin-Vide
Place of Publication	Berlin
Publisher	Springer
Pages	608-619
ISBN (Print)	978-3-642-13088-5
DOIs	https://doi.org/10.1007/978-3-642-13089-2_51
Publication status	Published - 2010

Publication series

Name	Lecture Notes in Computer Science
Volume	6031
ISSN (Print)	0302-9743

Access to Document

10.1007/978-3-642-13089-2_51

Cite this

Zantema, H. (2010). Complexity of guided insertion-deletion in RNA-editing. In A. H. Dediu, H. Fernau, & C. Martin-Vide (Eds.), Language and Automata Theory and Applications (4th International Conference, LATA 2010, Trier, Germany, May 24-28, 2010. Proceedings) (pp. 608-619). (Lecture Notes in Computer Science; Vol. 6031). Springer. https://doi.org/10.1007/978-3-642-13089-2_51

@inproceedings{c6be711487c643f3a13969e429e2b40e,

title = "Complexity of guided insertion-deletion in RNA-editing",

abstract = "Inspired by RNA-editing, we study an elementary formalism of string replacement based on insertion and deletion using a fixed finite set of guides, and in which only occurrences of a single symbol are inserted or deleted. While in this replacement mechanism computation lengths are at most exponential by construction, we show that this exponential upper bound is tight. Moreover, we show that both the class of regular languages and the class of context-free languages are not closed under this replacement mechanism.",

author = "H. Zantema",

year = "2010",

doi = "10.1007/978-3-642-13089-2\_51",

language = "English",

isbn = "978-3-642-13088-5",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "608--619",

editor = "A.H. Dediu and H. Fernau and C. Martin-Vide",

booktitle = "Language and Automata Theory and Applications (4th International Conference, LATA 2010, Trier, Germany, May 24-28, 2010. Proceedings)",

address = "Germany",

}

Zantema, H 2010, Complexity of guided insertion-deletion in RNA-editing. in AH Dediu, H Fernau & C Martin-Vide (eds), Language and Automata Theory and Applications (4th International Conference, LATA 2010, Trier, Germany, May 24-28, 2010. Proceedings). Lecture Notes in Computer Science, vol. 6031, Springer, Berlin, pp. 608-619. https://doi.org/10.1007/978-3-642-13089-2_51

Complexity of guided insertion-deletion in RNA-editing. / Zantema, H.
Language and Automata Theory and Applications (4th International Conference, LATA 2010, Trier, Germany, May 24-28, 2010. Proceedings). ed. / A.H. Dediu; H. Fernau; C. Martin-Vide. Berlin: Springer, 2010. p. 608-619 (Lecture Notes in Computer Science; Vol. 6031).

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

TY - GEN

T1 - Complexity of guided insertion-deletion in RNA-editing

AU - Zantema, H.

PY - 2010

Y1 - 2010

N2 - Inspired by RNA-editing, we study an elementary formalism of string replacement based on insertion and deletion using a fixed finite set of guides, and in which only occurrences of a single symbol are inserted or deleted. While in this replacement mechanism computation lengths are at most exponential by construction, we show that this exponential upper bound is tight. Moreover, we show that both the class of regular languages and the class of context-free languages are not closed under this replacement mechanism.

AB - Inspired by RNA-editing, we study an elementary formalism of string replacement based on insertion and deletion using a fixed finite set of guides, and in which only occurrences of a single symbol are inserted or deleted. While in this replacement mechanism computation lengths are at most exponential by construction, we show that this exponential upper bound is tight. Moreover, we show that both the class of regular languages and the class of context-free languages are not closed under this replacement mechanism.

U2 - 10.1007/978-3-642-13089-2_51

DO - 10.1007/978-3-642-13089-2_51

M3 - Conference contribution

SN - 978-3-642-13088-5

T3 - Lecture Notes in Computer Science

SP - 608

EP - 619

BT - Language and Automata Theory and Applications (4th International Conference, LATA 2010, Trier, Germany, May 24-28, 2010. Proceedings)

A2 - Dediu, A.H.

A2 - Fernau, H.

A2 - Martin-Vide, C.

PB - Springer

CY - Berlin

ER -

Complexity of guided insertion-deletion in RNA-editing

Abstract

Publication series

Access to Document

Fingerprint

Cite this