Scholarlink

<p>In the past, there have been many different string insertion operations—often inspired by biological or physical systems—that have been defined and studied using formal language theory. For each such insertion operation, it is common to state various decision problems using important computational models, and to study whether these problems are decidable or not. Here, we generalize this approach by studying any possible insertion operation that can be defined as long as they produce every string in some lower bound language and no strings outside some upper bound language. We create two different such classes of insertion operations called <i>general contextual insertion operations</i> and <i>general concatenative insertion operations</i>. Several problems (so-called language equations) are shown to be undecidable no matter how an insertion operation is defined, so long as it belongs to one of these classes of operations. Several problems are also shown to be decidable, as long as the insertion operation satisfies some simple conditions. This general approach covers many different insertion operations that have been defined and studied in the literature, from classical operations such as concatenation and shuffle, to bio-inspired insertion operations, and we are able to demonstrate many stronger decidability results than what was previously known.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

On decidability of problems involving insertion operations

  • 期刊论文

  • 发表日期：

    2025年6月14日

查看全文
  • Oscar H. Ibarra,
  • Ian McQuillan

摘要

In the past, there have been many different string insertion operations—often inspired by biological or physical systems—that have been defined and studied using formal language theory. For each such insertion operation, it is common to state various decision problems using important computational models, and to study whether these problems are decidable or not. Here, we generalize this approach by studying any possible insertion operation that can be defined as long as they produce every string in some lower bound language and no strings outside some upper bound language. We create two different such classes of insertion operations called general contextual insertion operations and general concatenative insertion operations. Several problems (so-called language equations) are shown to be undecidable no matter how an insertion operation is defined, so long as it belongs to one of these classes of operations. Several problems are also shown to be decidable, as long as the insertion operation satisfies some simple conditions. This general approach covers many different insertion operations that have been defined and studied in the literature, from classical operations such as concatenation and shuffle, to bio-inspired insertion operations, and we are able to demonstrate many stronger decidability results than what was previously known.