|
| << vorige | volgende >> |
Tijdschrift beschrijving
Alle jaargangen van het bijbehorende tijdschrift
Alle afleveringen van het bijbehorende jaargang
Alle artikelen van de bijbehorende aflevering
Details van artikel 2 van 4 gevonden artikelen
| Titel: |
Conditional Concatenation |
| Auteur: |
Jürgen Dassow Carlos Martín-Vide Gheorghe Păun Alfonso Rodríguez-Patón |
| Verschenen in: |
Fundamenta informaticae |
| Paginering: | Jaargang 44 (2003) nr. 4 pagina's 353-372 |
| Jaar: |
2003-07-11 |
| Inhoud: |
Inspired from biochemistry and DNA computing, we introduce several variants of controlled concatenation of strings and languages: a finite set of pairs of strings is given and two arbitrary strings are concatenated only when among their substrings (scattered substrings, of various forms) we can find a pair in this control set. Five types of non-iterated and iterated (like Kleene closure) conditional concatenations are considered. The closure properties of abstract families of languages (hence also of families in the Chomsky hierarchy) are settled. They are similar to the closure properties under usual concatenation and Kleene closure. A representation of regular languages in terms of these operations (and a coding) is also given. Then, we use the new concatenation operations as basic operations in Chomsky grammars: rewriting a nonterminal means concatenating a new string with the strings to the left and the right of that nonterminal, hence restricted concatenations can be used. Context-free grammars working in this restricted manner can generate non-context-free languages; in one case, characterizations of recursively enumerable or of context-sensitive languages are obtained, depending on using or not erasing rules. Some topics for further research are also suggested. |
| Uitgever: |
IOS Press |
| Bronbestand: |
Elektronische Wetenschappelijke Tijdschriften |
Details van artikel 2 van 4 gevonden artikelen
| << vorige | volgende >> |