What is Decidable about Strings?
We prove several decidability and undecidability results for the satisfiability/validity problem of formulas over a language of finite-length strings and integers (interpreted as lengths of strings). The atomic formulas over this language are equality over string terms (word equations), linear inequ...
Main Authors: | , , , |
---|---|
Other Authors: | |
Published: |
2011
|
Subjects: | |
Online Access: | http://hdl.handle.net/1721.1/60877 |