Space-efficient bimachine construction based on the equalizer accumulation principle

DOI10.1016/J.TCS.2019.04.027MaRDI QIDQ2272386zbMATH OpenOpenAlexWikidataFDO

Authors Stefan Gerdjikov, Stoyan Mihov, K. U. Schulz

Publication date 10 September 2019

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1803.04312

zbMATH Keywords

rational functionstransducersbimachines

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Semigroups in automata theory, linguistics, etc. (20M35)

Abstract: Algorithms for building bimachines from functional transducers found in the literature in a run of the bimachine imitate one successful path of the input transducer. Each single bimachine output exactly corresponds to the output of a single transducer transition. Here we introduce an alternative construction principle where bimachine steps take alternative parallel transducer paths into account, maximizing the possible output at each step using a joint view. The size of both the deterministic left and right automaton of the bimachine is restricted by $2^{vertQvert}$ where $vertQvert$ is the number of transducer states. Other bimachine constructions lead to larger subautomata. As a concrete example 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. Our 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.

Recommendations

• A simple method for building bimachines from functional finite-state transducers
• scientific article; zbMATH DE number 2143017
• Nondeterministic bimachines and rational relations with finite codomain
• Finite-state techniques. Automata, transducers and bimachines
• scientific article; zbMATH DE number 1047903

Cites work

• scientific article; zbMATH DE number 3497806 (Why is no real title available?)
• scientific article; zbMATH DE number 1773083 (Why is no real title available?)
• scientific article; zbMATH DE number 1773099 (Why is no real title available?)
• A simple method for building bimachines from functional finite-state transducers
• Elements of automata theory. Translated from the French by Reuben Thomas
• Over Which Monoids is the Transducer Determinization Procedure Applicable?
• Squaring transducers: An efficient procedure for deciding functionality and sequentiality.

Cited in

(3)

• Conditions for the existence of maximal factorizations
• A simple method for building bimachines from functional finite-state transducers
• scientific article; zbMATH DE number 2143017 (Why is no real title available?)

This page was built for publication: Space-efficient bimachine construction based on the equalizer accumulation principle

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2272386)