2 Search Results for "Tamm, Hellis"

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-dev.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-dev.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}
}
  • Refine by Author
  • 2 Tamm, Hellis

  • Refine by Classification
  • 1 Theory of computation → Formal languages and automata theory

  • Refine by Keyword
  • 1 Atoms
  • 1 Boolean automaton
  • 1 Kameda-Weinermethod
  • 1 NFA minimization
  • 1 Nondeterministic finite automata
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2016
  • 1 2021

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 Imprint Privacy Contact