Scoped MSO, Register Automata, and Expressions: Equivalence over Data Words

1 Introduction

2 Preliminaries

2.1 Formalisms for regular languages

2.2 Words over infinite alphabets

2.3 Register automata: a formalism for data languages

3 New formalisms equivalent to register automata

3.1 Data regular expressions

3.2 Scoped MSO

4 Translations between the new formalisms and register automata

4.1 Translations between Data Regular Expressions and register automata

4.2 Translations between Scoped MSO and register automata

4.2.1 From logic to automata

4.2.2 From automata to logic

5 Extensions and restrictions of Scoped MSO

5.1 A logic equivalent to register automata over infinite words

5.2 A logic equivalent to register automata with strong guessing

5.3 A logic equivalent to register automata without guessing

References