First order synthesis for data words revisited

2023/07/10 by Grange, Julien, Lehaut, Mathieu
#FOS: Computer and information sciences #Logic in Computer Science (cs.LO)

paper · doi:10.48550/arxiv.2307.04499

Abstract

We carry on the study of the synthesis problem on data words for fragments of first order logic, and delineate precisely the border between decidability and undecidability.

Related

• Synthesis for prefix first-order logic on data words
• Parameterized Synthesis for Fragments of First-Order Logic over Data\n Words
• Decidability, Complexity, and Expressiveness of First-Order Logic Over the Subword Ordering
• Logics for Word Transductions with Synthesis
• First-order Fragments with Successor over Infinite Words