zbMATH — the first resource for mathematics

Synchronizing relations on words. (English) Zbl 1335.68118
Summary: While the theory of languages of words is very mature, our understanding of relations on words is still lagging behind. And yet such relations appear in many new applications such as verification of parameterized systems, querying graph-structured data, and information extraction, for instance. Classes of well-behaved relations typically used in such applications are obtained by adapting some of the equivalent definitions of regularity of words for relations, leading to non-equivalent notions of recognizable, regular, and rational relations. The goal of this paper is to propose a systematic way of defining classes of relations on words, of which these three classes are just natural examples, and to demonstrate its advantages compared to some of the standard techniques for studying word relations. The key idea is that of a synchronization of a pair of words, which is a word over an extended alphabet. Using it, we define classes of relations via classes of regular languages over a fixed alphabet, just \(\{1,2\}\) for binary relations. We characterize some of the standard classes of relations on words via finiteness of parameters of synchronization languages, called shift, lag, and shiftlag. We describe these conditions in terms of the structure of cycles of graphs underlying automata, thereby showing their decidability. We show that for these classes there exist canonical synchronization languages, and every class of relations can be effectively re-synchronized using those canonical representatives. We also give sufficient conditions on synchronization languages, defined in terms of injectivity and surjectivity of their Parikh images, that guarantee closure under intersection and complement of the classes of relations they define.

68Q45 Formal languages and automata
68R15 Combinatorics on words
jSpin; SPIN
Full Text: DOI
[1] Abdulla, J., Jonnson, B., Nilsson, M., Saksena, M.: A survey of regular model checking. In: (CONCUR’03), pp 35-48 (2003) · Zbl 1099.68055
[2] Alur, R., Madhusudan, P.: Visibly pushdown languages. In: (STOC’04), pp 202-211 (2004) · Zbl 1192.68396
[3] Angles, R., Gutiérrez, C.: Survey of graph database models. ACM Comput. Surv. 40(1) (2008)
[4] Anyanwu, K., Sheth, A.: \(ρ\)-queries: enabling querying for semantic associations on the semantic web. In: 12th International World Wide Web Conference (WWW’03), pp 690-699 (2003) · Zbl 1115.68101
[5] Barceló, P., Figueira, D., Libkin, L.: Graph logics with rational relations and the generalized intersection problem. In: (LICS’12), pp 115-124 (2012), doi:10.1109/LICS.2012.23 · Zbl 1362.68063
[6] Barceló, P; Libkin, L; Lin, AW; Wood, PT, Expressive languages for path queries over graph-structured data, ACM Trans. Database Syst., 37, 31, (2012)
[7] Ben-Ari, M.: Principles of the Spin model checker. Springer (2008) · Zbl 1142.68044
[8] Benedikt, M; Libkin, L; Schwentick, T; Segoufin, L, Definable relations and first-order query languages over strings, J. ACM, 50, 694-751, (2003) · Zbl 1325.03031
[9] Berstel, J.: Transductions and Context-Free Languages. B. G. Teubner (1979) · Zbl 0424.68040
[10] Blumensath, A., Grädel, E.: Automatic structures. In: LICS, pp 51-62 (2000) · Zbl 0456.68097
[11] Bojańczyk, M.: Automata for data words and data trees. In: 21st International Conference on Rewriting Techniques and Applications (RTA), Vol. 6, pp 1-4 (2010) · Zbl 0783.68065
[12] Bouajjani, A., Jonsson, B., Nilsson, M., Touili, T.: Regular model checking. In: (CAV’00), pp 403-418. Springer-Verlag, London (2000) · Zbl 0974.68118
[13] Carton, O, The growth ratio of synchronous rational relations is unique, Theor. Comput. Sci., 376, 52-59, (2007) · Zbl 1111.68052
[14] Carton, O., Choffrut, C., Grigorieff, S.: Decision problems among the main subfamilies of rational relations 40(2), 255-275 (2006) · Zbl 1112.03008
[15] Choffrut, C, Relations over words and logic: A chronology, Bull EATCS, 89, 159-163, (2006) · Zbl 1169.68460
[16] Choffrut, C; Culik II, K, Properties of finite and pushdown transducers, SIAM J. Comput., 12, 300-315, (1983) · Zbl 0512.68065
[17] Elgot, CC; Mezei, JE, On relations defined by generalized finite automata, IBM J. Res. Dev., 9, 47-68, (1965) · Zbl 0135.00704
[18] Fagin, R., Kimelfeld, B., Reiss, F., Vansummeren, S.: A formal framework for information extraction. In: (PODS’13) (2013). to appear · Zbl 1333.68098
[19] Figueira, D., Libkin, L.: Synchronizing relations on words. In: (STACS’14), Vol. 25, pp 93-104. Leibniz-Zentrum für Informatik, Lyon (2014), doi:10.4230/LIPIcs.STACS.2014.518 · Zbl 1359.68240
[20] Frougny, C; Sakarovitch, J, Synchronized rational relations of finite and infinite words, Theor. Comput. Sci., 108, 45-82, (1993) · Zbl 0783.68065
[21] Harju, T., Mateescu, A., Salomaa, A.: Shuffle on trajectories: The schützenberger product and related operations. In: MFCS, pp 503-511 (1998) · Zbl 0914.68112
[22] Hell, P., Nešetřil, J.: Graphs and Homomorphisms. Oxford University Press (2004) · Zbl 0154.25801
[23] Jonsson, B., Nilsson, M.: Transitive closures of regular relations for verifying infinite-state systems. In: (TACAS’00), pp 220-234. Springer-Verlag (2000) · Zbl 0960.68039
[24] Leguy, J, Transductions rationnelles décroissantes, ITA, 15, 141-148, (1981) · Zbl 0456.68097
[25] McMillan, K.L.: Symbolic Model Checking. Kluwer Academic Publishers (1993) · Zbl 0784.68004
[26] Milo, R; Shen-Orr, S; Itzkovitz, S; Kashtan, N; Chklovskii, D; Alon, U, Network motifs: simple building blocks of complex networks, Science, 298, 824-827, (2002)
[27] Neven, F.: Automata, Logic, and XML. In: (CSL’02), pp 2-26 (2002) · Zbl 1020.68044
[28] Nivat, M, Transduction des langages de chomsky, Ann. Inst. Fourier, 18, 339-455, (1968) · Zbl 0313.68065
[29] Parikh, R, On context-free languages, J. ACM, 13, 570-581, (1966) · Zbl 0154.25801
[30] Sakarovitch, J.: Elements of Automata Theory. Cambridge University Press (2009) · Zbl 1188.68177
[31] Schwentick, T, Automata for XML - a survey, J. Comput. Syst. Sci., 73, 289-315, (2007) · Zbl 1115.68101
[32] To, A.W., Libkin, L.: Algorithmic metatheorems for decidable LTL model checking over infinite systems. In: (FOSSACS’10), pp 221-236 (2010) · Zbl 1284.68416
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.