TY - GEN
T1 - Representations and characterizations of languages in chomsky hierarchy by means of insertion-deletion systems
AU - Pǎun, Gheorghe
AU - Pérez-Jiménez, Mario J.
AU - Yokomori, Takashi
PY - 2007/1/1
Y1 - 2007/1/1
N2 - Insertion-deletion operations are much investigated in linguistics and in DNA computing and several characterizations of Turing computability were obtained in this framework. In this note we contribute to this research direction with a new characterization of this type, as well as with representations of regular and context-free languages, mainly starting from context-free insertion systems of as small as possible complexity. For instance, each recursively enumerable language L can be represented in a way similar to the celebrated Chomsky-Scḧutzenberger representation of context-free languages, i.e., in the form L = h(L(γ) ∩D), where is an insertion system of weight (3, 0) (at most three symbols are inserted in a context of length zero), h is a projection, and D is a Dyck language. A similar representation can be obtained for regular languages, involving insertion systems of weight (2,0) and star languages, as well as for context-free languages - this time using insertion systems of weight (3, 0) and star languages.
AB - Insertion-deletion operations are much investigated in linguistics and in DNA computing and several characterizations of Turing computability were obtained in this framework. In this note we contribute to this research direction with a new characterization of this type, as well as with representations of regular and context-free languages, mainly starting from context-free insertion systems of as small as possible complexity. For instance, each recursively enumerable language L can be represented in a way similar to the celebrated Chomsky-Scḧutzenberger representation of context-free languages, i.e., in the form L = h(L(γ) ∩D), where is an insertion system of weight (3, 0) (at most three symbols are inserted in a context of length zero), h is a projection, and D is a Dyck language. A similar representation can be obtained for regular languages, involving insertion systems of weight (2,0) and star languages, as well as for context-free languages - this time using insertion systems of weight (3, 0) and star languages.
KW - Context-free languages
KW - Insertion-deletion systems
KW - Recursively enumerable languages
KW - Regular languages
UR - http://www.scopus.com/inward/record.url?scp=84905842130&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84905842130&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:84905842130
SN - 9788070976883
T3 - Descriptional Complexity of Formal Systems - 9th International Workshop, DCFS 2007
SP - 129
EP - 140
BT - Descriptional Complexity of Formal Systems - 9th International Workshop, DCFS 2007
PB - Technical University of Kosice
T2 - 9th International Workshop on Descriptional Complexity of Formal Systems, DCFS 2007
Y2 - 20 July 2007 through 22 July 2007
ER -