• TUCS Publication Series
• How to Publish in TUCS Series
• Publication Search
• Publication Graph
• Publication Input
• Publication Input Guide
• JuFo Browser

On Continuous Weighted Finite Automata

Jarkko Kari, Alexandr Kazda, Paula Steinby, On Continuous Weighted Finite Automata. LINEAR ALGEBRA AND ITS APPLICATIONS 436(7), 1791–1824, 2012.

Abstract:

We investigate the continuity of the ω-functions and real functions defined by weighted finite automata (WFA).We concentrate on the case of average preserving WFA. We show that every continuous ω-function definable by some WFA can be defined by an average preserving WFA and then characterize minimal average preserving WFA whose ω-function or ω-function and real function are continuous. We obtain several algorithmic reductions for WFA-related decision problems. In particular, we show that deciding whether the ω-function and real function of an average preserving WFA are both continuous is computationally equivalent to deciding stability of a set of matrices. We also present amethod for constructingWFA that compute continuous real functions.

BibTeX entry:

@ARTICLE{jKaKaSt12a,
  title = {On Continuous Weighted Finite Automata},
  author = {Kari, Jarkko and Kazda, Alexandr and Steinby, Paula},
  journal = {LINEAR ALGEBRA AND ITS APPLICATIONS},
  volume = {436},
  number = {7},
  pages = {1791–1824},
  year = {2012},
}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Publication Forum rating of this publication: level 1

Edit publication