← All problems
Unverified

Does a ( min,+)-WA preserve REG by inverse image?

We are interested in functions realized by weighted automata over the semiring Nmin=⟨N∪{∞},min,+,∞,0⟩\mathbb N_{\mathsf{ min}}=\langle \mathbb N\cup\left\{ \infty \right\} , \mathsf{ min}, +, \infty,0\rangle. An Nmin\mathbb N \mathsf{ min}-weighted automaton A\mathcal A over alphabet Σ\Sigma realizes a partial function [ ⁣[A] ⁣]:Σ∗→N[\![ \mathcal A ]\!]:\Sigma^*\rightarrow \mathbb N. We want to decide given such a function if it preserves ``simple'' sets by inverse image. By simple we mean regular languages (N\mathbb N is viewed a the set of words over a unary alphabet, hence the regular languages are the semilinear sets). Let us state the decision problem. Input: A\mathcal{A}, weighted automaton over Nmin\mathbb{N}_{\mathsf{min}} Question: Does it hold that for all S⊆NS\subseteq \mathbb N semilinear, [ ⁣[A] ⁣]−1(S)[\![ \mathcal A ]\!]^{-1}(S) is regular? Remark. This is equivalent to solving the problem over the semiring Nmax=⟨N∪{−∞},max,+,−∞,0⟩\mathbb N_{\mathsf{ max}}=\langle \mathbb N\cup\left\{ -\infty \right\} , \mathsf{ max}, +, -\infty,0\rangle.

Coming soon

Organizer

Boyuan Wang portraitBoyuan Wang
Minghan Wang portraitMinghan Wang
Bochao Li portraitBochao Li
Hongwei Hu portraitHongwei Hu