Search Results

Documents authored by Goldberg, Emmanuel


Document
A Robust Measure on FDFAs Following Duo-Normalized Acceptance

Authors: Dana Fisman, Emmanuel Goldberg, and Oded Zimerman

Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)


Abstract
Families of DFAs (FDFAs) are a computational model recognizing ω-regular languages. They were introduced in the quest of finding a Myhill-Nerode theorem for ω-regular languages and obtaining learning algorithms. FDFAs have been shown to have good qualities in terms of the resources required for computing Boolean operations on them (complementation, union, and intersection) and answering decision problems (emptiness and equivalence); all can be done in non-deterministic logarithmic space. In this paper we study FDFAs with a new type of acceptance condition, duo-normalization, that generalizes the traditional normalization acceptance type. We show that duo-normalized FDFAs are advantageous to normalized FDFAs in terms of succinctness as they can be exponentially smaller. Fortunately this added succinctness doesn't come at the cost of increasing the complexity of Boolean operations and decision problems - they can still be preformed in NLOGSPACE. An important measure of the complexity of an ω-regular language is its position in the Wagner hierarchy (aka the Rabin Index). It is based on the inclusion measure of Muller automata, and for the common ω-automata there exist algorithms computing their position. We develop a similarly robust measure for duo-normalized (and normalized) FDFAs, which we term the diameter measure. We show that the diameter measure corresponds one-to-one to the position in the Wagner hierarchy. We show that computing it for duo-normalized FDFAs is PSPACE-complete, while it can be done in NLOGSPACE for traditional FDFAs.

Cite as

Dana Fisman, Emmanuel Goldberg, and Oded Zimerman. A Robust Measure on FDFAs Following Duo-Normalized Acceptance. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 53:1-53:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{fisman_et_al:LIPIcs.MFCS.2024.53,
  author =	{Fisman, Dana and Goldberg, Emmanuel and Zimerman, Oded},
  title =	{{A Robust Measure on FDFAs Following Duo-Normalized Acceptance}},
  booktitle =	{49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)},
  pages =	{53:1--53:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-335-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{306},
  editor =	{Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.53},
  URN =		{urn:nbn:de:0030-drops-206093},
  doi =		{10.4230/LIPIcs.MFCS.2024.53},
  annote =	{Keywords: Omega-Regular Languages, Families of DFAs, Complexity Measure, Wagner Hierarchy, Rabin Index}
}
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