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;]

---