Derived-Term Automata of Weighted Rational Expressions with Quotient Operators

摘要

Quotient operators have been rarely studied in the context of weighted rational expressions and automaton generation-in spite of the key role played by the quotient of words in formal language theory. To handle both left- and right-quotients we generalize an expansion-based construction of the derived-term (or Antimirov, or equation) automaton and rely on support for a transposition (or reversal) operator. The resulting automata may have spontaneous transitions, which requires different techniques from the usual derived-term constructions.