×

Remarks on separating words. (English) Zbl 1341.68087

Holzer, Markus (ed.) et al., Descriptional complexity of formal systems. 13th international workshop, DCFS 2011, Gießen/Limburg, Germany, July 25–27, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-22599-4/pbk). Lecture Notes in Computer Science 6808, 147-157 (2011).
Summary: The separating words problem asks for the size of the smallest DFA needed to distinguish between two words of length \(\leq n\) (by accepting one and rejecting the other). In this paper we survey what is known and unknown about the problem, consider some variations, and prove several new results.
For the entire collection see [Zbl 1218.68017].

MSC:

68Q45 Formal languages and automata
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Chrobak, M.: Finite automata and unary languages. Theoret. Comput. Sci. 47, 149–158 (1986); Erratum 302, 497–498 (2003) · Zbl 0638.68096 · doi:10.1016/0304-3975(86)90142-8
[2] Currie, J., Petersen, H., Robson, J.M., Shallit, J.: Separating words with small grammars. J. Automata, Languages, and Combinatorics 4, 101–110 (1999) · Zbl 0937.68070
[3] Geffert, V.: Magic numbers in the state hierarchy of finite automata. Inform. Comput. 205, 1652–1670 (2007) · Zbl 1130.68069 · doi:10.1016/j.ic.2007.07.001
[4] Gimadeev, R.A., Vyalyi, M.N.: Identical relations in symmetric groups and separating words with reversible automata. In: Ablayev, F., Mayr, E.W. (eds.) CSR 2010. LNCS, vol. 6072, pp. 144–155. Springer, Heidelberg (2010) · Zbl 1285.68134 · doi:10.1007/978-3-642-13182-0_14
[5] Goralčík, P., Koubek, V.: On discerning words by automata. In: Kott, L. (ed.) ICALP 1986. LNCS, vol. 226, pp. 116–122. Springer, Heidelberg (1986) · Zbl 0594.68049 · doi:10.1007/3-540-16761-7_61
[6] Nozaki, A.: Equivalence problem of non-deterministic finite automata. J. Comput. System Sci. 18, 8–17 (1979) · Zbl 0401.68028 · doi:10.1016/0022-0000(79)90048-5
[7] Robson, J.M.: Separating strings with small automata. Inform. Process. Lett. 30, 209–214 (1989) · Zbl 0666.68051 · doi:10.1016/0020-0190(89)90215-9
[8] Robson, J.M.: Separating words with machines and groups. RAIRO Inform. Théor. App. 30, 81–86 (1996) · Zbl 0851.68076
[9] Shallit, J.: A Second Course in Formal Languages and Automata Theory. Cambridge University Press, Cambridge (2009) · Zbl 1163.68025
[10] Shallit, J., Breitbart, Y.: Automaticity I: Properties of a measure of descriptional complexity. J. Comput. System Sci. 53, 10–25 (1996) · Zbl 0859.68059 · doi:10.1006/jcss.1996.0046
[11] To, A.W.: Unary finite automata vs. arithmetic progressions. Inform. Process. Lett. 109, 1010–1014 (2009) · Zbl 1202.68241 · doi:10.1016/j.ipl.2009.06.005
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.