Generalized regular expressions - a language for synthesis of programs with branching in loops (Q1822523)

Regular expressions are generalized to the effect that, besides letters from a finite alphabet, they may also contain natural numbers. Within the framework of these generalized expressions the task of the inductive synthesis of programs from its sample run is formalized. Special automata recognizing the sets defined by generalized expressions are introduced, and their equivalence problem is shown to be recursively solvable. The set-theoretic properties of the sets defined by generalized expressions are also studied.