Realization and synthesis of reversible functions

Reversible circuits play an important role in quantum computing. This paper studies the realization problem of reversible circuits. For any n-bit reversible function, we present a constructive synthesis algorithm. Given any n-bit reversible function, there are N distinct input patterns different from their corresponding outputs, where N≤2ⁿ, and the other (2ⁿ−N) input patterns will be the same as their outputs. We show that this circuit can be synthesized by at most 2n⋅N ‘(n−1)’-CNOT gates and 4n²⋅N NOT gates. The time and space complexities of the algorithm are Ω(n⋅4ⁿ) and Ω(n⋅2ⁿ), respectively. The computational complexity of our synthesis algorithm is exponentially lower than that of breadth-first search based synthesis algorithms.     

Generalized distances in digital geometry

A generalized distance measure called m-neighbor distance in n-D quantized space is presented. Its properties as a metric are examined. It is shown to give the shortest path length between two points in n-D digital space. An algorithm for finding such a shortest path between two points is presented. It is shown that lower dimension (2-D and 3-D) distance measures presently used in digital geometry can easily be derived as special cases. Other properties of m-neighbor distance are also examined.     

Computation in reversible cellular automata

A reversible cellular automaton (RCA) is a subclass of a CA such that its global function is injective. It is considered as an abstract spatiotemporal model of a reversible physical system. In spite of the strong constraint of reversibility, an RCA has a high ability of information processing. In this survey, we overview the past studies on RCAs, and discuss how computing is performed in them. We can see even very simple RCAs have computation-universality.     

Complementing two-way finite automata

We study the relationship between the sizes of two-way finite automata accepting a language and its complement. In the deterministic case, for a given automaton (2dfa) with n states, we build an automaton accepting the complement with at most 4n states, independently of the size of the input alphabet. Actually, we show a stronger result, by presenting an equivalent 4n-state 2dfa that always halts. For the nondeterministic case, using a variant of inductive counting, we show that the complement of a unary language, accepted by an n-state two-way automaton (2nfa), can be accepted by an O(n⁸)-state 2nfa. Here we also make 2nfa’s halting. This allows the simulation of unary 2nfa’s by probabilistic Las Vegas two-way automata with O(n⁸) states.     

Magic numbers in the state hierarchy of finite automata

A number d is magic for n, if there is no regular language for which an optimal nondeterministic finite state automaton (nfa) uses exactly n states and, at the same time, the optimal deterministic finite state automaton (dfa) uses exactly d states. We show that, in the case of unary regular languages, the state hierarchy of dfa’s, for the family of languages accepted by n-state nfa’s, is not contiguous. There are some “holes” in the hierarchy, i.e., magic numbers in between values that are not magic. This solves, for automata with a single letter input alphabet, an open problem of existence of magic numbers. Actually, most of the numbers is magic in the unary case. As an additional bonus, we also get a new universal lower bound for the conversion of unary d-state dfa’s into equivalent nfa’s: nondeterminism does not reduce the number of states below log² d, not even in the best case.     

Two-way unary automata versus logarithmic space

We show that if L=NL (the classical logarithmic space classes), then each unary 2nfa (a two-way nondeterministic finite automaton) can be converted into an equivalent 2dfa (a deterministic two-way automaton), keeping the number of states polynomial. (Unlike other results of this kind, here the deterministic simulation is valid for inputs of all lengths, not only polynomially long ones.) This shows a connection between the standard logarithmic space complexity and the state complexity of two-way unary automata: it indicates that L could be separated from NL by proving a superpolynomial gap, in the number of states, for the conversion from unary 2nfas to 2dfa. Moreover, without any unproven assumptions, we show that each n-state unary 2nfa can be simulated by an equivalent 2ufa (an unambiguous 2nfa) with a polynomial number of states.     

Adaptive reversible image watermarking scheme

This paper presents an adaptive block sized reversible image watermarking scheme. A reversible watermarking approach recovers the original image from a watermarked image after extracting the embedded watermarks. Without loss of generality, the proposed scheme segments an image of size 2^N × 2^N adaptively to blocks of size 2^L × 2^L, where L starts from a user-defined number to 1, according to their block structures. If possible, the differences between central ordered pixel and other pixels in each block are enlarged to embed watermarks. The embedded quantity is determined by the largest difference in a block and watermarks are embedded into LSB bits of above differences. Experimental results show that the proposed adaptive block size scheme has higher capacity than conventional fixed block sized method.     

New Results on Path Approximation

In this paper we give bounds on the complexity of some algorithms for approximating 2-D and 3-D polygonal paths with the infinite beam measure of error. While the time/space complexities of the algorithms known for other error measures are well understood, path approximation with infinite beam measure seems to be harder due to the complexity of some geometric structures that arise in the known approaches. Our results answer some open problems left in previous work. We also present a more careful analysis of the time complexity of the general iterative algorithm for infinite beam measure and show that it could perform much better in practice than in the worst case. We then propose a new approach for path approximation that consists of a breadth first traversal of the path approximation graph, without constructing the graph. This approach can be applied to any error criterion in any constant dimension. The running time of the new algorithm depends on the size of the output: if the optimal approximating path has m vertices, the algorithm performs F(m) iterations rather than n–1 in the previous approaches, where F(m) \le n–1 is the number of vertices of the path approximation graph that can be reached with at most m–2 edges. This is the first output sensitive path approximation algorithm.     

FPGA implementation of reversible watermarking in digital images using reversible contrast mapping

Reversible contrast mapping (RCM) and its various modified versions are used extensively in reversible watermarking (RW) to embed secret information into the digital contents. RCM based RW accomplishes a simple integer transform applied on pair of pixels and their least significant bits (LSB) are used for data embedding. It is perfectly invertible even if the LSBs of the transformed pixels are lost during data embedding. RCM offers high embedding rate at relatively low visual distortion (embedding distortion). Moreover, low computation cost and ease of hardware realization make it attractive for real-time implementation. To this aim, this paper proposes a field programmable gate array (FPGA) based very large scale integration (VLSI) architecture of RCM-RW algorithm for digital images that can serve the purpose of media authentication in real-time environment. Two architectures, one for block size (8 × 8) and the other one for (32 × 32) block are developed. The proposed architecture allows a 6-stage pipelining technique to speed up the circuit operation. For a cover image of block size (32 × 32), the proposed architecture requires 9881 slices, 9347 slice flip-flops, 11291 number 4-input LUTs, 3 BRAMs and a data rate of 1.0395 Mbps at an operating frequency as high as 98.76 MHz.     

State-complexity of finite-state devices,state compressibility and incompressibility

We study how the number of states may change when we convert between different finite-state devices. The devices that we consider are finite automata that are one-way or two-way, deterministic or nondeterministic or alternating. We obtain several new simulation results (e.g., ann-state 2NFA can be simulated by a 1NFA with 8 ⁿ + 2 states, and by a 1AFA with n ² states), and state-incompressibility results (e.g., in order to simulate ann-state 2DFA, a 1NFA needs /2 ^n–2 states, and a 2AFA needs cn states for some constant c, in general).     

Time-space trade-offs for compressed suffix arrays

Given a binary string of length n, we give a representation of its suffix array that takes O(nt(lgn)^1/t) bits of space such that given i,1?i?n, the ith entry in the suffix array of the string can be retrieved in O(t) time, for any parameter 1?t?lglgn. For t=lglgn, this gives a compressed suffix array representation of Grossi and Vitter [Proc. Symp. on Theory Comput., 2000, pp. 397-406]. For t=O(1/ε), this gives the best known (in terms of space) compressed suffix array representation with constant query time. From this representation one can construct a suffix tree structure for a text of length n, that uses o(nlgn) bits of space which can be used to find all the k occurrences of a given pattern of length m in O(m/lgn+k) time. No such structure was known earlier.     

A non-linear response history model for the seismic analysis of high-rise framed buildings

A materially non-linear plane-frame model is presented that is capable of analysing high-rise buildings subjected to earthquake forces. The model represents each storey of the building by an assembly of vertical and horizontal beam elements The model introduces yield hinges with ideal plastic properties in a regular plane frame. The displacements are described by the translation (sway) of each floor and the rotation of all beam–column intersections. The mass is only associated with the translations, and thus the analysis can be carried out as a static condensation of the rotations, combined with integration of the dynamic equations for the translations. The dynamic integration is here carried out by use of the Runge–Kutta scheme. This approach allows a building to be modelled by m(n + 2) degrees of freedom (where m is the number of storeys and n is the number of bays). The rank of the condensed stiffness matrix is only m. Its construction, which requires the inversion of the rotational, rank m(n + 1), stiffness matrix, is required only at time-steps where the pattern of yielding has altered from the previous time-step. This model is particularly attractive for non-linear response history analysis of high-rise buildings as it is efficient, allows each storey to have multiple redundancies, and each connection to be modelled with any suitable moment–rotation relationship.Three verification examples are presented and the results from static push-over analysis are compared with time–history results from the simplified model. The results verify that the model is capable of performing non-linear response history analysis on regular high rise buildings.     

A Dijkstra-like method computing all extreme supported non-dominated solutions of the biobjective shortest path problem

We address the problem of determining all extreme supported solutions of the biobjective shortest path problem. A novel Dijkstra-like method generalizing Dijkstra׳s algorithm to this biobjective case is proposed. The algorithm runs in O(N(m+n log n)) time to solve one-to-one and one-to-all biobjective shortest path problems determining all extreme supported non-dominated points in the outcome space and one supported efficient path associated with each one of them. Here n is the number of nodes, m is the number of arcs and N is the number of extreme supported points in outcome space for the one-to-all biobjective shortest path problem. The memory space required by the algorithm is O(n+m) for the one-to-one problem and O(N+m) for the one-to-all problem. A computational experiment comparing the performance of the proposed methods and state-of-the-art methods is included.     

Virtual screening of novel reversible inhibitors for marine alkaline protease MP

Marine alkaline protease (MP,² accession no. ACY25898) is produced by a marine bacterium strain isolated from Yellow Sea sediment in China. Previous research has shown that this protease is a cold-adapted enzyme with antioxidant activity that could be used as a detergent additive. Owing to its instability in the liquid state, MP's application in liquid detergents was limited. Therefore, the discovery of reversible MP inhibitors to stabilize the protease was imperative. Here, we used the X-ray structure of MP and recompiled AutoDock 4.2 with refined Zn²⁺ characters to screen the free chemical database ZINC. After completing the docking procedure, we applied strategies including the “initial filter”, consensus scoring and pharmocophore model to accelerate the process and improve the virtual screening success rate. The “initial filter” was built based on the docking results of boronic acid derivatives validated as reversible inhibitors of MP by our previous studies. Finally, ten compounds were purchased or synthetized to test their binding affinity for MP. Three of the compounds could reversibly inhibit MP with apparent K_i values of 0.8–1.2 mmol. These active compounds and their binding modes provide useful information for understanding the molecular mechanism of reversible MP inhibition. The results may also serve as the foundation for further screening and design of reversible MP inhibitors.     

Fast Constructive Recognition of a Black Box Group Isomorphic toSnorAnusing Goldbach’s Conjecture

The well-known Goldbach Conjecture (GC) states that any sufficiently large even number can be represented as a sum of two odd primes. Although not yet demonstrated, it has been checked for integers up to 10¹⁴. Using two stronger versions of the conjecture, we offer a simple and fast method for recognition of a gray box group G known to be isomorphic to S_n(or A_n) with knownn ≥  20, i.e. for construction1of an isomorphism from G toS_n (or A_n). Correctness and rigorous worst case complexity estimates rely heavily on the conjectures, and yield times of O([ρ + ν + μ ] n log²n) or O([ ρ + ν + μ ] n logn / loglog n) depending on which of the stronger versions of the GC is assumed to hold. Here,ρ is the complexity of generating a uniform random element of G, ν is the complexity of finding the order of a group element in G, and μ is the time necessary for group multiplication in G. Rigorous lower bound and probabilistic approach to the time complexity of the algorithm are discussed in the Appendix.     

Energy-efficient topology control algorithm for maximizing network lifetime in wireless sensor networks with mobile sink

Uneven energy consumption is an inherent problem in wireless sensor networks characterized by multi-hop routing and many-to-one traffic pattern. Such unbalanced energy dissipation can significantly reduce network lifetime. In this paper, we study the problem of prolonging network lifetime in large-scale wireless sensor networks where a mobile sink gathers data periodically along the predefined path and each sensor node uploads its data to the mobile sink over a multi-hop communication path. By using greedy policy and dynamic programming, we propose a heuristic topology control algorithm with time complexity O(n(m + n log n)), where n and m are the number of nodes and edges in the network, respectively, and further discuss how to refine our algorithm to satisfy practical requirements such as distributed computing and transmission timeliness. Theoretical analysis and experimental results show that our algorithm is superior to several earlier algorithms for extending network lifetime.     

Finding extreme supported solutions of biobjective network flow problems: An enhanced parametric programming approach

We address the problem of determining a complete set of extreme supported efficient solutions of biobjective minimum cost flow (BMCF) problems. A novel method improving the classical parametric method for this biobjective problem is proposed. The algorithm runs in O(Nn(m + nlogn)) time determining all extreme supported non-dominated points in the outcome space and one extreme supported efficient solution associated with each one of them. Here n is the number of nodes, m is the number of arcs and N is the number of extreme supported non-dominated points in outcome space for the BMCF problem. The memory space required by the algorithm is O(n + m) when the extreme supported efficient solutions are not required to be stored in RAM. Otherwise, the algorithm requires O(N + m) space. Extensive computational experiments comparing the performance of the proposed method and a standard parametric network simplex method are presented.     

Diameter variability of cycles and tori

The diameter of a graph is an important factor for communication as it determines the maximum communication delay between any pair of processors in a network. Graham and Harary [N. Graham, F. Harary, Changing and unchanging the diameter of a hypercube, Discrete Applied Mathematics 37/38 (1992) 265-274] studied how the diameter of hypercubes can be affected by increasing and decreasing edges. They concerned whether the diameter is changed or remains unchanged when the edges are increased or decreased. In this paper, we modify three measures proposed in Graham and Harary (1992) to include the extent of the change of the diameter. Let D^-k(G) is the least number of edges whose addition to G decreases the diameter by (at least) k, D⁺⁰(G) is the maximum number of edges whose deletion from G does not change the diameter, and D^+k(G) is the least number of edges whose deletion from G increases the diameter by (at least) k. In this paper, we find the values of D^-k(C_m), D^-1(T_m,n), D^-2(T_m,n), D⁺¹(T_m,n), and a lower bound for D⁺⁰(T_m,n) where C_m be a cycle with m vertices, T_m,n be a torus of size m by n.     

Petri net based decision system modeling in real-time scheduling and control of flexible automotive manufacturing systems

This paper presents the design and the implementation of a Petri net (PN) model for the control of a flexible manufacturing system (FMS). A flexible automotive manufacturing system used in this environment enables quick cell configuration, and the efficient operation of cells. In this paper, we attempt to propose a flexible automotive manufacturing approach for modeling and analysis of shop floor scheduling problem of FMSs using high-level PNs. Since PNs have emerged as the principal performance modeling tools for FMS, this paper provides an object-oriented Petri nets (OOPNs) approach to performance modeling and to implement efficient production control. In this study, we modeled the system as a timed marked graph (TMG), a well-known subclass of PNs, and we showed that the problem of performance evaluation can be reduced to a simple linear programming (LP) problem with m − n + 1 variables and n constraints, where m and n represent the number of places and transitions in the marked graph, respectively. The presented PN based method is illustrated by modeling a real-time scheduling and control for flexible automotive manufacturing system (FAMS) in Valeo Turkey.