
arXiv: 0908.3784
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 a method for constructing WFA that compute continuous real functions.
41 pages, 9 figures
FOS: Computer and information sciences, Matrix semigroup, Formal Languages and Automata Theory (cs.FL), Computer Science - Formal Languages and Automata Theory, Decidability, Formal languages and automata, weighted finite automaton, Discrete Mathematics and Combinatorics, ta113, Numerical Analysis, Algebra and Number Theory, Continuity and related questions (modulus of continuity, semicontinuity, discontinuities, etc.) for real functions in one variable, ta111, decidability, Basic linear algebra, stability, continuity, matrix semigroup, Semigroups in automata theory, linguistics, etc., Weighted finite automaton, Geometry and Topology, Stability, F.1.1, Continuity
FOS: Computer and information sciences, Matrix semigroup, Formal Languages and Automata Theory (cs.FL), Computer Science - Formal Languages and Automata Theory, Decidability, Formal languages and automata, weighted finite automaton, Discrete Mathematics and Combinatorics, ta113, Numerical Analysis, Algebra and Number Theory, Continuity and related questions (modulus of continuity, semicontinuity, discontinuities, etc.) for real functions in one variable, ta111, decidability, Basic linear algebra, stability, continuity, matrix semigroup, Semigroups in automata theory, linguistics, etc., Weighted finite automaton, Geometry and Topology, Stability, F.1.1, Continuity
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 1 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
