
arXiv: 1205.1825
Automata, Logic and Semantics Our aim is to construct a finite automaton recognizing the set of words that are at a bounded distance from some word of a given regular language. We define new regular operators, the similarity operators, based on a generalization of the notion of distance and we introduce the family of regular expressions extended to similarity operators, that we call AREs (Approximate Regular Expressions). We set formulae to compute the Brzozowski derivatives and the Antimirov derivatives of an ARE, which allows us to give a solution to the ARE membership problem and to provide the construction of two recognizers for the language denoted by an ARE. As far as we know, the family of approximative regular expressions is introduced for the first time in this paper. Classical approximate regular expression matching algorithms are approximate matching algorithms on regular expressions. Our approach is rather to process an exact matching on approximate regular expressions.
FOS: Computer and information sciences, [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], Formal Languages and Automata Theory (cs.FL), [INFO]Computer Science [cs], Computer Science - Formal Languages and Automata Theory, [INFO] Computer Science [cs], [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
FOS: Computer and information sciences, [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], Formal Languages and Automata Theory (cs.FL), [INFO]Computer Science [cs], Computer Science - Formal Languages and Automata Theory, [INFO] Computer Science [cs], [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
