Document Open Access Logo

Query Learning of Derived Omega-Tree Languages in Polynomial Time

Authors Dana Angluin, Timos Antonopoulos, Dana Fisman

PDF
Thumbnail PDF

File

LIPIcs.CSL.2017.10.pdf
  • Filesize: 4.3 MB
  • 21 pages

Document Identifiers

Author Details

Dana Angluin
Timos Antonopoulos
Dana Fisman

Cite As Get BibTex

Dana Angluin, Timos Antonopoulos, and Dana Fisman. Query Learning of Derived Omega-Tree Languages in Polynomial Time. In 26th EACSL Annual Conference on Computer Science Logic (CSL 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 82, pp. 10:1-10:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.CSL.2017.10

Abstract

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 is a general polynomial time reduction
of learning a class of derived omega-tree languages to learning the underlying class of omega-word languages, for any class of omega-word languages recognized by a deterministic Büchi acceptor.
Our reduction, combined with the polynomial time learning algorithm of Maler and Pnueli [Maler and Pneuli, Inform. Comput., 1995]
for the class of weak regular omega-word languages yields the main result. We also show that subset queries that return counterexamples
can be implemented in polynomial time using subset queries that return no counterexamples for deterministic or non-deterministic finite word acceptors, and deterministic or non-deterministic Büchi
omega-word acceptors.

A previous claim of an algorithm to learn regular omega-trees
due to Jayasrirani, Begam and Thomas [Jayasrirani et al., ICGI, 2008] is unfortunately incorrect, as shown in [Angluin, YALEU/DCS/TR-1528, 2016].

Subject Classification

Keywords
  • Learning
  • queries
  • infinite trees
  • derived tree languages
  • reactive systems

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. D. Angluin. Learning regular sets from queries and counterexamples. Inf. Comput., 75(2):87-106, 1987. Google Scholar
  2. D. Angluin. Queries and concept learning. Mach. Learn., 2(4):319-342, 1988. Google Scholar
  3. D. Angluin. Negative results for equivalence queries. Mach. Learn., 5(2):121-150, 1990. Google Scholar
  4. D. Angluin. The class DBW ∩ DCW of ω-languages is identifiable in the limit from positive data and membership queries with polynomial time and data. Technical Report YALEU/DCS/TR-1528, Dept. of Computer Science, Yale University, August 2016. Google Scholar
  5. D. Angluin and D. Fisman. Learning regular omega languages. Theor. Comput. Sci., 650:57-72, 2016. Google Scholar
  6. U. Boker, D. Kuperberg, O. Kupferman, and M. Skrzypczak. Nondeterminism in the presence of a diverse or unknown future. In Automata, Languages, and Programming, 40th Inter. Colloq., ICALP, pages 89-100, 2013. Google Scholar
  7. H. Calbrix, M. Nivat, and A. Podelski. Ultimately periodic words of rational ω-languages. In Proc. of the 9th Inter. Conf. on Mathematical Foundations of Programming Semantics, pages 554-566, 1994. Google Scholar
  8. J. M. Cobleigh, D. Giannakopoulou, and C. S. Păsăreanu. Learning assumptions for compositional verification. In Proc. of the 9th Inter. Conf. on Tools and Algorithms for the Construction and Analysis of Systems, TACAS, pages 331-346, 2003. Google Scholar
  9. A. Farzan, Y. Chenand, E.M. Clarke, Y. Tsay, and B. Wang. Extending automated compositional verification to the full class of omega-regular languages. In Tools and Algorithms for the Construction and Analysis of Systems, TACAS, volume 4963 of LNCS, pages 2-17, 2008. Google Scholar
  10. E. Grädel, W. Thomas, and T. Wilke, editors. Automata, Logics, and Infinite Games: A Guide to Current Research. Springer, 2002. Google Scholar
  11. M. Jayasrirani, M. Humrosia Begam, and D. Gnanaraj Thomas. Learning of regular omega-tree languages. In Grammatical Inference: Algorithms and Applications, 9th Inter. Colloq., ICGI, pages 295-297, 2008. Google Scholar
  12. D. Kuperberg and M. Skrzypczak. On determinisation of good-for-games automata. In Automata, Languages, and Programming, 42nd Inter. Colloq., ICALP, pages 299-310, 2015. Google Scholar
  13. O. Kupferman, S. Safra, and M. Y. Vardi. Relating word and tree automata. Annals of Pure and Applied Logic, 138:126-146, 2006. Google Scholar
  14. C. Löding. Automata on infinite trees. Available online from author, 2011. Google Scholar
  15. O. Maler and A. Pnueli. On the learnability of infinitary regular sets. Inform. Comput., 118(2):316-326, 1995. Google Scholar
  16. Z. Manna and A. Pnueli. A hierarchy of temporal properties. In Proc. of the Ninth Annual ACM Symposium on Principles of Distributed Computing, PODC, pages 377-410, 1990. Google Scholar
  17. D. Niwiński and I. Walukiewicz. Relating hierarchies of word and tree automata. In In Symposium on Theoretical Aspects in Computer Science, STACS, LNCS 1373, pages 320-331. Springer-Verlag, 1998. Google Scholar
  18. D. Perrin and J.-É. Pin. Infinite Words: Automata, Semigroups, Logic and Games. Elsevier, 2004. Google Scholar
  19. M. Rabin. Automata on infinite objects and Church’s problem. Regional Conf. series in mathematics. Conf. Board of the Math. Sci. by the American Mathematical Society, 1972. Google Scholar
  20. F. Vaandrager. Model learning. Commun. ACM, 60(2):86-95, 2017. Google Scholar
  21. K. W. Wagner. A hierarchy of regular sequence sets. In 4th Symposium on Mathematical Foundations of Computer (MFCS), pages 445-449, 1975. Google Scholar
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
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact