Multi-tilde-bar expressions and their automata

摘要

The aim of this paper is to extend the family of Glushkov automata. This is achieved by designing new operators, the so-called multi-tilde-bar operators, that allow us to compute Glushkov functions for the associated extended expressions. Conversely an extended Glushkov automaton with n + 1 states can be converted into an extended expression with n occurrences of symbols. It leads to a characterization in terms of graphs of the family of extended Glushkov automata. Moreover, extended expressions are shown to be superpoly-nomially more succinct than standard expressions.