×

Random generation of deterministic tree (walking) automata. (English) Zbl 1248.68298

Maneth, Sebastian (ed.), Implementation and application of automata. 14th international conference, CIAA 2009, Sydney, Australia, July 14–17, 2009. Proceedings. Berlin: Springer (ISBN 978-3-642-02978-3/pbk). Lecture Notes in Computer Science 5642, 115-124 (2009).
Summary: Uniform random generators deliver a simple empirical means to estimate the average complexity of an algorithm. We present a general rejection algorithm that generates sequential letter-to-letter transducers up to isomorphism. We tailor this general scheme to randomly generate deterministic tree walking automata and deterministic top-down tree automata. We apply our implementation of the generator to the estimation of the average complexity of a deterministic tree walking automata to nondeterministic top-down tree automata construction we also implemented.
For the entire collection see [Zbl 1165.68016].

MSC:

68Q45 Formal languages and automata

Software:

Antichains; REGAL
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Wulf, M.D., Doyen, L., Henzinger, T.A., Raskin, J.F.: Antichains: A new algorithm for checking universality of finite automata. In: Ball, T., Jones, R.B. (eds.) CAV 2006. LNCS, vol. 4144, pp. 17–30. Springer, Heidelberg (2006) · Zbl 1188.68171 · doi:10.1007/11817963_5
[2] van Glabbeek, R.J., Ploeger, B.: Five determinisation algorithms. In: Ibarra, O.H., Ravikumar, B. (eds.) CIAA 2008. LNCS, vol. 5148, pp. 161–170. Springer, Heidelberg (2008) · Zbl 1172.68535 · doi:10.1007/978-3-540-70844-5_17
[3] Schewe, S.: Büchi complementation made tight. In: [17], pp. 661–672 · Zbl 1236.68176
[4] Bassino, F., David, J., Nicaud, C.: On the average complexity of Moore’s state minimization algorithm. In: [17], pp. 123–134 · Zbl 1236.68162
[5] Neven, F.: Automata theory for XML researchers. SIGMOD Record 31(3), 39–46 (2002) · Zbl 05444552 · doi:10.1145/601858.601869
[6] Murata, M., Lee, D., Mani, M., Kawaguchi, K.: Taxonomy of XML schema languages using formal language theory. ACM Transactions on Internet Technology 5(4), 660–704 (2005) · Zbl 05458172 · doi:10.1145/1111627.1111631
[7] Engelfriet, J., Hoogeboom, H.J.: Tree-walking pebble automata. In: Karhumäki, J., Maurer, H.A., Paun, G., Rozenberg, G. (eds.) Jewels are Forever, pp. 72–83. Springer, Heidelberg (1999) · Zbl 0944.68108 · doi:10.1007/978-3-642-60207-8_7
[8] Bojańczyk, M., Colcombet, T.: Tree-walking automata do not recognize all regular languages. SIAM Journal on Computing 38(2), 658–701 (2008) · Zbl 1172.68030 · doi:10.1137/050645427
[9] ten Cate, B., Segoufin, L.: XPath, transitive closure logic, and nested tree walking automata. In: Lenzerini, M., Lembo, D. (eds.) PODS 2008, pp. 251–260 (2008) · Zbl 1327.03024 · doi:10.1145/1376916.1376952
[10] Bassino, F., Nicaud, C.: Enumeration and random generation of accessible automata. Theoretical Computer Science 381(1-3), 86–104 (2007) · Zbl 1188.68168 · doi:10.1016/j.tcs.2007.04.001
[11] Bassino, F., David, J., Nicaud, C.: Enumeration and random generation of possibly incomplete deterministic automata. Pure Mathematics and Applications (2009) · Zbl 1224.68043
[12] Champarnaud, J.M., Paranthoën, T.: Random generation of DFAs. Theoretical Computer Science 330(2), 221–235 (2005) · Zbl 1078.68078 · doi:10.1016/j.tcs.2004.03.072
[13] Bassino, F., David, J., Nicaud, C.: REGAL: A library to randomly and exhaustively generate automata. In: Holub, J., Žďárek, J. (eds.) CIAA 2007. LNCS, vol. 4783, pp. 303–305. Springer, Heidelberg (2007) · Zbl 1139.68355 · doi:10.1007/978-3-540-76336-9_28
[14] Tabakov, D., Vardi, M.Y.: Experimental evaluation of classical automata constructions. In: Sutcliffe, G., Voronkov, A. (eds.) LPAR 2005. LNCS, vol. 3835, pp. 396–411. Springer, Heidelberg (2005) · Zbl 1143.68443 · doi:10.1007/11591191_28
[15] Chen, Y.F., Farzan, A., Clarke, E.M., Tsay, Y.K., Wang, B.Y.: Learning minimal separating DFA’s for compositional verification. In: Kowalewski, S., Philippou, A. (eds.) TACAS 2009. LNCS, vol. 5505. Springer, Heidelberg (2009) · Zbl 1234.68166
[16] Comon, H., Dauchet, M., Gilleron, R., Löding, C., Jacquemard, F., Lugiez, D., Tison, S., Tommasi, M.: Tree Automata Techniques and Applications (2007)
[17] Albers, S., Marion, J.Y. (eds.): STACS 2009. Dagstuhl Seminar Proceedings, vol. 09001 (2009)
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.