DROPS

Document

DOI: 10.4230/LIPIcs.MFCS.2021.86

Boolean Automata and Atoms of Regular Languages

Authors: Hellis Tamm

Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)

Abstract

We examine the role that atoms of regular languages play in boolean automata. We observe that the size of a minimal boolean automaton of a regular language is directly related to the number of atoms of the language. We present a method to construct minimal boolean automata, using the atoms of a given regular language. The "illegal" cover problem of the Kameda-Weiner method for NFA minimization implies that using the union operation only to construct an automaton from a cover - as is the case with NFAs -, is not sufficient. We show that by using the union and the intersection operations (without the complementation operation), it is possible to construct boolean automata accepting a given language, for a given maximal cover.

Cite as

Hellis Tamm. Boolean Automata and Atoms of Regular Languages. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 86:1-86:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{tamm:LIPIcs.MFCS.2021.86,
  author =	{Tamm, Hellis},
  title =	{{Boolean Automata and Atoms of Regular Languages}},
  booktitle =	{46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
  pages =	{86:1--86:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-201-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{202},
  editor =	{Bonchi, Filippo and Puglisi, Simon J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.86},
  URN =		{urn:nbn:de:0030-drops-145267},
  doi =		{10.4230/LIPIcs.MFCS.2021.86},
  annote =	{Keywords: Boolean automaton, Regular language, Atoms}
}

Document

DOI: 10.4230/LIPIcs.ICALP.2016.116

New Interpretation and Generalization of the Kameda-Weiner Method

Authors: Hellis Tamm

Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

Abstract

We present a reinterpretation of the Kameda-Weiner method of finding a minimal nondeterministic finite automaton (NFA) of a language, in terms of atoms of the language. We introduce a method to generate NFAs from a set of languages, and show that the Kameda-Weiner method is a special case of it. Our method provides a unified view of the construction of several known NFAs, including the canonical residual finite state automaton and the atomaton of the language.

Cite as

Hellis Tamm. New Interpretation and Generalization of the Kameda-Weiner Method. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 116:1-116:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{tamm:LIPIcs.ICALP.2016.116,
  author =	{Tamm, Hellis},
  title =	{{New Interpretation and Generalization of the Kameda-Weiner Method}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{116:1--116:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.116},
  URN =		{urn:nbn:de:0030-drops-62518},
  doi =		{10.4230/LIPIcs.ICALP.2016.116},
  annote =	{Keywords: Nondeterministic finite automata, NFA minimization, Kameda-Weinermethod, atoms of regular languages}
}

Search Results

Documents authored by Tamm, Hellis

Boolean Automata and Atoms of Regular Languages

Abstract

Cite as

New Interpretation and Generalization of the Kameda-Weiner Method

Abstract

Cite as

Thanks for your feedback!

Could not send message