<?xml version="1.0" encoding="UTF-8"?><xml><records><record><source-app name="Biblio" version="7.x">Drupal-Biblio</source-app><ref-type>17</ref-type><contributors><authors><author><style face="normal" font="default" size="100%">Joost K Batenburg</style></author><author><style face="normal" font="default" size="100%">Antal Nagy</style></author><author><style face="normal" font="default" size="100%">Maurice Nivat</style></author></authors></contributors><titles><title><style face="normal" font="default" size="100%">Algorithms, automata, complexity and games Preface</style></title><secondary-title><style face="normal" font="default" size="100%">THEORETICAL COMPUTER SCIENCE</style></secondary-title><short-title><style face="normal" font="default" size="100%">THEOR COMPUT SCI</style></short-title></titles><dates><year><style  face="normal" font="default" size="100%">2008</style></year><pub-dates><date><style  face="normal" font="default" size="100%">2008</style></date></pub-dates></dates><volume><style face="normal" font="default" size="100%">406</style></volume><pages><style face="normal" font="default" size="100%">1</style></pages><isbn><style face="normal" font="default" size="100%">0304-3975</style></isbn><language><style face="normal" font="default" size="100%">eng</style></language><issue><style face="normal" font="default" size="100%">1-2</style></issue><work-type><style face="normal" font="default" size="100%">Journal article</style></work-type><notes><style face="normal" font="default" size="100%">UT: 000260289400001doi: 10.1016/j.tcs.2008.07.010</style></notes></record><record><source-app name="Biblio" version="7.x">Drupal-Biblio</source-app><ref-type>17</ref-type><contributors><authors><author><style face="normal" font="default" size="100%">Joost K Batenburg</style></author><author><style face="normal" font="default" size="100%">Antal Nagy</style></author><author><style face="normal" font="default" size="100%">Maurice Nivat</style></author></authors></contributors><titles><title><style face="normal" font="default" size="100%">In Memoriam Attila Kuba (1953-2006)</style></title><secondary-title><style face="normal" font="default" size="100%">THEORETICAL COMPUTER SCIENCE</style></secondary-title><short-title><style face="normal" font="default" size="100%">THEOR COMPUT SCI</style></short-title></titles><dates><year><style  face="normal" font="default" size="100%">2008</style></year><pub-dates><date><style  face="normal" font="default" size="100%">2008</style></date></pub-dates></dates><pub-location><style face="normal" font="default" size="100%">KUBA A, PUBLICATION LIST</style></pub-location><volume><style face="normal" font="default" size="100%">406</style></volume><pages><style face="normal" font="default" size="100%">2 - 7</style></pages><isbn><style face="normal" font="default" size="100%">0304-3975</style></isbn><language><style face="normal" font="default" size="100%">eng</style></language><issue><style face="normal" font="default" size="100%">1-2</style></issue><work-type><style face="normal" font="default" size="100%">Journal article</style></work-type><notes><style face="normal" font="default" size="100%">UT: 000260289400002doi: 10.1016/j.tcs.2008.07.011</style></notes></record><record><source-app name="Biblio" version="7.x">Drupal-Biblio</source-app><ref-type>17</ref-type><contributors><authors><author><style face="normal" font="default" size="100%">Attila Kuba</style></author><author><style face="normal" font="default" size="100%">Maurice Nivat</style></author></authors></contributors><titles><title><style face="normal" font="default" size="100%">A sufficient condition for non-uniqueness in binary tomography with absorption</style></title><secondary-title><style face="normal" font="default" size="100%">Theoretical Computer Science</style></secondary-title></titles><dates><year><style  face="normal" font="default" size="100%">2005</style></year><pub-dates><date><style  face="normal" font="default" size="100%">2005</style></date></pub-dates></dates><volume><style face="normal" font="default" size="100%">346</style></volume><pages><style face="normal" font="default" size="100%">335-357</style></pages><language><style face="normal" font="default" size="100%">eng</style></language><abstract><style face="normal" font="default" size="100%">&lt;p&gt;A new kind of discrete tomography problem is introduced: the reconstruction of discrete sets from their absorbed projections. A special case of this problem is discussed, namely, the uniqueness of the binary matrices with respect to their absorbed row and column sums when the absorption coefficient is n=log((1+5^0.5)/2). It is proved that if a binary matrix contains a special structure of 0s and 1s, called alternatively corner-connected component, then this binary matrix is non-unique with respect to its absorbed row and column sums. Since it has been proved in another paper [A. Kuba, M. Nivat, Reconstruction of discrete sets with absorption, Linear Algebra Appl. 339 (2001) 171194] that this condition is also necessary, the existence of alternatively corner-connected component in a binary matrix gives a characterization of the non-uniqueness in this case of absorbed projections. &lt;tt&gt; &lt;/tt&gt;&lt;/p&gt;</style></abstract><work-type><style face="normal" font="default" size="100%">Journal Article</style></work-type></record><record><source-app name="Biblio" version="7.x">Drupal-Biblio</source-app><ref-type>17</ref-type><contributors><authors><author><style face="normal" font="default" size="100%">Sara Brunetti</style></author><author><style face="normal" font="default" size="100%">Alberto DelLungo</style></author><author><style face="normal" font="default" size="100%">F. DelRistoro</style></author><author><style face="normal" font="default" size="100%">Attila Kuba</style></author><author><style face="normal" font="default" size="100%">Maurice Nivat</style></author></authors></contributors><titles><title><style face="normal" font="default" size="100%">Reconstruction of 4- and 8-connected convex discrete sets from row and column projections</style></title><secondary-title><style face="normal" font="default" size="100%">Linear Algebra and its Applications</style></secondary-title></titles><dates><year><style  face="normal" font="default" size="100%">2001</style></year></dates><volume><style face="normal" font="default" size="100%">339</style></volume><pages><style face="normal" font="default" size="100%">37-57</style></pages><language><style face="normal" font="default" size="100%">eng</style></language><abstract><style face="normal" font="default" size="100%">&lt;p&gt;In this paper we examine the problem of reconstructing a discrete two-dimensional set from its two orthogonal projection (H,V) when the set satisfies some convexity conditions. We show that the algorithm of the paper [Int. J. Imaging Systems and Technol. 9 (1998) 69] is a good heuristic algorithm but it does not solve the problem for all (H,V) instances. We propose a modification of this algorithm solving the problem for all (H,V) instances, by starting to build the ``spine''. The complexity of our reconstruction algorithm is O(mnˇlog(mn)ˇmin{m2,n2}) in the worst case. However, according to our experimental results, in 99% of the studied cases the algorithm is able to reconstruct a solution without using the newly introduced operation. In such cases the upper bound of the complexity of the algorithm is O(mnˇlog(mn)). A systematic comparison of this algorithm was done and the results show that this algorithm has the better average complexity than other published algorithms. The way of comparison and the results are given in a separate paper [Linear Algebra Appl. (submitted)]. Finally we prove that the problem can be solved in polynomial time also in a class of discrete sets which is larger than the class of convex polyominoes, namely, in the class of 8-connected convex sets. &lt;tt&gt; &lt;/tt&gt;&lt;/p&gt;</style></abstract></record><record><source-app name="Biblio" version="7.x">Drupal-Biblio</source-app><ref-type>17</ref-type><contributors><authors><author><style face="normal" font="default" size="100%">Attila Kuba</style></author><author><style face="normal" font="default" size="100%">Maurice Nivat</style></author></authors></contributors><titles><title><style face="normal" font="default" size="100%">Reconstruction of discrete sets with absorption</style></title><secondary-title><style face="normal" font="default" size="100%">Linear Algebra and its Applications</style></secondary-title></titles><dates><year><style  face="normal" font="default" size="100%">2001</style></year></dates><urls><web-urls><url><style face="normal" font="default" size="100%">http://www.sciencedirect.com/science/article/B6V0R-44CHW26-C/2/e4cd2b3dc91dbb828db15e331a6230cc</style></url></web-urls></urls><volume><style face="normal" font="default" size="100%">339</style></volume><pages><style face="normal" font="default" size="100%">171-194</style></pages><language><style face="normal" font="default" size="100%">eng</style></language><abstract><style face="normal" font="default" size="100%">&lt;p&gt;The uniqueness problem is considered when binary matrices are to be reconstructed from their absorbed row and column sums. Let the absorption coefficient n be selected such that en = (1+5^0.5)/2. Then it is proved that if a binary matrix is non-uniquely determined, then it contains a special pattern of 0s and 1s called composition of alternatively corner-connected components. In a previous paper [Discrete Appl. Math. (submitted)] we proved that this condition is also sufficient, i.e., the existence of such a pattern in the binary matrix is necessary and sufficient for its non-uniqueness. &lt;tt&gt; &lt;/tt&gt;&lt;/p&gt;</style></abstract></record></records></xml>