Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userPushing for weighted tree automata
164
0
0.0
(
0
)
Added by
Ale\\v{s} Bizjak
Publication date
2017
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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 useful 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)$.
rate research
Read More
This short note aims at proving that the isolation problem is undecidable for probabilistic automata with only one probabilistic transition. This problem is known to be undecidable for general probabilistic automata, without restriction on the number of probabilistic transitions. In this note, we develop a simulation technique that allows to simulate any probabilistic automaton with one having only one probabilistic transition.
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.
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}}$.
Algorithms for (nondeterministic) finite-state tree automata (FTAs) are often tested on random FTAs, in which all internal transitions are equiprobable. The run-time results obtained in this manner are usually overly optimistic as most such generated random FTAs are trivial in the sense that the number of states of an equivalent minimal deterministic FTA is extremely small. It is demonstrated that nontrivial random FTAs are obtained only for a narrow band of transition probabilities. Moreover, an analytic analysis yields a formula to approximate the transition probability that yields the most complex random FTAs, which should be used in experiments.
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 grounded 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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
