License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CSL.2017.10
URN: urn:nbn:de:0030-drops-77022
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7702/
Go to the corresponding LIPIcs Volume Portal

Angluin, Dana ; Antonopoulos, Timos ; Fisman, Dana

Query Learning of Derived Omega-Tree Languages in Polynomial Time

pdf-format:
LIPIcs-CSL-2017-10.pdf (4 MB)

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

BibTeX - Entry

@InProceedings{angluin_et_al:LIPIcs:2017:7702,
  author =	{Dana Angluin and Timos Antonopoulos and Dana Fisman},
  title =	{{Query Learning of Derived Omega-Tree Languages in Polynomial Time}},
  booktitle =	{26th EACSL Annual Conference on Computer Science Logic (CSL 2017)},
  pages =	{10:1--10:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-045-3},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{82},
  editor =	{Valentin Goranko and Mads Dam},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7702},
  URN =		{urn:nbn:de:0030-drops-77022},
  doi =		{10.4230/LIPIcs.CSL.2017.10},
  annote =	{Keywords: Learning, queries, infinite trees, derived tree languages, reactive systems}
}

Keywords: Learning, queries, infinite trees, derived tree languages, reactive systems
Collection: 26th EACSL Annual Conference on Computer Science Logic (CSL 2017)
Issue Date: 2017
Date of publication: 16.08.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI