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.2020.8
URN: urn:nbn:de:0030-drops-116519
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/11651/
Go to the corresponding LIPIcs Volume Portal

Angluin, Dana ; Antonopoulos, Timos ; Fisman, Dana

Strongly Unambiguous Büchi Automata Are Polynomially Predictable With Membership Queries

pdf-format:
LIPIcs-CSL-2020-8.pdf (0.6 MB)

Abstract

A Büchi automaton is strongly unambiguous if every word w ∈ Σ^ω has at most one final path. Many properties of strongly unambiguous Büchi automata (SUBAs) are known. They are fully expressive: every regular ω-language can be represented by a SUBA. Equivalence and containment of SUBAs can be decided in polynomial time. SUBAs may be exponentially smaller than deterministic Muller automata and may be exponentially bigger than deterministic Büchi automata. In this work we show that SUBAs can be learned in polynomial time using membership and certain non-proper equivalence queries, which implies that they are polynomially predictable with membership queries. In contrast, under plausible cryptographic assumptions, non-deterministic Büchi automata are not polynomially predictable with membership queries.

BibTeX - Entry

@InProceedings{angluin_et_al:LIPIcs:2020:11651,
  author =	{Dana Angluin and Timos Antonopoulos and Dana Fisman},
  title =	{{Strongly Unambiguous B{\"u}chi Automata Are Polynomially Predictable With Membership Queries}},
  booktitle =	{28th EACSL Annual Conference on Computer Science Logic (CSL 2020)},
  pages =	{8:1--8:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-132-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{152},
  editor =	{Maribel Fern{\'a}ndez and Anca Muscholl},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/11651},
  URN =		{urn:nbn:de:0030-drops-116519},
  doi =		{10.4230/LIPIcs.CSL.2020.8},
  annote =	{Keywords: Polynomially predictable languages, Automata learning, Strongly unambiguous B{\"u}chi automata, Automata succinctness, Regular ?-languages, Grammatical}
}

Keywords: Polynomially predictable languages, Automata learning, Strongly unambiguous Büchi automata, Automata succinctness, Regular ω-languages, Grammatical
Collection: 28th EACSL Annual Conference on Computer Science Logic (CSL 2020)
Issue Date: 2020
Date of publication: 06.01.2020

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