Abstract
Given a system modeled by a rational relation R, a channel is a pair (E,D) of rational relations that respectively encode and decode binary messages, and such that the composition E R D is the identity relation. This means that the message between E and D has been perfectly transmitted through R. Investigating the links between channels and the growth of rational sets of words, we give new characterizations for relations with channels. In the particular case where the relation is given as a union of functions, we obtain as a consequence the decidability of the synthesis problem with a linear complexity.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bérard, B., Benattar, G., Lime, D., Mullins, J., Roux, O.H., Sassolas, M.: Channel synthesis for finite transducers. In: Dömösi, P., I.S. (eds.) Proceedings of the 13th International Conference on Automata and Formal Languages (AFL 2011), pp. 79–92 (August 2011)
Benattar, G., Bérard, B., Lime, D., Mullins, J., Roux, O.H., Sassolas, M.: Channel Synthesis for Finite Transducers. International Journal of Foundations of Computer Science 23(6), 1241–1260 (2012)
Schewe, S., Finkbeiner, B.: Synthesis of asynchronous systems. In: Puebla, G. (ed.) LOPSTR 2006. LNCS, vol. 4407, pp. 127–142. Springer, Heidelberg (2007)
Millen, J.K.: 20 years of covert channel modeling and analysis. In: Proc. of the 1999 IEEE Symposium on Security and Privacy, pp. 113–114 (May 1999)
Hélouet, L., Zeitoun, M., Degorre, A.: Scenarios and Covert channels: another game. In: de Alfaro, L. (ed.) Proc. of Games in Design and Verification (GDV 2004). ENTCS, vol. 119, pp. 93–116. Elsevier (2005)
Hélouët, L., Roumy, A.: Covert channel detection using information theory. In: Chatzikokolakis, K., Cortier, V. (eds.) Proc. of the 8th Int. Workshop on Security Issues in Concurrency (SecCo 2010) (August 2010)
Maurer, A., Nivat, M.: Rational bijection of rational sets. Acta Inf. 13, 365–378 (1980)
Benattar, G.: Synthèse de systèmes informatiques temporisés non interférents. PhD thesis, Université de Nantes (2011)
Lothaire, M.: Combinatorics on words. Encyclopedia of Mathematics, vol. 17. Addison-Wesley, Reading (1983)
Sakarovitch, J.: Elements of automata theory. Cambridge University Press (2009)
Elgot, C.C., Mezei, J.E.: On relations defined by generalized finite automata. IBM Journal Res. Develop. 9, 47–68 (1965)
Weber, A.: Decomposing a k-valued transducer into k unambiguous ones. RAIRO Theoretical Informatics and Applications 30(5), 379–413 (1996)
Sakarovitch, J., de Souza, R.: On the decomposition of k-valued rational relations. In: Albers, S., Weil, P. (eds.) Proceedings of the 25th Symposium on Theoretical Aspects of Computer Science (STACS 2008), pp. 621–632 (2008)
Harrison, M.A.: Introduction to formal language theory. Addison-Wesley (1978)
Bérard, B., Carton, O.: Channel synthesis revisited. Technical report, LIP6 (2013), http://pagesperso-systeme.lip6.fr/Beatrice.Berard/PDF/rr-channels-BBOC.pdf
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Bérard, B., Carton, O. (2014). Channel Synthesis Revisited. In: Dediu, AH., Martín-Vide, C., Sierra-Rodríguez, JL., Truthe, B. (eds) Language and Automata Theory and Applications. LATA 2014. Lecture Notes in Computer Science, vol 8370. Springer, Cham. https://doi.org/10.1007/978-3-319-04921-2_12
Download citation
DOI: https://doi.org/10.1007/978-3-319-04921-2_12
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-04920-5
Online ISBN: 978-3-319-04921-2
eBook Packages: Computer ScienceComputer Science (R0)