Space-efficient bimachine construction based on the equalizer accumulation principle

Gerdjikov, Stefan; Mihov, Stoyan und Schulz, Klaus U. (2019): Space-efficient bimachine construction based on the equalizer accumulation principle. In: Theoretical Computer Science, Bd. 790: S. 80-95

Abstract

Algorithms for building bimachines from functional transducers found in the literature are based on the following principle: each run of the bimachine simulates a particular successful path of the input transducer. Every single bimachine output exactly corresponds to the output of a single transducer transition. Here we introduce an alternative construction principle called the equalizer accumulation principle. It suggests that the bimachine steps take into account alternative parallel transducer paths, maximizing the possible output at each step using a joint view. This results in a construction where the deterministic left and right automaton of the bimachine both have size bounded by 2(vertical bar Q vertical bar) where vertical bar Q vertical bar is the number of transducer states. In contrast, previous bimachine constructions lead to larger automata. We present a class of real-time functional transducers with n + 2 states for which the standard bimachine construction generates a bimachine with at least Theta(n!) states whereas the construction based on the equalizer accumulation principle leads to 2(n) + n + 3 states. On the other end we present a real-time functional transducers with 4(n + 1) states that cannot be represented as a bimachine with less than 2(n) states. Therefore the space complexity of our construction is close to optimal in terms of the number of states. The new construction can be applied to rational functions from free monoids to "mge monoids", a large class of monoids including free monoids, groups, and others that is closed under Cartesian products. (C) 2019 Elsevier B.V. All rights reserved.

• Dokumententyp: Zeitschriftenartikel
• Fakultätsübergreifende Einrichtungen: Centrum für Informations- und Sprachverarbeitung (CIS)
• Themengebiete: 400 Sprache > 400 Sprache
• ISSN: 0304-3975
• Sprache: Englisch