Multiplicity automatons (see here) is an interesting model. They have the (almost) same syntax as a non-deterministic finite automatons, but instead of deciding whether a word belongs to a language, they compute a function, $f_A: \Sigma^* \to F$.

I'm interested in a special kind of multiplicity automata, called binary MA :- automaton which computes a value over $Z_2$, and all of the weights associated to the arcs are $1$.

Since the function computed is over $Z_2$, we can discuss the language of the automaton, which is defined as: $L(A) = \{w|f_A(w)=1\}$.

In other words - such automaton $A$ is a NFA, accepting a word $w$ iff the number of accepting paths for $w$ in $A$ is a odd number.

For example, every DFA is a binary MFA.

While it is easy to figure whether a DFA or NFA has an empty language, finding whether a binary MFA's language is empty or not seems harder.

(or, formulated differently, whether a NFA has a word which is accepted by odd number of paths).

It seems that I can find a naive algorithm for the task which runs in $poly(n,|\Sigma|)$ (where $n$ is the number of states), but I'm wondering if it's possible to reduce it to $n^2$ (or maybe lower :) ).

EDIT: if it helps, the actual automaton I have has no cycles (which means $L(A)$ is finite).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.