(Un)Decidability Results for Word Equations with Length and Regular Expression Constraints

Vijay Ganesh, Mia Minnes, Armando Solar-Lezama +1

We prove several decidability and undecidability results for the satisfiability and validity problems for languages that can express solutions to word equations with length constra…