Scholarlink

We investigate the relationship of languages characterized by variants of string assembling systems and by Watson-Crick automata with a small number of states. Besides the general variant, we consider so-called free and pure string assembling systems, and compare their language generating power to Watson-Crick automata having one, two, or three states in their state sets. In some cases, restricted variants of the models describing unary languages are also considered.

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

On the Power of Small Watson-Crick Automata and Variants of String Assembling Systems

  • 会议论文

  • 发表日期：

    2025年

查看全文
  • András Murvai,
  • György Vaszil

摘要

We investigate the relationship of languages characterized by variants of string assembling systems and by Watson-Crick automata with a small number of states. Besides the general variant, we consider so-called free and pure string assembling systems, and compare their language generating power to Watson-Crick automata having one, two, or three states in their state sets. In some cases, restricted variants of the models describing unary languages are also considered.