1 Search Results for "Frenkel, Hadar"


Document
Inferring Symbolic Automata

Authors: Dana Fisman, Hadar Frenkel, and Sandra Zilles

Published in: LIPIcs, Volume 216, 30th EACSL Annual Conference on Computer Science Logic (CSL 2022)


Abstract
We study the learnability of symbolic finite state automata, 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 efficient learnability of SFAs in this paradigm, from which we obtain the first negative result. The main focus of our work lies in the learnability of SFAs under the paradigm of identification in the limit using polynomial time and data. We provide a necessary condition and a sufficient condition for efficient learnability of SFAs in this paradigm, from which we derive a positive and a negative result.

Cite as

Dana Fisman, Hadar Frenkel, and Sandra Zilles. Inferring Symbolic Automata. In 30th EACSL Annual Conference on Computer Science Logic (CSL 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 216, pp. 21:1-21:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{fisman_et_al:LIPIcs.CSL.2022.21,
  author =	{Fisman, Dana and Frenkel, Hadar and Zilles, Sandra},
  title =	{{Inferring Symbolic Automata}},
  booktitle =	{30th EACSL Annual Conference on Computer Science Logic (CSL 2022)},
  pages =	{21:1--21:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-218-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{216},
  editor =	{Manea, Florin and Simpson, Alex},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2022.21},
  URN =		{urn:nbn:de:0030-drops-157412},
  doi =		{10.4230/LIPIcs.CSL.2022.21},
  annote =	{Keywords: Symbolic Finite State Automata, Query Learning, Characteristic Sets}
}
  • Refine by Author
  • 1 Fisman, Dana
  • 1 Frenkel, Hadar
  • 1 Zilles, Sandra

  • Refine by Classification
  • 1 Computing methodologies → Machine learning
  • 1 Theory of computation → Formal languages and automata theory
  • 1 Theory of computation → Models of computation
  • 1 Theory of computation → Regular languages

  • Refine by Keyword
  • 1 Characteristic Sets
  • 1 Query Learning
  • 1 Symbolic Finite State Automata

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2022

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail