ترغب بنشر مسار تعليمي؟ اضغط هنا

Detectability of labeled weighted automata over monoids

285   0   0.0 ( 0 )
 نشر من قبل Kuize Zhang
 تاريخ النشر 2020
  مجال البحث الهندسة المعلوماتية
والبحث باللغة English
 تأليف Kuize Zhang




اسأل ChatGPT حول البحث

In this paper, by developing appropriate methods, we for the first time obtain characterization of four fundamental notions of detectability for general labeled weighted automata over monoids (denoted by $mathcal{A}^{mathfrak{M}}$ for short), where the four notions are strong (periodic) detectability (SD and SPD) and weak (periodic) detectability (WD and WPD). Firstly, we formulate the notions of concurrent composition, observer, and detector for $mathcal{A}^{mathfrak{M}}$. Secondly, we use the concurrent composition to give an equivalent condition for SD, use the detector to give an equivalent condition for SPD, and use the observer to give equivalent conditions for WD and WPD, all for general $mathcal{A}^{mathfrak{M}}$ without any assumption. Thirdly, we prove that for a labeled weighted automaton over monoid $(mathbb{Q}^k,+)$ (denoted by $mathcal{A}^{mathbb{Q}^k}$), its concurrent composition, observer, and detector can be computed in NP, $2$-EXPTIME, and $2$-EXPTIME, respectively, by developing novel connections between $mathcal{A}^{mathbb{Q}^k}$ and the NP-complete exact path length problem (proved by [Nyk{a}nen and Ukkonen, 2002]) and a subclass of Presburger arithmetic. As a result, we prove that for $mathcal{A}^{mathbb{Q}^k}$, SD can be verified in coNP, while SPD, WD, and WPD can be verified in $2$-EXPTIME. Particularly, for $mathcal{A}^{mathbb{Q}^k}$ in which from every state, a distinct state can be reached through some unobservable, instantaneous path, its detector can be computed in NP, and SPD can be verified in coNP. Finally, we prove that the problems of verifying SD and SPD of deterministic $mathcal{A}^{mathbb{N}}$ over monoid $(mathbb{N},+)$ are both NP-hard. The original methods developed in this paper will provide foundations for characterizing other fundamental properties (e.g., diagnosability and opacity) in $mathcal{A}^{mathfrak{M}}$.

قيم البحث

اقرأ أيضاً

177 - Kuize Zhang , Joerg Raisch 2021
In this paper, emph{diagnosability} is characterized for a labeled max-plus automaton $mathcal{A}^{mathcal{D}}$ over a dioid $mathcal{D}$ as a real-time system. In order to represent time elapsing, a special class of dioids called emph{progressive} a re considered, in which there is a total canonical order, there is at least one element greater than $textbf{1}$, the product of sufficiently many elements greater than $textbf{1}$ is arbitrarily large, and the cancellative law is satisfied. Then a notion of diagnosability is formulated for $mathcal{A}^{mathcal{D}}$ over a progressive dioid $mathcal{D}$. By developing a notion of emph{concurrent composition}, a sufficient and necessary condition is given for diagnosability of automaton $mathcal{A}^{mathcal{D}}$. It is also proven that the problem of verifying diagnosability of $mathcal{A}^{underline{mathbb{Q}}}$ is coNP-complete, where coNP-hardness even holds for deterministic, deadlock-free, and divergence-free $mathcal{A}^{underline{mathbb{N}}}$, where $underline{mathbb{Q}}$ and $underline{mathbb{N}}$ are the max-plus dioids having elements in $mathbb{Q}cup{-infty}$ and $mathbb{N}cup{-infty}$, respectively.
A weight normalization procedure, commonly called pushing, is introduced for weighted tree automata (wta) over commutative semifields. The normalization preserves the recognized weighted tree language even for nondeterministic wta, but it is most use ful for bottom-up deterministic wta, where it can be used for minimization and equivalence testing. In both applications a careful selection of the weights to be redistributed followed by normalization allows a reduction of the general problem to the corresponding problem for bottom-up deterministic unweighted tree automata. This approach was already successfully used by Mohri and Eisner for the minimization of deterministic weighted string automata. Moreover, the new equivalence test for two wta $M$ and $M$ runs in time $mathcal O((lvert M rvert + lvert Mrvert) cdot log {(lvert Qrvert + lvert Qrvert)})$, where $Q$ and $Q$ are the states of $M$ and $M$, respectively, which improves the previously best run-time $mathcal O(lvert M rvert cdot lvert Mrvert)$.
We study detectability properties for labeled Petri nets and finite automata. We first study weak approximate detectability (WAD) that implies that there exists an infinite observed output sequence of the system such that each prefix of the output se quence with length greater than a given value allows an observer to determine if the current state belongs to a given set. We also consider two new concepts called instant strong detectability (ISD) and eventual strong detectability (ESD). The former property implies that for each possible infinite observed output sequence each prefix of the output sequence allows reconstructing the current state. The latter implies that for each possible infinite observed output sequence, there exists a value such that each prefix of the output sequence with length greater than that value allows reconstructing the current state. Results: WAD: undecidable for labeled Petri nets, PSPACE-complete for finite automata ISD: decidable and EXPSPACE-hard for labeled Petri nets, belongs to P for finite automata ESD: decidable under promptness assumption and EXPSPACE-hard for labeled Petri nets, belongs to P for finite automata SD: belongs to P for finite automata, strengthens Shu and Lins 2011 results based on two assumptions of deadlock-freeness and promptness ISD<SD<ESD<WD<WAD for both labeled Petri nets and finite automata
We show that weighted automata over the field of two elements can be exponentially more compact than non-deterministic finite state automata. To show this, we combine ideas from automata theory and communication complexity. However, weighted automata are also efficiently learnable in Angluins minimal adequate teacher model in a number of queries that is polynomial in the size of the minimal weighted automaton.. We include an algorithm for learning WAs over any field based on a linear algebraic generalization of the Angluin-Schapire algorithm. Together, this produces a surprising result: weighted automata over fields are structured enough that even though they can be very compact, they are still efficiently learnable.
We address the approximate minimization problem for weighted finite automata (WFAs) with weights in $mathbb{R}$, over a one-letter alphabet: to compute the best possible approximation of a WFA given a bound on the number of states. This work is groun ded in Adamyan-Arov-Krein Approximation theory, a remarkable collection of results on the approximation of Hankel operators. In addition to its intrinsic mathematical relevance, this theory has proven to be very effective for model reduction. We adapt these results to the framework of weighted automata over a one-letter alphabet. We provide theoretical guarantees and bounds on the quality of the approximation in the spectral and $ell^2$ norm. We develop an algorithm that, based on the properties of Hankel operators, returns the optimal approximation in the spectral norm.
التعليقات
جاري جلب التعليقات جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا