Stability of desynchronized 0L-systems
type: Item
instance of: scholarly article
title: Stability of desynchronized 0L-systems
zbMATH Open document ID: 0539.68046
DOI: 10.1016/0020-0190(83)90076-5
author: Youichi Kobuchi
published in: Information Processing Letters
publication date: 1983-01-01T00:00:00Z
review text: A 0L scheme (\(\Sigma\),g) is defined to be \(\Delta\)-desynchronization of \(S=(\Sigma,h)\) if \(g(a)=\{a,h(a)\}\) for \(a\in \Delta\), \(g(a)=h(a)\) otherwise. For a 0L system \(G=(\Sigma,h,w)\) whose underlying scheme is equal to \(S=(\Sigma,h)\) the \(\Delta\)-desynchronization of S induces \(\Delta\)-desynchronization of G. A system G is defined to be stable under \(\Delta\)-desynchronization w.r.t. a target \(T\subseteq \Sigma^*\) if \(T\cap L(G)=T\cap L(G^ d(\Delta)),\) where L(G) is a language generated by G and \(G^ d(\Delta)\) is \(\Delta\)-desynchronization of G. It is proved that a 0L system is stable under \(\Sigma\)-desynchronization w.r.t. the set of recurrent strings and it is stable under \(\Delta\)- desynchronization w.r.t. the set of adult strings.
Mathematics Subject Classification ID: 68Q42
zbMATH DE Number: 3858421
zbMATH Keywords: stability
zbMATH Keywords: desynchronization
zbMATH Keywords: 0L system
MaRDI profile type: Publication
full work available at URL: 0020-0190(83)90076-5
OpenAlex ID: W2028929372
cites work: Description of developmental languages using recurrence systems
cites work: Context free languages in biological systems
cites work: CONCEPT ADVANTAGES OF DISCRETE EVENT FORMALISM
cites work: Stability in OL systems
cites work: Q4140407
cites work: Recurrent words for substitution
cites work: Formal grammars and the regeneration capability of biological systems
description: scientific article; zbMATH DE number 3858421