Journal article

Publication year: 2019

Pages: 94-111

Journal: Information and Computation

Volume number: 265

ISSN: 0890-5401

eISSN: 1090-2651

Open access status: Bronze

DOI Link: https://doi.org/10.1016/j.ic.2019.01.003

Publisher: Elsevier

Abstract: 
We contribute new relations to the taxonomy of different conversions from regular expressions to equivalent finite automata. In particular, we are interested in transformations that construct automata such as, the follow automaton, the partial derivative automaton, the prefix automaton, the automata based on pointed expressions recently introduced and studied, and last but not least the position, or Glushkov automaton (A(POS)), and their double reversed construction counterparts. We deepen the understanding of these constructions and show that with the artefacts used to construct the Glushkov automaton one is able to capture most of them. As a byproduct we define a dual version A((POS) over left arrow) of the position automaton which plays a similar role as A(POS) but now for the reverse expression. Moreover, it turns out that the prefix automaton A(Pre) is central to reverse expressions, because the determinisation of the double reversal of A(Pre) (first reverse the expression, construct the automaton A(Pre), and then reverse the automaton) can be represented as a quotient of any of the considered deterministic automata that we consider in this investigation. This shows that although the conversion of regular expressions and reversal of regular expressions to finite automata seems quite similar, there are significant differences. (C) 2019 Elsevier Inc. All rights reserved.

Harvard Citation style: Broda, S., Holzer, M., Maia, E., Moreira, N. and Reis, R. (2019) A mesh of automata, Information and Computation, 265, pp. 94-111. https://doi.org/10.1016/j.ic.2019.01.003

APA Citation style: Broda, S., Holzer, M., Maia, E., Moreira, N., & Reis, R. (2019). A mesh of automata. Information and Computation. 265, 94-111. https://doi.org/10.1016/j.ic.2019.01.003