Search

Abstract: Being motivated by John Tantalo’s Planarity Game, we consider straight line plane drawings of a planar graph with edge crossings and wonder how obfuscated such drawings can be. We define , the obfuscation complexity of , to be the maximum number of edge crossings in a drawing of . Relating to the distribution of vertex degrees in , we show an efficient way of constructing a drawing of with at least edge crossings. We prove bounds for an -vertex planar graph with minimum vertex degree . The shift complexity of , denoted by , is the minimum number of vertex shifts sufficient to eliminate all edge crossings in an arbitrarily obfuscated drawing of (after shifting a vertex, all incident edges are supposed to be redrawn correspondingly). If , then is linear in the number of vertices due to the known fact that the matching number of is linear. However, in the case we notice that can be linear even if the matching number is bounded. As for computational complexity, we show that, given a drawing of a planar graph, it is NP-hard to find an optimum sequence of shifts making crossing-free. [Copyright &y& Elsevier]

This paper considers when one can invert general recursive operators which map a class of functions to . In this regard, we study four different notions of inversion. We additionally consider enumeration of operators which cover all general recursive operators which map to in the sense that, for every general recursive operator mapping to , there is a general recursive operator in the enumerated sequence which behaves the same way as on . Three different possible types of enumeration are studied. [Copyright &y& Elsevier]

Abstract: Higher dimensional automata (HDA) represent a promising tool for modelling (“true”) concurrency in a both combinatorial and topological framework. Within these models, fast algorithms investigating deadlocks and unreachable regions have been devised previously on a background of easily understandable “directed” geometric ideas. In this article, we modify notions and methods from homotopy theory to define and investigate “essentially different” schedules in a HDA and to detect whether two given runs are essentially different using an algorithm again based on “directed geometry”. [Copyright &y& Elsevier]

Abstract: We present an analog and machine-independent algebraic characterization of elementarily computable functions over the real numbers in the sense of recursive analysis: we prove that they correspond to the smallest class of functions that contains some basic functions, and closed by composition, linear integration, and a simple limit schema. We generalize this result to all higher levels of the Grzegorczyk Hierarchy. This paper improves several previous partial characterizations and has a dual interest: [ ] Concerning recursive analysis, our results provide machine-independent characterizations of natural classes of computable functions over the real numbers, allowing to define these classes without usual considerations on higher-order (type 2) Turing machines. [ ] Concerning analog models, our results provide a characterization of the power of a natural class of analog models over the real numbers and provide new insights for understanding the relations between several analog computational models. [Copyright &y& Elsevier]

Abstract: This paper proves the decidability of several problems in the theory of HD , and PD systems, some of which that have been proved before but are now proved in a different way. First, the paper tackles the decidability of the nilpotency of HD systems and the infinitude of PD languages. Then, we prove the decidability of the problem of momentary stagnation of the growth function of PD systems. Finally, we suggest a way to solve the decidability of the momentary stagnation of the growth function of systems, proving the decidability of the infinitude of HD as a trivial consequence. [Copyright &y& Elsevier]

We introduce Concurrent Timed Automata (CTAs) where automata running in parallel are synchronized. We consider the subclasses of CTAs obtained by admitting, or not, diagonal clock constraints and constant updates, and by letting, or not, sequential automata to update the same clocks. We prove that such subclasses recognize the same languages but differ w.r.t. the succinctness of the models. Moreover, we distinguish between subclasses that are polynomially closed w.r.t. finite union and finite intersection, and subclasses that do not have such properties. [Copyright &y& Elsevier]