Document Open Access Logo

New Interpretation and Generalization of the Kameda-Weiner Method

Author Hellis Tamm

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2016.116.pdf
  • Filesize: 429 kB
  • 12 pages

Document Identifiers

Author Details

Hellis Tamm

Cite AsGet BibTex

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)
https://doi.org/10.4230/LIPIcs.ICALP.2016.116

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.
Keywords
  • Nondeterministic finite automata
  • NFA minimization
  • Kameda-Weinermethod
  • atoms of regular languages

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. J. Brzozowski. Canonical regular expressions and minimal state graphs for definite events. In Proceedings of the Symposium on Mathematical Theory of Automata, volume 12 of MRI Symposia Series, pages 529-561. Polytechnic Press, Polytechnic Institute of Brooklyn, N.Y., 1963. Google Scholar
  2. J. Brzozowski and S. Davies. Quotient complexities of atoms in regular ideal languages. Acta Cybernetica, 22(2):293-311, 2015. Google Scholar
  3. J. Brzozowski and H. Tamm. Theory of átomata. In G. Mauri and A. Leporati, editors, Proceedings of the 15th International Conference on Developments in Language Theory (DLT ), volume 6795 of Lecture Notes in Computer Science, pages 105-116. Springer, 2011. Google Scholar
  4. J. Brzozowski and H. Tamm. Minimal nondeterministic finite automata and atoms of regular languages, 2013. URL: http://arxiv.org/abs/1301.5585.
  5. J. Brzozowski and H. Tamm. Theory of átomata. Theor. Comput. Sci., 539:13-27, 2014. Google Scholar
  6. J.-M. Champarnaud and F. Coulon. Enumerating nondeterministic automata for a given language without constructing the canonical automaton. Int. J. Found. Comput. Sci., 16:1253-1266, 2005. Google Scholar
  7. F. Denis, A. Lemay, and A. Terlutte. Residual finite state automata. Fund. Inform., 51:339-368, 2002. Google Scholar
  8. H. Gruber and M. Holzer. Finding lower bounds for nondeterministic state complexity is hard. In Proc. of DLT 2006, volume 4036 of Lecture Notes in Computer Science, pages 363-374. Springer, 2006. Google Scholar
  9. S. Iván. Complexity of atoms, combinatorially. Information Processing Letters, 116:356-360, 2016. Google Scholar
  10. T. Kameda and P. Weiner. On the state minimization of nondeterministic finite automata. IEEE Trans. Comput., C-19(7):617-627, 1970. Google Scholar
  11. M. Rabin and D. Scott. Finite automata and their decision problems. IBM J. Res. and Dev., 3:114-129, 1959. Google Scholar
  12. H. Sengoku. Minimization of nondeterministic finite automata. Master’s thesis, Kyoto University, Department of Information Science, Kyoto University, Kyoto, Japan, 1992. Google Scholar
  13. H. Tamm. Generalization of the double-reversal method of finding a canonical residual finite state automaton. In Proceedings of DCFS 2015, volume 9118 of LNCS, pages 268-279. Springer, 2015. Google Scholar
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