Non-Deterministic Finite Cover Automata – Facultatea de Informatică

Published in Volume XXV, Issue 1, 2015, pages 3-28, doi: 10.7561/SACS.2015.1.3

Authors: C. Câmpeanu

Abstract

The concept of Deterministic Finite Cover Automata (DFCA) was introduced at WIA ’98, as a more compact representation than Deterministic Finite Automata (DFA) for finite languages. In some cases representing a finite language using a Non-deterministic Finite Automata (NFA) may significantly reduce the number of required states. The combined power of the succinctness of the representation of finite languages using both cover languages and non-determinism has been suggested, but never systematically studied. In the present paper, for non-deterministic finite cover automata (NFCA) and l-non-deterministic finite cover automaton (l-NFCA), we show that minimization can be as hard as minimizing NFAs for regular languages, even in the case of NFCAs using unary alphabets. Moreover, we show how we can adapt the methods used to reduce, or minimize the size of NFAs/DFCAs/l-DFCAs, for simplifying NFCAs/l-NFCAs.

Full Text (PDF)

References

[1] M. Agrawal, N. Kayal, and N. Saxena. PRIMES is in P. Annals of mathematics, 160(2):781–793, 2004. doi:10.4007/annals.2004.160.781.

[2] J. Amilhastre, P. Janssen, and M-C. Vilarem. FA minimisation heuristics for a class of finite languages. In O. Boldt and H. Jü rgensen, editors, Proceedings of the 4th International Workshop on Implementing Automata (WIA’ 99), volume 2214, pages 1–12, 2001. doi: 10.1007/3-540-45526-4_1.

[3] J.-C. Birget. Intersection and union of regular languages and state complexity. Information Processing Letters, 43(4):185–190, 1992. doi: 10.1016/0020-0190(92)90198-5.

[4] C. Câmpeanu. Simplifying nondeterministic finite cover automata. In Z. Ésik and Z. Fü löp, editors, Proceedings of the 14th International Conference on Automata and Formal Languages (AFL 2014), volume 151 of EPTCS, pages 162–173, 2014. doi:10.4204/EPTCS.151.11.

[5] C. Câmpeanu, N. Sântean, and S. Yu. Mergible states in large NFA. Theoretical Computer Science, 330(1):23–34, 2004. doi:10.1016/j.tcs.2004.09.008.

[6] C. Câmpeanu, A. Păun, and S. Yu. An efficient algorithm for constructing minimal cover automata for finite languages. International Journal of Foundations of Computer Science, 13(1):83–97, 2002. doi:10.1142/S0129054102000960.

[7] C. Câmpeanu, K. Culik II, K. Salomaa, and S. Yu. State complexity of basic operations on finite languages. In O. Boldt and H. Jü rgensen, editors, Proceedings of the 4th International Workshop on Implementing Automata (WIA’ 99), volume 2214 of Lecture Notes in Computer Science, pages 60–70, 2001. doi:10.1007/3-540-45526-4_6.

[8] C. Câmpeanu, N. Sântean, and S. Yu. Minimal cover-automata for finite languages. Theoretical Computer Science, 267(1-2):3–16, 2001. doi:10.1016/S0304-3975(00)00292-9.

[9] C. Câmpeanu, N. Sântean, and S. Yu. A family of NFAs free of state reductions. Journal of Automata Languages and Combinatorics, 12(1):69–78, 2007. Available from: http://dl.acm.org/citation.cfm?id=1463362.1463367.

[10] M. Chrobak. Finite automata and unary languages. Theoretical Computer Science, 47:149–158, 1986. doi:10.1016/0304-3975(86)90142-8.

[11] I. Glaister and J. Shallit. A lower bound technique for the size of non-deterministic finite automata. Information Processing Letters, 59(2):75– 77, 1996. doi:10.1016/0020-0190(96)00095-6.

[12] G. Gramlich. Probabilistic and nondeterministic unary automata. In B. Rovan and P. Vojtás, editors, Proceedings of the 28th International Symposium on Mathematical Foundations of Computer Science (MFCS 2003), volume 2747 of Lecture Notes in Computer Science, pages 460– 469, 2003. doi:10.1007/978-3-540-45138-9_40.

[13] H. Gruber and M. Holzer. Finding lower bounds for nondeterministic state complexity is hard. In Oscar H. Ibarra and Zhe Dang, editors, Proceedings of the 10th International Conference on Developments in Language Theory (DLT 2006), volume 4036 of Lecture Notes in Computer Science, pages 363–374, 2006. doi:10.1007/11779148_33.

[14] H. Gruber and M. Holzer. Computational complexity of NFA minimization for finite and unary languages. In R. Loos, S.Z. Fazekas, and C. Martín-Vide, editors, Proceedings of the 1st International Conference on Language and Automata Theory and Applications (LATA 2007), pages 261–272, 2007. Available from: http://www.hermann-gruber.com/data/lata07-final.pdf.

[15] M. Holzer and M. Kutrib. State complexity of basic operations on nondeterministic finite automata. In J.-M. Champarnaud and D. Maurel, editors, Implementation and Application of Automata, volume 2608 of Lecture Notes in Computer Science, pages 148–157. 2003. doi: 10.1007/3-540-44977-9_14.

[16] M. Holzer and M. Kutrib. Unary language operations and their non-deterministic state complexity. In M. Ito and M. Toyama, editors, Proceedings of the 6th International Conference on Developments in Language Theory (DLT 2002), volume 2450 of Lecture Notes in Computer Science, pages 162–172, 2003. doi:10.1007/3-540-45005-X_14.

[17] M. Holzer and M. Kutrib. Descriptional and computational complexity of finite automata. In A.H. Dediu, A.M. Ionescu, and C. Martin- Vide, editors, Proceedings of the Third International Conference on Language and Automata Theory and Applications (LATA 2009), volume 5457 of Lecture Notes in Computer Science, pages 23–42, 2009. doi: 10.1007/978-3-642-00982-2_3.

[18] M. Holzer and M. Kutrib. Nondeterministic finite automata – recent results on the descriptional and computational complexity. International Journal of Foundation of Computing Science, 20(4):563–580, 2009. doi: 10.1142/S0129054109006747.

[19] J. Hopcroft. An n log n algorithm for minimizing states in a finite automaton. In Z. Kohavi and A. Paz, editors, Theory of Machines and Computations, pages 189–196. Academic Press, New York, 1971.

[20] J.E. Hopcroft and J.D. Ullman. Introduction to Automata Theory, Languages and Computation. Addison-Wesley, 1979.

[21] L. Ilie, G. Navarro, and S. Yu. On NFA reductions. In J. Karhumäki, H. Maurer, G. Păun, and G. Rozenberg, editors, Theory Is Forever – Essays Dedicated to Arto Salomaa on the Occasion of His 70th Birthday, volume 3113 of Lecture Notes in Computer Science, pages 112–124. 2004. doi:10.1007/978-3-540-27812-2_11.

[22] T. Jiang and B. Ravikumar. Minimal NFA problems are hard. In Javier Leach Albert, Burkhard Monien, and Mario Rodríguez Artalejo, editors, Automata, Languages and Programming, volume 510 of Lecture Notes in Computer Science, pages 629–640. Springer Berlin Heidelberg, 1991. doi:10.1007/3-540-54233-7_169.

[23] N. Koblitz. A Course in Number Theory and Cryptography. Springer, 1994. doi:10.1007/978-1-4419-8592-7.

[24] H. Körner. A time and space efficient algorithm for minimizing cover automata for finite languages. International Journal of Foundations of Computer Science, 14(6):1071–1086, 2003. doi:10.1142/ S0129054103002187.

[25] A. N. Maslov. Estimates of the number of states of finite automata. Soviet Mathematics Doklady, 11:1373–1374, 1970.

[26] A. N. Maslov. Cyclic shift operation for languages. Problems of Information Transmission, 9:333–338, 1973.

[27] F. Mera and G. Pighizzini. Complementing unary non-deterministic automata. Theoretical Computer Science, 330(2):349–360, 2005. doi: 10.1016/j.tcs.2004.04.015.

[28] E. F. Moore. Gedanken-experiments on sequential machines. Automata Studies, Annals of Mathematics Studies, 34:129–153, 1956.

[29] D. Revuz. Minimisation of acyclic deterministic automata in linear time. Theoretical Computer Science, 92(1):181–189, 1992. doi:10. 1016/0304-3975(92)90142-3.

[30] S. Yu. Regular languages. In Grzegorz Rozenberg and Arto Salomaa, editors, Handbook of Formal Languages, volume 1, pages 41–110. Springer, 1997. Available from: http://dl.acm.org/citation.cfm?id=267846.267848.

[31] S. Yu, Q. Zhuang, and K. Salomaa. The state complexities of some basic operations on regular languages. Theoretical Computer Science, 125(2):315–328, 1994. doi:10.1016/0304-3975(92)00011-F.

Bibtex

@article{sacscuza:campeanu2015nfca,
  title={Non-Deterministic Finite Cover Automata},
  author={C. C{'a}mpeanu},
  journal={Scientific Annals of Computer Science},
  volume={25},
  number={1},
  organization={``A.I. Cuza'' University, Iasi, Romania},
  year={2015},
  pages={3--28},
  doi={10.7561/SACS.2015.1.3},
  publisher={``A.I. Cuza'' University Press}
}