Drag and lift coefficients of inclined finite circular cylinders at moderate Reynolds numbers

The flow around two-dimensional cylinders at moderate Reynolds numbers has been much studied, both for cylinders perpendicular to the flow and for cylinders yawed to the flow. In contrast, yawed finite aspect ratio cylinders have received little attention. In this article we describe computer simulations of cylinders with aspect ratios 2  L/D  20 yawed at angles 0°  α  90° relative to a free stream. The simulations were carried out for Reynolds numbers in the range 1  Re  40. The simulations show that the Independence Principle [Zdravkovich MM. Flow around circular cylinders, vol. 2: applications. New York: Oxford University Press; 2003[1]] is not accurate for α  45°. We have also found that for all aspect ratios, the ratio of the lift to drag force reaches a maximum for 40° < α < 50°. Finally, we present C_L and C_D relationships as best curve fits to computational data.     

Intervals of solutions of the discrete-time algebraic Riccati equation

If two solutions YZ of the DARE are given then the set of solutions X with YXZ can be parametrized by invariant subspaces of the closed loop matrix corresponding to Y. The paper extends the geometric theory of Willems from the continuous-time to the discrete-time ARE making the weakest possible assumptions.     

A note on path bipancyclicity of hypercubes

In [C.H. Tsai, S.Y. Jiang, Path bipancyclicity of hypercubes, Inform. Process. Lett. 101 (2007) 93–97], the authors showed that any path in an n-cube with length of k, 2k2n−4, lies on a cycle of every even length from 2k to 2ⁿ inclusive. Base on Lemma 5 of that paper, they proved the subcase 2.2.1 of the main theorem of that paper. However, the lemma is false, therefore, we propose a lemma to replace that lemma. Therefore, the main result of [C.H. Tsai, S.Y. Jiang, Path bipancyclicity of hypercubes, Inform. Process. Lett. 101 (2007) 93–97] is still correct.     

Inductive Synthesis of Recursive Processes from Logical Properties

This paper proposes an inductive synthesis algorithm for a recursive process. To synthesize a process, facts, which must be satisfied by the target process, are given to the algorithm one by one since such facts are infinitely many in general. When n facts are input to the algorithm, it outputs a process which satisfies the given n facts. And this generating process is repeated infinitely many times. To represent facts of a process, we adopt a subcalculus of μ-calculus. First, we introduce a new preorder _d on recursive processes based on the subcalculus to discuss its properties. p_d q means that pf implies qf, for all formulae f in the subcalculus. Then, its discriminative power and relationship with other preorders are also discussed. Finally, we present the synthesis algorithm. The correctness of the algorithm can be stated that the output sequence of processes by the algorithm converges to a process, which cannot be distinguished from the intended one (if we could know it) by a given enumeration of facts, in the limit. A prototype system based on the algorithm is stated as well.     

To be fair or efficient or a bit of both

Introducing a new concept of (α,β)-fairness, which allows for a bounded fairness compromise, so that a source is allocated a rate neither less than 0α1, nor more than β1, times its fair share, this paper provides a framework to optimize efficiency (utilization, throughput or revenue) subject to fairness constraints in a general telecommunications network for an arbitrary fairness criterion and cost functions. We formulate a non-linear program (NLP) that finds the optimal bandwidth allocation by maximizing efficiency subject to (α,β)-fairness constraints. This leads to what we call an efficiency–fairness function, which shows the benefit in efficiency as a function of the extent to which fairness is compromised. To solve the NLP we use two algorithms. The first is a well-known branch-and-bound-based algorithm called Lipschitz Global Optimization and the second is a recently developed algorithm called Algorithm for Global Optimization Problems (AGOP).We demonstrate the applicability of the framework to a range of examples from sharing a single link to efficiency fairness issues associated with serving customers in remote communities.     

Digital circles with non-lattice point centers

Digitization of a real circle is defined as the set of closest pixels (integer lattice points) to the circle. These pixels form a digital circle. First, this paper defines the term closest pixels and provides an algorithm to digitize an arbitrary circle, i.e., one whose radius is not necessarily an integer, and whose center is not necessarily a lattice point. This digitizing algorithm is simplified to the case of integer radius and integer-coordinate center so that it can be compared to two well-known algorithms: the Bresenham algorithm and an algorithm using the Digital Differential Analyzer (DDA) technique. As a result, the new algorithm consumes only 77% and 40% of the time required for Bresenham and DDA algorithms, respectively. Second, we investigate the problem of finding, for a given digital circle and center, the set of possible real radii that generate that digital circle. For some integerr, we look at all digital circles centered at the origin with real radius in the interval [r–0.5,r+0.5) and determine the paritions of this interval into sub-intervals of real radii generating the same digital circles. Third, we study fixing the digital circle and radius, and finding the set of possible centers. For some pixel (x _c,y _c), we find the partitions of the unit square [x _c –0.5,x _c +0.5)×[y _c –0.5,y _c +0.5) such that for each partition each center in that partition generates the same digital circle. The partition boundaries can be constructed by compass and ruler. Finally, the paper uses these results to determine whether or not a given finite set of pixels is a digital circle segment and if so, shows how to construct its region of possible centers by ruler and compass. We also present an algorithm to detect whether a closed digital are is a digital circle.     

The SAT-based Approach to Separation Logic

The SAT-based approach to the decision problem for expressive, decidable, quantifier-free first-order theories has been investigated with remarkable results at least since 1993. One such theory, successfully employed in the formal verification of complex, infinite state systems, is Separation Logic (SL), which combines Boolean logic with arithmetic constraints of the form x − y ⋈ c, where ⋈ is ≤, <, >, ≥, =, or ≠. The SAT-based approach to SL was first proposed and implemented in 1999: the results in terms of performance were good, and since then a number of other systems for SL have appeared. In this paper we focus on the problem of building efficient SAT-based decision procedures for SL. We present the basic procedure and four optimizations that improve dramatically its effectiveness in most cases: (a) IS ₂ preprocessing, (b) early pruning, (c) model reduction, and (d) best reason detection. For each technique we give an example of how it might improve the performance. Furthermore, for the first three techniques, we give a pseudo-code representation and formally state the soundness and completeness of the resulting optimized procedure. We also show how it is possible to check the satisfiability of valuations involving constraints of the form x − y < c using the Bellman–Ford algorithm. Lastly, we present an extensive comparative experimental analysis, showing that our solver TSAT++, built along the lines described in this paper, is currently the state of the art on various classes of problems, including randomly generated, hand-made, and real-world instances.     

Finite gain stabilization requires analog control

A causal feedback map, taking sequences of measurements and producing sequences of controls, is denoted as finite set if, within any finite time horizon, its range is in a finite set. Bit-rate constrained or digital control are particular cases of finite-set feedback. In this paper, we show that the finite gain (FG) l_p stabilization, with 1p∞, of a discrete-time, linear and time-invariant unstable plant is impossible by finite-set feedback. In addition, we show that, under finite-set feedback, weaker (local) versions of FG l_p stability are also impossible. These facts are not obvious, since recent results have shown that input to state stabilization is viable by bit-rate constrained control. In view of such existing work, this paper leads to two conclusions: (1) even when input to state stability is attainable by finite-set feedback, small changes in the amplitude of the external excitation may cause, in relative terms, a large increase in the amplitude of the state (2) FG l_p stabilization requires logarithmic precision around zero. Since our conclusions hold with no assumption on the feedback structure, they cannot be derived from existing results. We adopt an information theoretic viewpoint, which also brings new insights into the problem of stabilization.     

Long paths in hypercubes with a quadratic number of faults

A path between distinct vertices u and v of the n-dimensional hypercube Q_n avoiding a given set of f faulty vertices is called long if its length is at least 2ⁿ-2f-2. We present a function (n)=Θ(n²) such that if f(n) then there is a long fault-free path between every pair of distinct vertices of the largest fault-free block of Q_n. Moreover, the bound provided by (n) is asymptotically optimal. Furthermore, we show that assuming f(n), the existence of a long fault-free path between an arbitrary pair of vertices may be verified in polynomial time with respect to n and, if the path exists, its construction performed in linear time with respect to its length.     

VCPSS: A two-in-one two-decoding-options image sharing method combining visual cryptography (VC) and polynomial-style sharing (PSS) approaches

This paper presents a novel method to combine two major branches of image sharing: VC and PSS. n transparencies are created for a given gray-valued secret image. If the decoding computer is temporarily not available at (or, not connected to) the decoding scene, we can still physically stack any t received transparencies (tn is a threshold value) to get a vague black-and-white view of the secret image immediately. On the other hand, when the decoding computer is finally available, then we can get a much finer gray-valued view of the secret image using the information hidden in the transparencies. In summary, each transparency is a two-in-one carrier of the information, and the decoding has two options.     

A sufficient condition for pancyclic graphs

In 2005, Rahman and Kaykobad proved that if G is a connected graph of order n such that d(x)+d(y)+d(x,y)n+1 for each pair x, y of distinct nonadjacent vertices in G, where d(x,y) is the length of a shortest path between x and y in G, then G has a Hamiltonian path [Inform. Process. Lett. 94 (2005) 37–41]. In 2006 Li proved that if G is a 2-connected graph of order n3 such that d(x)+d(y)+d(x,y)n+2 for each pair x,y of nonadjacent vertices in G, then G is pancyclic or G=K_n/2,n/2 where n4 is an even integer [Inform. Process. Lett. 98 (2006) 159–161]. In this work we prove that if G is a 2-connected graph of order n such that d(x)+d(y)+d(x,y)n+1 for all pairs x, y of distinct nonadjacent vertices in G, then G is pancyclic or G belongs to one of four specified families of graphs.     

A discrete-time dynamic K-winners-take-all neural circuit

A discrete-time mathematical model of K-winners-take-all (KWTA) neural circuit that can quickly identify the K-winning from N neurons, where 1K<N, whose input signals are larger than that of remaining N−K neurons, is given and analyzed. A functional block scheme of the circuit is presented. For N competitors, such circuit is composed of N feedforward and one feedback hard-limiting neurons that are used to determine the dynamic shift of input signals. The circuit has low computational and hardware implementation complexity, high speed of signal processing, can process signals of any finite range, possesses signal order preserving property and does not require resetting and corresponding supervisory circuit that additionally increases a speed of signal processing.     

-Admissible control elements for diagonal semigroups on -spaces

For linear systems described by , where A is a diagonal operator on the state space l^r for some 1r<∞ and bl^r, we develop necessary and sufficient conditions for b to be p-admissible. This extends results by Ho, Russell and Weiss to the case r≠2.     

Fully Scalable Fault-Tolerant Simulations for BSP and CGM

In this paper we consider general simulations of algorithms designed for fully operational BSP and CGM machines on machines with faulty processors. The BSP (or CGM) machine is a parallel multicomputer consisting of p processors for which a memory of n words is evenly distributed and each processor can send and receive at most h messages in a superstep. The faults are deterministic (i.e., worst-case distributions of faults are considered) and static (i.e., they do not change in the course of computation). We assume that a constant fraction of processors are faulty.  We present two fault-tolerant simulation techniques for BSP and CGM:  1. A deterministic simulation that achieves O(1) slowdown for local computations and O((log_h p)²) slowdown for communications per superstep, provided that a preprocessing is done that requires O((log_h p)²) supersteps and linear (in h) computation per processor in each superstep.  2. A randomized simulation that achieves O(1) slowdown for local computations and O(log_h p) slowdown for communications per superstep with high probability, after the same (deterministic) preprocessing as above.  Our results are fully scalable over all values of p from Θ(1) to Θ(n). Furthermore, our results imply that if pn for 0<<1 and h=Θ((n/p)^δ) for 0<δ1 (which hold in almost all practical BSP and CGM computations), algorithms can be made resilient to a constant fraction of processor faults without any asymptotic slowdown.     

Fast periodic graph exploration with constant memory

We consider the problem of periodic exploration of all nodes in undirected graphs by using a finite state automaton called later a robot. The robot, using a constant number of states (memory bits), must be able to explore any unknown anonymous graph. The nodes in the graph are neither labelled nor coloured. However, while visiting a node v the robot can distinguish between edges incident to it. The edges are ordered and labelled by consecutive integers 1,…,d(v) called port numbers, where d(v) is the degree of v. Periodic graph exploration requires that the automaton has to visit every node infinitely many times in a periodic manner. In this paper, we are interested in minimisation of the length of the exploration period. In other words, we want to minimise the maximum number of edge traversals performed by the robot between two consecutive visits of a generic node, in the same state and entering the node by the same port. Note that the problem is unsolvable if the local port numbers are set arbitrarily, see [L. Budach, Automata and labyrinths, Math. Nachr. 86 (1978) 195–282]. In this context, we are looking for the minimum function π(n), such that, there exists an efficient deterministic algorithm for setting the local port numbers allowing the robot to explore all graphs of size n along a traversal route with the period π(n). Dobrev et al. proved in [S. Dobrev, J. Jansson, K. Sadakane, W.-K. Sung, Finding short right-hand-on-the-wall walks in graphs, in: Proc. 12th Colloquium on Structural Information and Communication Complexity, SIROCCO 2005, in: Lecture Notes in Comput. Sci., vol. 3499, Springer, Berlin, 2005, pp. 127–139] that for oblivious robots π(n)10n. Recently Ilcinkas proposed another port labelling algorithm for robots equipped with two extra memory bits, see [D. Ilcinkas, Setting port numbers for fast graph exploration, in: Proc. 13th Colloquium on Structural Information and Communication Complexity, SIROCCO 2006, in: Lecture Notes in Comput. Sci., vol. 4056, Springer, Berlin, 2006, pp. 59–69], where the exploration period π(n)4n−2. In the same paper, it is conjectured that the bound 4n−O(1) is tight even if the use of larger memory is allowed. In this paper, we disprove this conjecture presenting an efficient deterministic algorithm arranging the port numbers, such that, the robot equipped with a constant number of bits is able to complete the traversal period in π(n)<3.75n−2 steps hence decreasing the existing upper bound. This reduces the gap with the lower bound of π(n)2n−2 holding for any robot.     

Sentences over Integral Domains and Their Computational Complexities

LetRbe a Hilbertian domain and letKbe its fraction field. Letψ(x₁, …, x_n, y) be a quantifier free arithmetical formula overR. We may also takeψ(x₁, …, x_n, y) to be an arithmetical formula overK[x₁, …, x_n] and write it asψ(y). In this paper we show that ifRhas enough non-units and x₁…x_n y ψ(x₁, …, x_n, y), called an ⁿ  sentence, is true inR, then y ψ(y) is true inK[x₁, …, x_n]. Also, ifR=K[T], whereKis an infinite integral domain andx₁…x_n y ψ(x₁, …, x_n, y)is true inR, then y ψ(y) is true inR[x₁, …, x_n]. These results are applied to find the upper and lower bounds of the time complexities of various decision problems on diophantine equations with parameters and arithmetical sentences. Some of the results are: 1. The decision problem of sentences and diophantine equations with parameters over the ring of integers of a global field are co-NP-complete. 2. The decision problem of sentences over the ring of integers of a global field is NP-complete. 3. LetKbe an infinite domain, the time complexities of the decision problems of equations with parameters and sentences over the polynomial ringK[t] are polynomial time reducible to factoring polynomials overK. 4. The decision problem of sentences over all algebraic integer rings is in P. 5. The decision problem of sentences over all integral domains with characteristic 0 is in P. 6. The time complexity of the decision problem of sentences over all integral domains is polynomial time reducible to factoring integers overZand factoring polynomials over finite fields.     

A necessary condition for quantitative exponential stability of linear state-space systems

For an arbitrary n×n constant matrix A the two following facts are well known:

• (1/n)Re(traceA)−max_j=1,…,nRe λ_j(A)0;

• If U is a unitary matrix, one can always find a skew-Hermitian matrix A so that U=e^A.

In this note we present the extension of these two facts to the context of linear time-varying dynamical systemsAs a by-product, this result suggests that, the notion of “slowly varying state-space systems”, commonly used in literature, is mathematically not natural to the problem of exponential stability.     

Range Estimation Is NP-Hard for ε2 Accuracy and Feasible for ε2−δ

The basic problem of interval computations is: given a function f(x ₁,..., x _n) and n intervals [x _i, x _i], find the (interval) range yof the given function on the given intervals. It is known that even for quadratic polynomials f(x ₁,..., x _n), this problem is NP-hard. In this paper, following the advice of A. Neumaier, we analyze the complexity of asymptotic range estimation, when the bound on the width of the input intervals tends to 0. We show that for small c > 0, if we want to compute the range with an accuracy c ₂, then the problem is still NP-hard; on the other hand, for every > 0, there exists a feasible algorithm which asymptotically, estimates the range with an accuracy c ^2–.     

On the oriented chromatic number of Halin graphs

An oriented k-coloring of an oriented graph G is a mapping such that (i) if xy∈E(G) then c(x)≠c(y) and (ii) if xy,zt∈E(G) then c(x)=c(t)⇒c(y)≠c(z). The oriented chromatic number of an oriented graph G is defined as the smallest k such that G admits an oriented k-coloring. We prove in this paper that every Halin graph has oriented chromatic number at most 9, improving a previous bound proposed by Vignal.