Search

• < Previous
• 1
• Next >

---

Families of DFAs as Acceptors of $\omega$-Regular Languages

Dana Angluin ; Udi Boker ; Dana Fisman.

Families of DFAs (FDFAs) provide an alternative formalism for recognizing $\omega$-regular languages. The motivation for introducing them was a desired correlation between the automaton states and right congruence relations, in a manner similar to the Myhill-Nerode theorem for regular languages.&nbsp;[&hellip;]

---

Query learning of derived $\omega$-tree languages in polynomial time

Dana Angluin ; Timos Antonopoulos ; Dana Fisman.

We present the first polynomial time algorithm to learn nontrivial classes of languages of infinite trees. Specifically, our algorithm uses membership and equivalence queries to learn classes of $\omega$-tree languages derived from weak regular $\omega$-word languages in polynomial time. The method&nbsp;[&hellip;]

---

Learning of Structurally Unambiguous Probabilistic Grammars

Dana Fisman ; Dolav Nitay ; Michal Ziv-Ukelson.

The problem of identifying a probabilistic context free grammar has two aspects: the first is determining the grammar's topology (the rules of the grammar) and the second is estimating probabilistic weights for each rule. Given the hardness results for learning context-free grammars in general, and&nbsp;[&hellip;]

---

Inferring Symbolic Automata

Dana Fisman ; Hadar Frenkel ; Sandra Zilles.

We study the learnability of symbolic finite state automata (SFA), a model shown useful in many applications in software verification. The state-of-the-art literature on this topic follows the query learning paradigm, and so far all obtained results are positive. We provide a necessary condition for&nbsp;[&hellip;]

---

Constructing Concise Characteristic Samples for Acceptors of Omega Regular Languages

Dana Angluin ; Dana Fisman.

A characteristic sample for a language $L$ and a learning algorithm $\textbf{L}$ is a finite sample of words $T_L$ labeled by their membership in $L$ such that for any sample $T \supseteq T_L$ consistent with $L$, on input $T$ the learning algorithm $\textbf{L}$ returns a hypothesis equivalent to&nbsp;[&hellip;]

---