Decision problems on copying and shuffling

DOI10.3233/FI-242182MaRDI QIDQ6614538

Esa Sahla, Vesa Halava, Tero Harju, Dirk Nowotka

Publication date: 7 October 2024

Published in: Fundamenta Informaticae (Search for Journal in Brave)

zbMATH Keywords

shuffleregular languagemembership problemlinear context-free languagemarked copyreverse copy

Mathematics Subject Classification ID

Computer science (68-XX)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Detecting patterns in finite regular and context-free languages
• Detecting palindromes, patterns and borders in regular languages
• The (generalized) Post correspondence problem with lists consisting of two words is decidable
• Binary (generalized) Post Correspondence Problem
• Unshuffling a square is NP-hard
• Undecidability in Binary Tag Systems and the Post Correspondence Problem for Five Pairs of Words
• On Comparing Deterministic Finite Automata and the Shuffle of Words
• Fixed Point Languages, Equality Languages, and Representation of Recursively Enumerable Languages
• On Recognizing Words That Are Squares for the Shuffle Product
• On Shuffling a Word with its Letter-to-Letter Substitution
• Queue Automata: Foundations and Developments
• The Unsolvability of the Recognition of Linear Context-Free Languages
• A variant of a recursively unsolvable problem

This page was built for publication: Decision problems on copying and shuffling

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6614538)