waashk/dblp huggingface dataset:
information systems revisited - the general continuous case. in this paper a new notion of continuous information system is introduced. it is shown that the information systems of this kind generate exactly the continuous domains. the new information systems are of the same logic-oriented style as the information systems first introduced by scott in 1982: they consist of a set of tokens, a consistency predicate and an entailment relation satisfying a set of natural axioms. it is shown that continuous information systems are closely related to abstract bases. indeed, both categories are equivalent. since it is known that the categories of abstract bases and/or continuous domains are equivalent, it follows that the category of continuous information systems is also equivalent to that of continuous domains. in applications, mostly subclasses of continuous domains are considered. for example, the domains have to be pointed, algebraic, bounded-complete or fs. conditions are presented that, when fulfilled by a continuous information system, force the generated domain to belong to the required subclass. in most cases the requirements are not only sufficient but also necessary.
apartness, compactness and nearness. we investigate constructively a pre-apartness structure that is classically important in the characterisation of compact proximity spaces, and that may help identify a good constructive notion of compactness for not-necessarily-uniform apartness spaces. in addition, we produce what may be the right notion of ''nearness'' in the theory of apartness spaces.
on computational environments of topological spaces. as has been disclosed by k. martin, a large number of important topological spaces do not have any continuous domain as their computational model. so it is of interest to study new kinds of pragmatic computational environments so as to model more topological spaces. in this paper we focus on bounded complete continuous posets with enough maximal points, which are shown to be a good choice for computational environments of tychonoff spaces with no directed complete model. it is proved that the maximal point space of a choquet complete weak domain is also choquet complete. furthermore, it is proved that x is a tychonoff space iff x has a bounded complete weak domain environment. and it is also shown that hausdorff compactifications of tychonoff spaces can be realized via some of their computational environments.
on the possibility of learning in reactive environments with arbitrary dependence. we address the problem of reinforcement learning in which observations may exhibit an arbitrary form of stochastic dependence on past observations and actions, i.e. environments more general than (po)mdps. the task for an agent is to attain the best possible asymptotic reward where the true generating environment is unknown, but belongs to a known countable family of environments. we find some sufficient conditions on the class of environments under which an agent exists which attains the best asymptotic reward for any environment in the class. we analyze how tight these conditions are, and how they relate to different probabilistic assumptions known in reinforcement learning and related fields, such as markov decision processes and mixing conditions.
static space-times naturally lead to quasi-pseudometrics. the standard 4-dimensional minkowski space-time of special relativity is based on the 3-dimensional euclidean metric. in 1967, h. busemann showed that similar static space-time models can be based on an arbitrary metric space. in this paper, we search for the broadest possible generalization of a metric under which a construction of a static space-time leads to a physically reasonable space-time model. it turns out that this broadest possible generalization is related to the known notion of a quasi-pseudometric.
modeling time and topology for animation and visualization with examples on parametric geometry. the art of animation relies upon modeling objects that change over time. a sequence of static images is displayed to produce an illusion of motion. even for simple cases, a careful analysis exposes that formal topological guarantees are often lacking. this absence of rigor can result in subtle, but significant, topological flaws. a new modeling approach is proposed to integrate topological rigor with a continuous model of time. examples will be given for bezier curves, while indicating extensions to a richer class of parametric curves and surfaces. applications to scientific visualization for molecular modeling are discussed. prototype animations are available for viewing over the web.
metric spaces and fs-domains. in this article we give general conditions on a metric space to insure that the poset of closed formal balls is an fs-domain.
the zariski spectrum as a formal geometry. we choose formal topology to deal in a basic manner with the zariski spectra of commutative rings and their structure sheaves. by casting prime and maximal ideals in a secondary role, we thus wish to prepare a constructive and predicative framework for abstract algebraic geometry. in contrast to the classical approach, neither points nor stalks need occur, let alone any instance of the axiom of choice. as compared with the topos-theoretic treatments that may be rendered predicative as well, the road we follow is built from more elementary material. the formal counterpart of the structure sheaf which we present first is our guiding example for a notion of a sheaf on a formal topology. we next define the category of formal geometries, a natural abstraction from that of locally ringed spaces. this allows us to eventually phrase and prove, still within the language of opens and sections, the universal property of the zariski spectrum. our version appears to be the only one that is explicitly point-free.
fine hierarchies and m-reducibilities in theoretical computer science. this is a survey of results about versions of fine hierarchies and many-one reducibilities that appear in different parts of theoretical computer science. these notions and related techniques play a crucial role in understanding complexity of finite and infinite computations. we try not only to present the corresponding notions and facts from the particular fields but also to identify the unifying notions, techniques and ideas.
finitary formal topologies and stone's representation theorem. we study the concept of finitary formal topology, a point-free version of a topological space with a basis of compact open subsets. the notion of finitary formal topology is defined from the perspective of the basic picture (introduced by the second author) and thus it is endowed with a binary positivity relation. as an application, we prove a constructive version of stone's representation theorem for distributive lattices. we work within the framework of a minimalist foundation (as proposed by maria emilia maietti and the second author). both inductive and co-inductive methods are used in most proofs.
enriched categories and models for spaces of evolving states. partially ordered sets, causets, partially ordered spaces, and their local counterparts are now often used to model systems in computer science and theoretical physics. the order models 'time' which is often not globally given. in this setting, directed paths are important objects of study, as they correspond to an evolving state or particle traversing the system. we model both the 'space' and the directed paths by a simplicially enriched category, and show how to adapt some classical constructions to produce a differential graded enrichment.
scanning integer matrices by means of two rectangular windows. this paper deals with the reconstruction of integer matrices from rectangular scans. in particular, since the case of one rectangular scan has already been treated in a previous paper, we consider two rectangular scans, given as two integer matrices, and we investigate the existence and the possibility of reconstruction of a third binary matrix which is compatible with them. furthermore, our inspection implies interesting side results about the number of these reconstructed matrices for different choices of the dimensions of two windows used in the input scans.
on the complexity of bandwidth allocation in radio networks. we define and study an optimization problem that is motivated by bandwidth allocation in radio networks. because radio transmissions are subject to interference constraints in radio networks, physical space is a common resource that the nodes have to share in such a way, that concurrent transmissions do not interfere. the bandwidth allocation problem we study under these constraints is the following. given bandwidth (traffic) demands between the nodes of the network, the objective is to schedule the radio transmissions in such a way that the traffic demands are satisfied. the problem is similar to a multicommodity flow problem, where the capacity constraints are replaced by the more complex notion of non-interfering transmissions. we provide a formal specification of the problem that we call round weighting. by modeling non-interfering radio transmissions as independent sets, we relate the complexity of round weighting to the complexity of various independent set problems (e.g. maximum weight independent set, vertex coloring, fractional coloring). from this relation, we deduce that in general, round weighting is hard to approximate within n^1^-^@e (n being the size of the radio network). we also provide polynomial (exact or approximation) algorithms e.g. in the following two cases: (a) when the interference constraints are specific (for instance for a network whose vertices belong to the euclidean space), or (b) when the traffic demands are directed towards a unique node in the network (also called gathering, analogous to single commodity flow).
reconstruction of binary matrices under fixed size neighborhood constraints. using a dynamic programming approach, we prove that a large variety of matrix reconstruction problems from two projections can be solved in polynomial time whenever the number of rows (or columns) is fixed. we also prove some complexity results for several problems concerning the reconstruction of a binary matrix when a neighborhood constraint occurs.
reconstruction of convex lattice sets from tomographic projections in quartic time. filling operations are procedures which are used in discrete tomography for the reconstruction of lattice sets having some convexity constraints. many algorithms have been published giving fast implementations of these operations, and the best running time [s. brunetti, a. daurat, a. kuba, fast filling operations used in the reconstruction of convex lattice sets, in: proc. of dgci 2006, in: lecture notes in comp. sci., vol. 4245, 2006, pp. 98-109] is o(n^2logn) time, where n is the size of projections. in this paper we improve this result by providing an implementation of the filling operations in o(n^2). as a consequence, we reduce the time-complexity of the reconstruction algorithms for many classes of lattice sets having some convexity properties. in particular, the reconstruction of convex lattice sets satisfying the conditions of gardner-gritzmann [r.j. gardner, p. gritzmann, discrete tomography: determination of finite sets by x-rays, trans. amer. math. soc. 349 (1997) 2271-2295] can be performed in o(n^4)-time.
large independent sets in general random intersection graphs. we investigate the existence and efficient algorithmic construction of close to optimal independent sets in random models of intersection graphs. in particular, (a) we propose a new model for random intersection graphs (g"n","m","p"->) which includes the model of [m. karonski, e.r. scheinerman, k.b. singer-cohen, on random intersection graphs: the subgraph problem, combinatorics, probability and computing journal 8 (1999), 131-159] (the ''uniform'' random intersection graph models) as an important special case. we also define an interesting variation of the model of random intersection graphs, similar in spirit to random regular graphs. (b) for this model we derive exact formulae for the mean and variance of the number of independent sets of size k (for any k) in the graph. (c) we then propose and analyse three algorithms for the efficient construction of large independent sets in this model. the first two are variations of the greedy technique while the third is a totally new algorithm. our algorithms are analysed for the special case of uniform random intersection graphs. our analyses show that these algorithms succeed in finding close to optimal independent sets for an interesting range of graph parameters.
the supercover of an m-flat is a discrete analytical object. the aim of this paper is to show that the supercover of an m-flat (i.e. a euclidean affine subspace of dimension m) in euclidean n-space is a discrete analytical object. the supercover of a euclidean object f is a discrete object consisting of all the voxels that intersect f. a discrete analytical object is a set of discrete points that is defined by a finite set of inequalities. a method to determine the inequalities defining the supercover of an m-flat is provided.
on image reconstruction algorithms for binary electromagnetic geotomography. in this paper we discuss the selected image reconstruction methods of binary tomography in the context of their application to geophysical imaging. we restrict our considerations to a discrete version of high-frequency electromagnetic geotomography, which we label as binary electromagnetic geotomography (beg). basically, such an imaging technique may be applied to detect subsurface anomalies (air-filled voids) whose attenuation coefficient is very low (nearly zero-value) and considerably different from that for the background. the assumption for a binary representation of the image to be reconstructed substantially relaxes image reconstruction problems related to ill-posedness that comes from an intrinsic limitation of an angular range of projections. we test two algorithms for binary tomography, where the penalty term is based on the markov random field (mrf) model. the mean-field reference distribution and mean-field annealing are applied to estimate the global maximizer of the gibbs-boltzmann distribution associated with the objective function. we also apply the projected gradient algorithm that uses a binary steering. very efficient implementations of the algorithms are also given. the numerical results are presented for noise-free, noisy, and real data.
finding a minimum medial axis of a discrete shape is np-hard. the medial axis is a classical representation of digital objects widely used in many applications. however, such a set of balls may not be optimal: subsets of the medial axis may exist without changing the reversivility of the input shape representation. in this article, we first prove that finding a minimum medial axis is an np-hard problem for the euclidean distance. then, we compare two algorithms which compute an approximation of the minimum medial axis, one of them providing bounded approximation results.
discrete sets with minimal moment of inertia. we analyze the moment of inertia i(s), relative to the center of gravity, of finite plane lattice sets s. we classify these sets according to their roundness: a set s is rounder than a set t if i(s)
high level communication functionalities for wireless sensor networks. in this paper we show how to establish a reliable and efficient high level communication system in a randomly deployed network of sensors equipped with directional antennas. this high level communication system enables the programming of the sensor network using high level communication functionalities without the burden of taking care of their physical capacities (low range, unidirectional links, single frequency, presence of collisions, etc.). the high level communication functionalities we offer include point-to-point communication, point-to-area communication, and one-to-all communication. the basic idea to implement this system is to simulate a virtual network that emerges from the ad-hoc network using self-organization, self-discovery and collaborative methods. we also analyse the efficiency, scalability and robustness of the proposed protocols.
on the polyhedral complexity of the integer points in a hyperball. let b^n be a hyperball in r^n, n>=2, and denote b"z^n=b^n@?z^n. define polyhedral facet complexity of b"z^n as fc(b"z^n)=min"p{f"n"-"1(p)} where p is an enclosing polyhedron for b"z^n (i.e., p"z=p@?z^n=b"z^n) and f"n"-"1(p) is the number of the (n-1)-facets of p. analogously, define polyhedral vertex complexity of b"z^n as vc(b"z^n)=min"p{f"0(p)} where p is an enclosing polyhedron for b"z^n and f"0(p) is the number of the 0-facets (vertices) of p. upper bounds for fc(b"z^n) follow from a well-known bound for the number of facets and vertices of the convex hull of b"z^n [i. barany, d.g. larman, the convex hull of the integer points in a large ball, math. ann. 312 (1998) 167-181]. in this note we provide the first nontrivial lower bounds on fc(b"z^n) and vc(b"z^n).
convex decomposition of u-polygons. when parallel x-rays are considered in any finite set u of directions, switching components with respect to u can be constructed. this is true for u@?r^n, and also for any finite set of lattice directions. r.j. gardner raised the problem of looking for a characterization of switching components. in 2001, l. hajdu and r. tijdeman gave an answer by proving that a switching component is always the linear combination of switching elements. though splendid, this result fails to be a characterization theorem inside the class of convex bodies, meaning that the switching element of the linear combination could be not convex even if the switching component is convex. the purpose of this paper is to investigate the problem in the plane, where a convex switching component with respect to u is a u-polygon. we prove that a u-polygon can always be decomposed as a linear sum inside the class of u-polygons.
the steiner tree problem on graphs: inapproximability results. the steiner tree problem on weighted graphs seeks a minimum weight subtree containing a given subset of the vertices (terminals). we show that it is np-hard to approximate the steiner tree problem within a factor 96/95. our inapproximability results are stated in a parametric way, and explicit hardness factors would be improved automatically by providing gadgets and/or expanders with better parameters.
a 3d fully parallel surface-thinning algorithm. the thinning is an iterative layer by layer erosion until only the ''skeletons'' of the objects are left. this paper presents a thinning algorithm for extracting medial surfaces from 3d binary pictures. the strategy which is used is called fully parallel, which means that the same parallel operator is applied at each iteration. an efficient implementation of the proposed algorithm on conventional sequential computers is given and the topological correctness for (26, 6) binary pictures is proved.
a randomized algorithm for the joining protocol in dynamic distributed networks. we describe a randomized algorithm for assigning neighbours to vertices joining a dynamic distributed network. the aim of the algorithm is to maintain connectivity, low diameter and constant vertex degree. on joining each vertex donates a constant number of tokens to the network. these tokens contain the address of the donor vertex. the tokens make independent random walks in the network. a token can be used by any vertex it is visiting to establish a connection to the donor vertex. this allows joining vertices to be allocated a random set of neighbours although the overall vertex membership of the network is unknown. the network we obtain in this way is robust under adversarial deletion of vertices and edges and actively reconnects itself. one model we consider is a network constructed in this fashion, in which vertices join but never leave. if t is the size of the network, then the diameter of the network is o(logt) for all t, with high probability. as an example of the robustness of this model, suppose an adversary deletes edges from the network leaving components of size at least t^1^/^2^+^@d. with high probability the network reconnects itself by replacing lost edges using tokens from the token pool.
deterministic monotone algorithms for scheduling on related machines. we consider the problem of designing monotone deterministic algorithms for scheduling tasks on related machines in order to minimize the makespan. several recent papers showed that monotonicity is a fundamental property to design truthful mechanisms for this scheduling problem. we give both theoretical and experimental results. first of all we consider the case of two machines when speeds of the machines are restricted to be powers of a given constant c>0. we prove that algorithm largest processing time (lpt) is monotone for any c>=2 while it is not monotone for c@?1.78; algorithm list scheduling (ls), instead, is monotone only for c>2. in the case of m>2 machines we restrict our attention to the class of ''greedy-like'' monotone algorithms defined in [vincenzo auletta, roberto de prisco, paolo penna, giuseppe persiano, deterministic truthful approximation mechanisms for scheduling related machines, in: proceedings of 21st annual symposium on theoretical aspects of computer science. stacs '04, in: lecture notes in computer science, vol. 2996, springer, 2004, pp. 608-619]. it has been shown that greedy-like monotone algorithms can be used to design a family of 2+@e-approximate truthful mechanisms. in particular, in [vincenzo auletta, roberto de prisco, paolo penna, giuseppe persiano, deterministic truthful approximation mechanisms for scheduling related machines, in: proceedings of 21st annual symposium on theoretical aspects of computer science. stacs '04, in: lecture notes in computer science, vol. 2996, springer, 2004, pp. 608-619], the greedy-like algorithm uniform is proposed and it is proved that it is monotone when machine speeds are powers of a given integer constant c>0. in this paper we propose a new algorithm, called uniform_rr, that is still monotone when speeds are powers of a given integer constant c>0 and we prove that its approximation factor is not worse than that of uniform. we also experimentally compare the performance of uniform, uniform_rr, lpt, and several other monotone and greedy-like heuristics.
on the reconstruction of binary and permutation matrices under (binary) tomographic constraints. the paper studies the problem of reconstructing binary matrices constrained by binary tomographic information. we prove new np-hardness results that sharpen previous complexity results in the realm of discrete tomography but also allow applications to related problems for permutation matrices. hence our results can be interpreted in terms of other combinatorial problems including the queens' problem.