pith. sign in

arxiv: 2302.06248 · v4 · submitted 2023-02-13 · 💻 cs.FL

Decision Problems on Copying and Shuffling

Vesa Halava , Tero Harju , Dirk Nowotka , Esa Sahla This is my paper

Pith reviewed 2026-05-24 10:11 UTC · model grok-4.3

classification 💻 cs.FL
keywords regular languageslinear context-free languagesdecidabilitycopy operationshuffle operationword problemsformal languages
0
0 comments X

The pith

The decidability status of problems asking whether regular or linear context-free languages contain words of copy, marked copy or shuffle forms is analyzed for different combinations.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper examines decision problems that ask, for a given regular or linear context-free language, whether it contains a word matching one of several fixed patterns built from the operations of copy, marked copy, shuffle, or combinations of them. These problems are studied to determine in which cases an algorithm exists to answer the question. A sympathetic reader would care because the results map out the effective properties of basic word operations inside the most commonly used language classes, clarifying where automated checks are possible.

Core claim

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.

What carries the argument

Decision problem for the existence of a word with a prescribed copy, marked-copy or shuffle structure inside a regular or linear context-free language.

If this is right

  • For each combination of copy, marked copy and shuffle the decidability status is settled for regular languages.
  • The same combinations receive decidability status for linear context-free languages.
  • The outcomes depend on the precise mix of operations appearing in the fixed form.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Similar decision questions could be posed for other restricted language families such as deterministic context-free languages.
  • The techniques might be reused to decide related properties involving additional word operations like reversal or duplication.

Load-bearing premise

The input languages belong to the regular or linear context-free classes, which keeps the decision problems well-defined and open to algorithmic treatment.

What would settle it

A concrete regular language L and a fixed copy-shuffle form for which no algorithm can correctly decide whether L contains a matching word.

read the original abstract

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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The manuscript studies decision problems of the form: given a regular or linear context-free language L, decide whether L contains a word matching a fixed pattern built from the operations copy, marked copy, shuffle, and combinations thereof. It claims that all such problems are decidable, via effective constructions that reduce each instance to emptiness or membership testing within the same language class (automata products for regular languages; intersections or homomorphisms for linear CFLs).

Significance. If the results hold, the paper delivers a uniform decidability classification for this family of pattern-existence problems. The constructive reductions stay inside the target classes and require no extra assumptions on alphabet size or pattern length, which is a clear technical strength. The approach yields explicit algorithms rather than non-constructive existence proofs.

minor comments (2)
  1. [Abstract] The abstract states the problems clearly but does not indicate the reduction technique; a single sentence on the proof method would help readers locate the main technical contribution.
  2. [Preliminaries] Notation for the 'marked copy' operation is introduced without an immediate concrete example; adding one in the preliminaries would improve readability for readers outside the immediate sub-area.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive evaluation of the manuscript and for recommending acceptance. The report accurately captures the main contributions regarding the decidability of the pattern-existence problems for regular and linear context-free languages.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper establishes decidability of pattern-existence problems for regular and linear CFLs by explicit reductions to emptiness (for regular languages via automata products) and to membership or emptiness (for linear CFLs via homomorphisms and intersections). These reductions rely on standard closure properties and decidability results for the language classes, which are independent of the paper's own constructions. No self-definitional equations, fitted parameters renamed as predictions, or load-bearing self-citations appear in the derivation chain. The argument is self-contained against external automata-theoretic benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Only the abstract is available; no free parameters, axioms, or invented entities can be extracted from the given text.

pith-pipeline@v0.9.0 · 5556 in / 969 out tokens · 17022 ms · 2026-05-24T10:11:33.016920+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

19 extracted references · 19 canonical work pages

  1. [1]

    Detecting patterns in finite regu lar and context-free languages

    Rampersad N, Shallit J. Detecting patterns in finite regu lar and context-free languages. Inf. Process. Lett.,

    work page

  2. [2]

    doi:10.1016/j.ipl.2009.11.002

    110(3):108–112. doi:10.1016/j.ipl.2009.11.002

    work page doi:10.1016/j.ipl.2009.11.002 2009

  3. [3]

    Formal Languages

    Salomaa A. Formal Languages. Academic Press, New Y ork, 1 973

    work page

  4. [4]

    Queue Automata: Founda tions and Developments, pp

    Kutrib M, Malcher A, Wendlandt M. Queue Automata: Founda tions and Developments, pp. 385–431. Springer International Publishing. ISBN 978-3-319-73216 -9, 2018. doi:10.1007/978-3-319-73216-9_19. URL https://doi.org/10.1007/978-3-319-73216-9_19

    work page doi:10.1007/978-3-319-73216-9_19 2018

  5. [5]

    A variant of a recursively unsolvable problem

    Post EL. A variant of a recursively unsolvable problem. Bull. Amer . Math. Soc. , 1946. 52:264–268. doi:10.1090/S0002-9904-1946-08555-9. URL http://dx.doi.org/10.1090/S0002-9904-1946- 08555-9

    work page doi:10.1090/s0002-9904-1946-08555-9 1946

  6. [6]

    ‘An equilibrium existence result for an economy with land’

    Ehrenfeucht A, Karhumäki J, Rozenberg G. The (generaliz ed) Post correspondence problem with lists consisting of two words is decidable. Theoret. Comput. Sci. , 1982. 21(2):119–144. doi:10.1016/0304- 3975(89)90080-7. URL http://dx.doi.org/10.1016/0304-3975(89)90080-7

    work page doi:10.1016/0304- 1982

  7. [7]

    Binary (generalized) Po st correspondence problem

    Halava V , Harju T, Hirvensalo M. Binary (generalized) Po st correspondence problem. The- oret. Comput. Sci. , 2002. 276(1-2):183–204. doi:10.1016/S0304-3975(01)00157-8. URL http://dx.doi.org/10.1016/S0304-3975(01)00157-8. 284 V . Halava et al. / Decision Problems on Copying and Shuffling

    work page doi:10.1016/s0304-3975(01)00157-8 2002

  8. [8]

    Undecidability in binary tag systems and the Pos t correspondence problem for five pairs of words

    Neary T. Undecidability in binary tag systems and the Pos t correspondence problem for five pairs of words. In: 32nd International Symposium on Theoretical Asp ects of Computer Science, volume 30 of LIPIcs. Leibniz Int. Proc. Inform. , Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2015 pp . 649–661. doi:10.5167/uzh-121761

    work page doi:10.5167/uzh-121761 2015

  9. [9]

    Rabin & D

    Rabin MO, Scott D. Finite Automata and Their Decision Pro blems. IBM J. Res. Dev., 1959. 3(2):114–125. doi:10.1147/rd.32.0114. URL https://doi.org/10.1147/rd.32.0114

    work page doi:10.1147/rd.32.0114 1959

  10. [10]

    D etecting palindromes, patterns and borders in regular languages

    Anderson T, Loftus J, Rampersad N, Santean N, Shallit J. D etecting palindromes, patterns and borders in regular languages. Inf. Comput., 2009. 207(11):1096–1118. doi:10.1016/j.ic.2008.06.007

    work page doi:10.1016/j.ic.2008.06.007 2009

  11. [11]

    Primitive words and roots of words

    Lischke G. Primitive words and roots of words. Acta Univ. Sapientiae, Inform., 2011. 3(1):5–34

    work page 2011

  12. [12]

    Fixed point languages, equa lity languages, and representation of recursively enumerable languages

    Engelfriet J, Rozenberg G. Fixed point languages, equa lity languages, and representation of recursively enumerable languages. J. Assoc. Comput. Mach. , 1980. 27:499–518

    work page 1980

  13. [13]

    On shuffling a word with its let ter-to-letter substitution

    Halava V , Harju T, Sahla E. On shuffling a word with its let ter-to-letter substitution. Fundamenta Infor- maticae, 2020. 175:201–206

    work page 2020

  14. [14]

    On comparing deterministic fini te automata and the shuffle of words

    Biegler F, McQuillan I. On comparing deterministic fini te automata and the shuffle of words. In: Im- plementation and application of automata. 19th internatio nal conference, CIAA 2014, Giessen, Germany, July 30 – August 2, 2014. Proceedings, pp. 98–109. Berlin: Sp ringer. ISBN 978-3-319-08845-7/pbk, 2014

    work page 2014

  15. [15]

    The unsolvability of the recognition of lin ear context-free languages

    Greibach S. The unsolvability of the recognition of lin ear context-free languages. J. Assoc. Comput. Mach., 1966. 13:582–587

    work page 1966

  16. [16]

    personal communication

    Köcher C. personal communication

    work page

  17. [17]

    On recognizing words that are squar es for the shuffle product

    Rizzi R, Vialette S. On recognizing words that are squar es for the shuffle product. In: Computer science – theory and applications. 8th international computer scie nce symposium in Russia, CSR 2013, Ekater- inburg, Russia, June 25–29, 2013. Proceedings, pp. 235–245 . Berlin: Springer. ISBN 978-3-642-38535- 3/pbk, 2013

    work page 2013

  18. [18]

    Unshuffling a square is NP-hard

    Buss S, Soltys M. Unshuffling a square is NP-hard. J. Comput. Syst. Sci. , 2014. 80(4):766–776

    work page 2014

  19. [19]

    Shuffling and Unshuf fling

    Henshall D, Rampersad N, Shallit J. Shuffling and Unshuf fling. Bulletin of the EATCS , 2012. (107):131–

    work page 2012