×

zbMATH — the first resource for mathematics

An approach to computing downward closures. (English) Zbl 1440.68166
Halldórsson, Magnús M. (ed.) et al., Automata, languages, and programming. 42nd international colloquium, ICALP 2015, Kyoto, Japan, July 6–10, 2015. Proceedings. Part II. Berlin: Springer. Lect. Notes Comput. Sci. 9135, 440-451 (2015).
Summary: The downward closure of a word language is the set of all (not necessarily contiguous) subwords of its members. It is well-known that the downward closure of any language is regular. While the downward closure appears to be a powerful abstraction, algorithms for computing a finite automaton for the downward closure of a given language have been established only for few language classes.
This work presents a simple general method for computing downward closures. For language classes that are closed under rational transductions, it is shown that the computation of downward closures can be reduced to checking a certain unboundedness property.
This result is used to prove that downward closures are computable for (i) every language class with effectively semilinear Parikh images that are closed under rational transductions, (ii) matrix languages, and (iii) indexed languages (equivalently, languages accepted by higher-order pushdown automata of order 2).
For the entire collection see [Zbl 1316.68013].

MSC:
68Q45 Formal languages and automata
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Abdulla, P.A., Boasson, L., Bouajjani, A.: Effective lossy queue languages. In: Proc. of ICALP 2001, pp. 639-651 (2001) · Zbl 0986.68044
[2] Abdulla, P.A., Collomb-Annichini, A., Bouajjani, A., Jonsson, B.: Using Forward Reachability Analysis for Verification of Lossy Channel Sys- tems. Form. Method. Syst. Des. 25(1), 39-65 (2004) · Zbl 1073.68675 · doi:10.1023/B:FORM.0000033962.51898.1a
[3] Aho, A.V.: Indexed grammars-an extension of context-free grammars. J. ACM 15(4), 647-671 (1968) · Zbl 0175.27801 · doi:10.1145/321479.321488
[4] Bonnet, R., Finkel, A., Leroux, J., Zeitoun, M.: Model Checking Vector Addition Systems with one zero-test. In: LMCS 8.2:11 (2012) · Zbl 1242.68196
[5] Bouajjani, A., Esparza, J., Maler, O.: Reachability analysis of push- down automata: application to model-checking. In: Proc. of CONCUR 1997, pp. 135-150 (1997)
[6] Colcombet, T.: Regular cost functions, Part I: logic and algebra over words. In: LMCS 9.3 (2013) · Zbl 1280.03044
[7] Courcelle, B.: On constructing obstruction sets of words. Bulletin of the EATCS 44, 178-186 (1991) · Zbl 0744.68074
[8] Czerwiński, W., Martens, W.: A Note on Decidable Separability by Piece- wise Testable Languages (2014).
[9] Dassow, J., Păun, G.: Regulated rewriting in formal language theory. Springer-Verlag, Berlin (1989) · doi:10.1007/978-3-642-74932-2
[10] Dassow, J., Păun, G., Salomaa, A.: Grammars with controlled derivations. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, vol. 2, pp. 101-154. Springer, Heidelberg (1997) · doi:10.1007/978-3-662-07675-0_3
[11] Ehrenfeucht, A., Rozenberg, G., Skyum, S.: A relationship between ET0L and EDT0L languages. Theor. Comput. Sci. 1(4), 325-330 (1976) · Zbl 0339.68055 · doi:10.1016/0304-3975(76)90076-1
[12] Gilman, R.H.: A shrinking lemma for indexed languages. Theor. Comput. Sci. 163(1-2), 277-281 (1996) · Zbl 0874.68168 · doi:10.1016/0304-3975(96)00244-7
[13] Gruber, H., Holzer, M., Kutrib, M.: The size of Higman-Haines sets. Theor. Comput. Sci. 387(2), 167-176 (2007) · Zbl 1143.68035 · doi:10.1016/j.tcs.2007.07.036
[14] Habermehl, P., Meyer, R., Wimmel, H.: The downward-closure of petri net languages. In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G. (eds.) ICALP 2010. LNCS, vol. 6199, pp. 466-477. Springer, Heidelberg (2010) · Zbl 1288.68181 · doi:10.1007/978-3-642-14162-1_39
[15] Haines, L.H.: On free monoids partially ordered by embedding. J. Combin. Theory 6(1), 94-98 (1969) · Zbl 0224.20065 · doi:10.1016/S0021-9800(69)80111-0
[16] Hayashi, T.: On Derivation Trees of Indexed Grammars-An Extension of the uvwxy-Theorem-. Publications of the Research Institute for Mathematical Sciences 9(1), 61-92 (1973) · Zbl 0319.68043 · doi:10.2977/prims/1195192738
[17] Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages and Computation. Addison-Wesley, Reading (1979) · Zbl 0426.68001
[18] Jantzen, M.: On the hierarchy of Petri net languages. RAIRO Theor. Inf. Appl. 13(1), 19-30 (1979) · Zbl 0404.68076
[19] Jullien, P.: Contribution à létude des types d’ordres dispersés. Université de Marseille, PhD thesis (1969)
[20] Kartzow, A.: A pumping lemma for collapsible pushdown graphs of level 2. In: Proc. of CSL 2011, pp. 322-336 (2011) · Zbl 1247.68147
[21] van Leeuwen, J.: Effective constructions in well-partially-ordered free monoids. Discrete Math. 21(3), 237-252 (1978) · Zbl 0384.68073 · doi:10.1016/0012-365X(78)90156-5
[22] Maslov, A.N.: Multilevel stack automata. Problems of Information Transmission 12(1), 38-42 (1976)
[23] Mayr, R.: Undecidable problems in unreliable computations. Theor. Comput. Sci. 297(1-3), 337-354 (2003) · Zbl 1044.68119 · doi:10.1016/S0304-3975(02)00646-1
[24] Parys, P.: A pumping lemma for pushdown graphs of any level. In: Proc. of STACS 2012, pp. 54-65 (2012) · Zbl 1279.68169
[25] Rounds, W.C.: Tree-oriented proofs of some theorems on context-free and indexed languages. In: Proc. of STOC 1970, pp. 109-116 (1970)
[26] Seki, H., Matsumura, T., Fujii, M., Kasami, T.: On multiple context-free grammars. Theor. Comput. Sci. 88(2), 191-229 (1991) · Zbl 0762.68039 · doi:10.1016/0304-3975(91)90374-B
[27] Smith, T.: On infinite words determined by indexed languages. In: Csuhaj-Varjú, E., Dietzfelbinger, M., Ésik, Z. (eds.) MFCS 2014, Part I. LNCS, vol. 8634, pp. 511-522. Springer, Heidelberg (2014) · Zbl 1425.68233
[28] Zetzsche, G.: An approach to computing downward closures (2015). arXiv:1503. 01068 [cs.FL] · Zbl 1355.68171
[29] Zetzsche, G.: Computing downward closures for stacked counter au tomata. In: Proc. of STACS 2015, pp. 743-756 (2015) · Zbl 1355.68171
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.