Automata and Grammars for Data Words

Register automaton (RA) and register context-free grammar (RCFG) are extensions of finite automaton and context-free grammar by adding the ability of data manipulation in a restricted way. This paper reviews definitions and basic properties of RA and RCFG. As a related topic, logics on data words, namely, linear-time temporal logic (LTL) with freeze quantifier and two-variable first-order logic with data equality are explained. Finally, nominal automaton, which can be regarded as a group-theoretic generalization of RA, is briefly described.