On Computability and Some Decision Problems of Parametric Weighted Finite Automata
German Tischler · Journal of automata, languages and combinatorics · 2007
Parametric weighted finite automata (PWFA) are a multidimensional variant of weighted finite automata (WFA). In contrast to WFA, one primarily considers the set of vectors computed by a PWFA and not the function it computes. In this paper we show that the membership, emptiness and equivalence problems for PWFA are recursively undecidable and that there is no algorithm that effectively minimizes a PWFA. We study the correlation between iterated function systems (IFS) and the class cPWFA of PWFA that are based on contraction mappings, where we Show that it is decidable, if a PWFA belongs to cPWFA, that automata in cPWFA compute affine transformations of the attractors of certain IFS, that the set of sets computable by automata in cPWFA is effectively closed under arbitrary affine transformation and that any PWFA computing a non compact set cannot be a member of cPWFA. For PWFA with unary alphabet we proof that the set of sets computable is effectively closed under set union and that the membership problem for unary alphabet integer PWFA is decidable.