Multiset automata are a class of automata for which the symbols can be read in any order and obtain the same result. We investigate weighted multiset automata and show how to construct them from weighted regular expressions. We present training methods to learn the weights for weighted regular expressions and for general multiset automata from data. Finally, we examine situations in which inside weights can be computed more efficiently.
Droste and Gastin @cite_1 show how to perform regular operations for the more general case of trace automata (automata on monoids). Our use of @math resembles their forward alphabet. Our construction does not utilize anything akin to their backward alphabet, so that we allow outgoing edges from final states and we allow initial states to be final states. Their construction, when converting @math , creates @math simultaneous copies of @math , that is, it creates an automaton with @math states. Since our Kleene star is restricted to the unary case, we can use the standard, much simpler, Kleene star construction @cite_3 .
@cite_1 @cite_3
1975161395 2092860912
Kleene's theorem on the coincidence of regular and rational languages in free monoids has been generalized by Schutzenberger to a description of the recognizable formal power series in noncommuting variables over arbitrary semirings and by Ochmanski to a characterization of the recognizable languages in trace monoids. We will describe the recognizable formal power series over arbitrary semirings and in partially commuting variables, i.e. over trace monoids. We prove that the recognizable series are certain rational power series, which can be constructed from the polynomials by using the operations sum, product, and a restricted star which is applied only to series for which the elements in the support all have the same connected alphabet. The converse is true if the underlying semiring is commutative. Moreover, if in addition the semiring is idempotent then the same result holds with a star restricted to series for which the elements in the support have connected (possibly different) alphabets. It is shown that these assumptions over the semiring are necessary. This provides a joint generalization of Kleene's, Schutzenberger's and Ochmanski's theorems. The main theorem allows an elegant algorithm to be refined into an efficient one. The elegant algorithm for constructing a finite automaton from a regular expression is based on ‘derivatives of’ regular expressions; the efficient algorithm is based on ‘marking of’ regular expressions. Derivatives of regular expressions correspond to state transitions in finite automata. When a finite automaton makes a transition under input symbol a, a leading a is stripped from the remaining input. Correspondingly, if the input string is generated by a regular expression E, then the derivative of E by a generates the remaining input after a leading a is stripped. Brzozowski (1964) used derivatives to construct finite automata; the state for expression E has a transition under a to the state for the derivative of E by a. This approach extends to regular expressions with new operators, including intersection and complement; however, explicit computation of derivatives can be expensive. Marking of regular expressions yields an expression with distinct input symbols. Following McNaughton and Yamada (1960), we attach subscripts to each input symbol in an expression; (ab + b)∗ba becomes (a1b2+b3)∗b4a5. Conceptually, the efficient algorithm constructs an automaton for the marked expression. The marks on the transitions are then erased, resulting in a nondeterministic automaton for the original unmarked expression. This approach works for the usual operations of union, concatenation, and iteration; however, intersection and complement cannot be handled because marking and unmarking do not preserve the languages generated by regular expressions with these operators.