Decision Problems on Copying and Shuffling

被引：0
作者：
Halava, Vesa [1 ]
Harju, Tero [1 ]
Nowotka, Dirk [2 ]
Sahla, Esa [1 ]
机构：
[1] Univ Turku, Dept Math & Stat, Turku, Finland
[2] Univ Kiel, Dept Comp Sci, Kiel, Germany
来源：
FUNDAMENTA INFORMATICAE | 2024年 / 191卷 / 3-4期
关键词：
Regular language; linear context-free language; shuffle; marked copy; reverse copy; membership problem; POST CORRESPONDENCE PROBLEM; FINITE AUTOMATA;
D O I：
10.3233/FI-242182
中图分类号：
TP31 [计算机软件];
学科分类号：
081202 ; 0835 ;
摘要：
We study decision problems of the form: given a regular or linear context-free language L, is there a word of a given fixed form in L, where given fixed forms are based on word operations copy, marked copy, shuffle and their combinations.
引用
收藏
页码：269 / 284
页数：16
相关论文
共 50 条
  • [1] Site-directed insertion: Language equations and decision problems
    Cho, Da-Jung
    Han, Yo-Sub
    Salomaa, Kai
    Smith, Taylor J.
    THEORETICAL COMPUTER SCIENCE, 2019, 798 : 40 - 51
  • [2] Decision problems for convex languages
    Brzozowski, Janusz
    Shallit, Jeffrey
    Xu, Zhi
    INFORMATION AND COMPUTATION, 2011, 209 (03) : 353 - 367
  • [3] Decision Problems for Reversible and Permutation Automata
    Radionova, Maria
    Okhotin, Alexander
    IMPLEMENTATION AND APPLICATION OF AUTOMATA, CIAA 2024, 2024, 15015 : 302 - 315
  • [4] Decision Problems and Applications of Rational Sets of Regular Languages
    Afonin, Sergey
    FUNDAMENTA INFORMATICAE, 2018, 162 (2-3) : 101 - 118
  • [5] Decision problems for serni-Thue systems with a few rules
    Matiyasevich, Y
    Sénizergues, G
    THEORETICAL COMPUTER SCIENCE, 2005, 330 (01) : 145 - 169
  • [6] Decision problems for semi-Thue systems with a few rules
    Matiyasevich, Y
    Senizergues, G
    11TH ANNUAL IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE, PROCEEDINGS, 1996, : 523 - 531
  • [7] Efficient and verifiable shuffling and shuffle-decryption
    Furukawa, J
    IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, 2005, E88A (01) : 172 - 188
  • [8] Site-Directed Insertion: Decision Problems, Maximality and Minimality
    Cho, Da-Jung
    Han, Yo-Sub
    Salomaa, Kai
    Smith, Taylor J.
    DESCRIPTIONAL COMPLEXITY OF FORMAL SYSTEMS, DCFS 2018, 2018, 10952 : 49 - 61
  • [9] Skew-Aware Collective Communication for MapReduce Shuffling
    Daikoku, Harunobu
    Kawashima, Hideyuki
    Tatebe, Osamu
    2018 IEEE INTERNATIONAL CONFERENCE ON BIG DATA (BIG DATA), 2018, : 3331 - 3340
  • [10] State Complexity of Permutation and Related Decision Problems on Alphabetical Pattern Constraints
    Hoffmann, Stefan
    IMPLEMENTATION AND APPLICATION OF AUTOMATA (CIAA 2021), 2021, 12803 : 115 - 126
12345