On transformations of formal power series |
| |
Authors: | Manfred Droste Guo-Qiang Zhang |
| |
Affiliation: | a Institut für Algebra, Technische Universität Dresden, Dresden D-01062, Germany;b Department of Electrical Engineering and Computer Science, Case Western Reserve University, 10900 Euclid Avenue, 610 Olin, Cleveland, OH 44106-1712, USA |
| |
Abstract: | Formal power series are an extension of formal languages. Recognizable formal power series can be captured by the so-called weighted finite automata, generalizing finite state machines. In this paper, motivated by codings of formal languages, we introduce and investigate two types of transformations for formal power series. We characterize when these transformations preserve recognizability, generalizing the recent results of Zhang 16] to the formal power series setting. We show, for example, that the “square-root” operation, while preserving regularity for formal languages, preserves recognizability for formal power series when the underlying semiring is commutative or locally finite, but not in general. |
| |
Keywords: | Formal power series Rational languages Recognizable languages Weighted finite automata |
本文献已被 ScienceDirect 等数据库收录! |
|