Computer Science – Theory and Applications

In cryptography we typically prove the security of a scheme by reducing the task of breaking the scheme to some hard computational problem. This reduction usually done in a

black-box

fashion. By this we mean that there is an algorithm that can solve the hard problem given any black-box for breaking the scheme.

This lecture concerns exceptions to this rule: that is, schemes that are proven secure using a non-black-box reduction, that actually uses the code of a scheme-breaking attacker to construct a problem-solving algorithm. It turns out that such reductions can be used to obtain schemes with better properties that were known before. In fact, in some cases these non-black-box reductions can be obtain goals that were proven to be impossible to achieve when restricting to black-box reductions. In particular, we will present constructions of zero-knowledge protocols that are proven secure under various compositions [1, 2, 3] .

We’ll also discuss some of the limitations and open questions regarding non-black-box security proofs.

We prove the

$(3 + \frac{(q - 1)^{2}} {q^{5} + (q - 1)^{3}})n - o(n)$

lower bound on the quadratic complexity of multiplication of two degree-

n

polynomials over a

q

-element field. The proof is based on a novel combination of two known techniques. One technique is the analysis of Hankel matrices representing bilinear forms defined by linear combinations of the coefficients of the polynomial product. The other technique is a counting argument from the coding theory.

Synchronous elastic circuits (also known as latency-insensitive and latency-tolerant) behave independently of the latencies of computations and communication channels.

In this paper we classify several group-theoretic computational problems into the classes PZK and SZK (problems with perfect/statistical zero-knowledge proofs respectively). Prior to this, these problems were known to be in AM ∩ coAM. As PZK ⊆ SZK ⊆ AM ∩ coAM, we have a tighter upper bound for these problems.

We consider decompositions of factorial languages to concatenations of factorial languages and prove that if the factorial language is regular, then so are the factors of its

canonical

decomposition.

Bidirected graphs

(a sort of nonstandard graphs introduced by Edmonds and Johnson) provide a natural generalization to the notions of directed and undirected graphs. By a

weakly acyclic

bidirected graph we mean such a graph having no simple cycles. We call a bidirected graph

strongly acyclic

if it has no cycles (even non-simple). We present (generalizing results of Gabow, Kaplan, and Tarjan) a modification of the depth-first search algorithm that checks (in linear time) if a given bidirected graph is weakly acyclic (in case of negative answer a simple cycle is constructed). We use the notion of

skew-symmetric graphs

(the latter give another, somewhat more convenient graph language which is essentially equivalent to the language of bidirected graphs). We also give structural results for the class of weakly acyclic bidirected and skew-symmetric graphs explaining how one can construct any such graph starting from strongly acyclic instances and, vice versa, how one can decompose a weakly acyclic graph into strongly acyclic “parts”. Finally, we extend acyclicity test to build (in linear time) such a decomposition.

Parametric inductive types can be seen as functions taking type parameters as arguments and returning the instantiated inductive types. Given functions between parameters one can construct a function between the instantiated inductive types representing the change of parameters along these functions. It is well known that it is not a functor w.r.t. intensional equality based on standard reductions. We investigate a simple type system with inductive types and iteration and show by modular rewriting techniques that new reductions can be safely added to make this construction a functor, while the decidability of the internal conversion relation based on the strong normalization and confluence properties is preserved. Possible applications: new categorical and computational structures on

λ

-calculus, certified computation.

Zielonka’s theorem shows that each regular set of Mazurkiewicz traces can be implemented as a system of synchronized processes provided with some distributed control structure called an asynchronous automaton. This paper gives a new algorithm for the synthesis of a non-deterministic asynchronous automaton from a regular Mazurkiewicz trace language. Our approach is based on an unfolding procedure that improves the complexity of Zielonka’s and Pighizzini’s techniques: Our construction is polynomial in terms of the number of states but still double-exponential in the size of the alphabet. As opposed to Métivier’s work, our algorithm does not restrict to acyclic dependence alphabets.

We show that two equivalent

$\mathbb{K}$

-automata are conjugate to a third one, when

$\mathbb{K}$

is equal to

$\mathbb{B, N, Z}$

, or any (skew) field and that the same holds true for functional tranducers as well.

The Steiner tree problem in unweighted graphs requires to find a minimum size connected subgraph containing a given subset of nodes (terminals). In this paper we investigate applications of the linear matroid parity algorithm to the Steiner tree problem for two classes of graphs: where the terminals form a vertex cover and where terminals form a dominating set. As all these problems are MAX-SNP-hard, the issue is what approximation can be obtained in polynomial time. The previously best approximation ratio for the first class of graphs (also known as unweighted quasi-bipartite graphs) is ≈ 1.217 (Gröpl et al. [4]) is reduced in this paper to 8/7–1/160≈ 1.137. For the case of graphs where terminals form a dominating set, an approximation ratio of 4/3 is achieved.

Disjoint

NP

-pairs are a well studied complexity theoretic concept with important applications in cryptography and propositional proof complexity. In this paper we introduce a natural generalization of the notion of disjoint

NP

-pairs to disjoint

k

-tuples of

NP

-sets for

k

≥ 2. We define subclasses of the class of all disjoint

k

-tuples of

NP

-sets. These subclasses are associated with a propositional proof system and possess complete tuples which are defined from the proof system.

In our main result we show that complete disjoint

NP

-pairs exist if and only if complete disjoint

k

-tuples of

NP

-sets exist for all

k

≥ 2. Further, this is equivalent to the existence of a propositional proof system in which the disjointness of all

k

-tuples is shortly provable. We also show that a strengthening of this conditions characterizes the existence of optimal proof systems.

We study the equivalence relations on probability measures corresponding respectively to having the same Martin-Löf random reals, having the same Kolmogorov-Loveland random reals, and having the same computably random reals. In particular, we show that, when restricted to the class of strongly positive generalized Bernoulli measures, they all coincide with the classical equivalence, which requires that two measures have the same nullsets.

Domino tilings of finite domains of the plane are used to model dimer systems in statistical physics. In this paper, we study

dimer tilings

, which generalize domino tilings and are indeed equivalent to perfect matchings of planar graphs. We use

height functions

, a notion previously introduced by Thurston in [10] for domino tilings, to prove that a dimer tiling of a given domain can be computed using any Single-Source-Shortest-Paths algorithm on a planar graph. We also endow the set of dimers tilings of a given domain with a structure of distributive lattice and show that it can be effectively visited by a simple algorithmical operation called flip.

We apply the algebraic approach to infinite-valued constraint satisfaction to classify the computational complexity of all constraint satisfaction problems with templates that have a highly transitive automorphism group. A relational structure has such an automorphism group if and only if all the constraint types are Boolean combinations of the equality relation, and we call the corresponding constraint languages

equality constraint languages

. We show that an equality constraint language is tractable if it admits a constant unary or an injective binary polymorphism, and is NP-complete otherwise.

Given two strings (a text

t

of length

n

and a pattern

p

) and a natural number

w

,

window subsequence problems

consist in deciding whether

p

occurs as a subsequence of

t

and/or finding the number of size (at most)

w

windows of text

t

which contain pattern

p

as a subsequence,

i.e.

the letters of pattern

p

occur in the text window, in the same order as in

p

, but not necessarily consecutively (they may be interleaved with other letters). We are searching for subsequences in a text which is compressed using Lempel-Ziv-like compression algorithms, without decompressing the text, and we would like our algorithms to be almost optimal, in the sense that they run in time

O

(

m

) where

m

is the size of the compressed text. The pattern is uncompressed (because the compression algorithms are evolutive: various occurrences of a same pattern look different in the text).

We suggest a model of representation of algebraic varieties based on representative systems of points of its irreducible components. Deterministic polynomial–time algorithms to substantiate this model are described in zero–characteristic. The main result here is a construction of the intersection of algebraic varieties. As applications we get efficient algorithms for constructing the smooth stratification and smooth cover of an algebraic variety introduced by the author earlier.

We prove a number of simplified and improved separations between pairs of Resolution with bounded conjunction proof systems, Res(

d

) , as well as their tree-like versions, Res* (

d

). The tautologies, which we use, are natural combinatorial principles: the Least Number Principle (

LNP

n

) and a variant of the Induction Principle (

IP

n

).

LNP

n

is known to be easy for resolution. We prove that its relativisation is hard for resolution, and, more generally, the relativisation of

LNP

n

iterated

d

times provides a natural separation between Res(

d

) and Res(

d

+1). We prove the same result for the iterated relativisation of

IP

n

if the tree-like proof system Res*(

d

) is considered instead of Res (

d

).

Forbidden Patterns problem (FPP) is a proper generalisation of Constraint Satisfaction Problem (CSP). FPP was introduced in [1] as a combinatorial counterpart of MMSNP, a logic which was in turn introduced in relation to CSP by Feder and Vardi [2]. We prove that

Forbidden Patterns Problems are Constraint Satisfaction Problems

when restricted to

graphs of bounded degree

. This is a generalisation of a result by Häggkvist and Hell who showed that

F

-moteness of bounded-degree graphs is a CSP (that is, for a given graph

F

there exists a graph

H

so that the class of bounded-degree graphs that do not admit a homomorphism from

F

is exactly the same as the class of bounded-degree graphs that are homomorphic to

H

). Forbidden-pattern property is a strict generalisation of

F

-moteness (in fact of

F

-moteness combined with a CSP) as it involves both vertex- and edge-colourings of the graph

F

, and thus allows to express

$\mathcal{N}p$

-complete problems (while

F

-moteness is always in

$\mathcal{P}$

). We finally extend our result to arbitrary relational structures, and prove that every problem in MMSNP, restricted to connected inputs of bounded (hyper-graph) degree, is in fact in CSP.

Two methods are used usually for to establish the collapse result for theories. They use the isolation property and the reducibility property. Early it is shown that the reducibility implies the isolation. We prove that these methods are equivalent.

We propose a new model of restricted branching programs which we call

incremental branching programs

. We show that

syntactic

incremental branching programs capture previously studied structured models of computation for the problem GEN, namely marking machines [Co74] and Poon’s extension [Po93] of jumping automata on graphs [CoRa80]. We then prove exponential size lower bounds for our syntactic incremental model, and for some other restricted branching program models as well. We further show that nondeterministic syntactic incremental branching programs are provably stronger than their deterministic counterpart when solving a natural NL-complete GEN subproblem. It remains open if syntactic incremental branching programs are as powerful as unrestricted branching programs for GEN problems.

The logic of proofs is known to be complete for the semantics of proofs in Peano Arithmetic

PA

. In this paper we present a refinement of this theorem, we will show that we can assure that all the operations on proofs can be realized by feasible, that is PTIME-computable, functions. In particular we will show that the logic of proofs is complete for the semantics of proofs in Buss’ bounded arithmetic

S

$^{1}_{2}$

. In view of recent applications of the Logic of Proofs in epistemology this result shows that explicit knowledge in the propositional framework can be made computationally feasible.

In this paper we answer an open question about the exact bound on the maximal number of non-mergible states in nondeterministic finite automaton (NFA). It is shown that the maximal possible number of non-mergible states in a NFA that accepts a given regular language

L

is not greater than 2

n

– 1, where

n

is the number of states in the minimal deterministic finite automaton that accepts

L

. Next we show that the bound is reachable by constructing a NFA that have exactly 2

n

– 1 non-mergible states. As a generalization of this result we show that the number of states in a NFA that does not contain a subset of

k

mergible states, where

k

> 1, is bounded by (

k

– 1)(2

n

– 1) and the bound is reachable.

We prove a conjecture by A. Pnueli and strengthen it showing a sequence of “counting modalities” none of which is expressible in the temporal logic generated by the previous modalities, over the real line, or over the positive reals. We use this sequence to prove that over the real line there is no finite temporal logic that can express all the natural properties that arise when dealing with systems that evolve in continuous time.

We consider the problem of computing shortest paths in a directed arc-weighted graph

G

= (

V

,

A

) in the presence of an adversary that can block (interdict), for each vertex

v

∈

V

, a given number

p

(

v

) of the arcs

A

out

(

v

) leaving

v

. We show that if all arc-weights are non-negative then the single-destination version of the problem can be solved by a natural extension of Dijkstra’s algorithm in time

$$O(|A|+|V|{\rm log}|V|+\Sigma_{\upsilon\in{V}\ \backslash \{t\}}(|A_{out}(\upsilon)|-p(\upsilon)){\rm log}(p(\upsilon)+1)).$$

Our result can be viewed as a polynomial algorithm for a special case of the network interdiction problem where the adversary’s budget is node-wise limited. When the adversary can block a given number

p

of arcs distributed arbitrarily in the graph, the problem (

p

-most-vital-arcs problem) becomes NP-hard. This result is also closely related to so-called cyclic games. No polynomial algorithm computing the value of a cyclic game is known, though this problem belongs to both NP and coNP.

We study a quantitative model of traces,

i.e.

trace series which assign to every trace an element from a semiring. We show the coincidence of recognizable trace series with those which are definable by restricted formulas from a weighted logics over traces. We use a translation technique from formulas over words to those over traces, and vice versa. This way, we show also the equivalence of aperiodic and first-order definable trace series.

The nonforgetting restarting automaton is a restarting automaton that is not forced to reset its internal state to the initial state when executing a restart operation. We analyse the expressive power of the various deterministic and/or monotone variants of this model.

Non-effective cut elimination proof uses Koenig’s lemma to obtain a non-closed branch of a proof-search tree

τ

(without cut) for a first order formula

A

, if

A

is not cut free provable. A partial model (semi-valuation) corresponding to this branch and verifying ¬

A

is extended to a total model for ¬

A

using arithmetical comprehension. This contradicts soundness, if

A

is derivable with cut. Hence

τ

is a cut free proof of

A

. The same argument works for Herbrand Theorem. We discuss algorithms of obtaining cut free proofs corresponding to this schema and quite different from complete search through all possible proofs.

We present a new method of solving graph problems related to

VERTEX COVER

by enumerating and expanding appropriate sets of nodes. As an application, we obtain dramatically improved runtime bounds for two variants of the

VERTEX COVER

problem: In the case of

CONNECTED VERTEX COVER

, we take the upper bound from

O

*

(6

k

) to

O

*

(3.2361

k

) without large hidden factors. For

TREE COVER

, we show exactly the same complexity, improving vastly over the previous bound of

O

*

((2

k

)

k

). In the process, faster algorithms for solving subclasses of the Steiner tree problem on graphs are investigated.

Most assertions involving Shannon entropy have their Kolmogorov complexity counterparts. A general theorem of Romashchenko [4] states that every information inequality that is valid in Shannon’s theory is also valid in Kolmogorov’s theory, and vice verse. In this paper we prove that this is no longer true for ∀ ∃-assertions, exhibiting the first example where the formal analogy between Shannon entropy and Kolmogorov complexity fails.

Systems of language equations used by Ginsburg and Rice (“Two families of languages related to ALGOL”,

JACM

, 1962) to represent context-free grammars are modified to use the symmetric difference operation instead of union. Contrary to a natural expectation that these two types of equations should have incomparable expressive power, it is shown that equations with symmetric difference can express every recursive set by their unique solutions, every recursively enumerable set by their least solutions and every co-recursively-enumerable set by their greatest solutions. The solution existence problem is Π

1

-complete, the existence of a unique, a least or a greatest solution is Π

2

-complete, while the existence of finitely many solutions is Σ

3

-complete.

An example of arithmetic sentence which is deducible in intuitionistic predicate calculus with identity but is not strictly primitive recursively realizable by Z. Damnjanovic is proposed. It is shown also that the notions of primitive recursive realizability by Z. Damnjanovic and by S. Salehi are essentially different.

We introduce the logic of proofs whose modal counterpart is the modal logic

S5

. The language of Logic of Proofs

LP

is extended by a new unary operation of

negative checker

“?”. We define Kripke-style models for the resulting logic in the style of Fitting models and prove the corresponding Completeness theorem. The main result is the Realization theorem for the modal logic

S5

.

As specifications and verifications of concurrent systems employ Linear Temporal Logic (LTL), it is increasingly likely that logical consequence in LTL will be used in description of computations and parallel reasoning. We consider the linear temporal logic

$\mathcal{LTL^{U,B}_{N,N^{-1}} (Z)}$

extending the standard LTL by operations

B

(before) and

N

− 1

(previous). Two sorts of problems are studied: (i) satisfiability and (ii) description of logical consequence in

$\mathcal{LTL^{U,B}_{N,N^{-1}} (Z)}$

via admissible logical consecutions (inference rules). The model checking for LTL is a traditional way of studying such logics. Most popular technique based on automata was developed by M.Vardi (cf. [39, 6]). Our paper uses a reduction of logical consecutions and formulas of LTL to consecutions of a uniform form consisting of formulas of temporal degree 1. Based on technique of Kripke structures, we find necessary and sufficient conditions for a consecution to be not admissible in

$\mathcal{LTL^{U,B}_{N,N^{-1}} (Z)}$

. This provides an algorithm recognizing consecutions (rules) admissible in

$\mathcal{LTL^{U,B}_{N,N^{-1}} (Z)}$

by Kripke structures of size linear in the reduced normal forms of the initial consecutions. As an application, this algorithm solves also the satisfiability problem for

$\mathcal{LTL^{U,B}_{N,N^{-1}} (Z)}$

.

A necessary and sufficient criterion for the existence and value of the frequency of a letter in a morphic sequence is given. This is done using a certain incidence matrix associated with the morphic sequence. The characterization gives rise to a simple if-and-only-if condition that all letter frequencies exist.

We consider Shostak theories introduced in [1]. The class of Shostak theories consists of decidable first order equality theories, specified by two algorithms: a canoniser and a solver. A canoniser calculates the normal form of a term. A solver tests whether an equality can be reduced to an equivalent substitution and constructs this substitution when it exists. The examples of Shostak theories are linear arithmetics of integers and rational numbers, theories of lists, arrays, ets.[2].

For two strings

a

,

b

of lengths

m

,

n

respectively, the longest common subsequence (LCS) problem consists in comparing

a

and

b

by computing the length of their LCS . In this paper, we define a generalisation, called “the all semi-local LCS problem”, where each string is compared against all substrings of the other string, and all prefixes of each string are compared against all suffixes of the other string. An explicit representation of the output lengths is of size Θ ((

m

+

n

)

2

). We show that the output can be represented implicitly by a geometric data structure of size

O

(

m

+

n

), allowing efficient queries of the individual output lengths. The currently best all string-substring LCS algorithm by Alves et al. can be adapted to produce the output in this form. We also develop the first all semi-local LCS algorithm, running in time

o

(

mn

) when

m

and

n

are reasonably close. Compared to a number of previous results, our approach presents an improvement in algorithm functionality, output representation efficiency, and/or running time.

Let

x

be a binary string of length

n

. Consider the set

P

x

of all pairs of integers (

a

,

b

) such that the randomness deficiency of

x

in a finite set

S

of Kolmogorov complexity at most

a

is at most

b

. The paper [4] proves that there is no algorithm that for every given

x

upper semicomputes the minimal deficiency function

β

x

(

a

) = min{

b

| (

a

,

b

) ∈ 

p

x

}with precision

n

/log

4

n

. We strengthen this result in two respects. First, we improve the precision to

n

/4. Second, we show that there is no algorithm that for every given

x

enumerates a set at distance at most

n

/4 from

P

x

, which is easier than to upper semicompute the minimal deficiency function of

x

with the same accuracy.

Logic of proofs

$\mathcal{LP}$

, introduced by S. Artemov, originally designed for describing properties of formal proofs, now became a basis for the theory of knowledge with justification. So far, in epistemic systems with justification the corresponding “evidence part”, even for multi-agent systems, consisted of a single explicit evidence logic. In this paper we introduce logics describing two interacting explicit evidence systems. We find an appropriate formalization of the intended semantics and prove the completeness of these logics with respect to both symbolic and arithmetical models. Also, we find the forgetful projections for the logics with two proof predicates which are extensions of the bimodal logic

s4

2

.

We present an algorithm for deciding polarized higher-order subtyping without bounded quantification. Constructors are identified not only modulo

β

, but also

η

. We give a direct proof of completeness, without constructing a model or establishing a strong normalization theorem. Inductive and coinductive types are enriched with a notion of size and the subtyping calculus is extended to account for the arising inclusions between the sized types.

The possibility of solving elliptic and parabolic partial differential equations by using cellular neural networks with specific structure is investigated. The method of solving varialble coefficients parabolic PDEs is proposed. Issues of cellular neural network stability are examined.

Constrained total variation minimization and related convex optimization problems have applications in many areas of image processing and computer vision such as image reconstruction, enhancement, noise removal, and segmentation. We propose a new method to approximately solve this problem. Numerical experiments show that this method gets close to the globally optimal solution, and is 15-100 times faster for typical images than a state-of-the-art interior point method. Our method’s denoising performance is comparable to that of a state-of-the-art noise removal method of [4]. Our work extends our previously published algorithm for solving the constrained total variation minimization problem for 1D signals [13] which was shown to produce the globally optimal solution exactly in

O

(

N

log

N

) time where

N

is the number of data points.

Queries over streaming data offer the potential to provide timely information for modern database applications, such as sensor networks and web services. Isoline-based visualization of streaming data has the potential to be of great use in such applications. Dynamic (real-time) isoline extraction from the streaming data is needed in order to fully harvest that potential, allowing the users to see in real time the patterns and trends – both spatial and temporal – inherent in such data. This is the goal of this paper.

Our approach to isoline extraction is based on

data terrains

, triangulated irregular networks (TINs) where the coordinates of the vertices corresponds to locations of data sources, and the height corresponds to their readings. We dynamically maintain such a data terrain for the streaming data. Furthermore, we dynamically maintain an isoline (contour) map over this dynamic data network. The user has the option of continuously viewing either the current shaded triangulation of the data terrain, or the current isoline map, or an overlay of both.

For large networks, we assume that complete recomputation of either the data terrain or the isoline map at every epoch is impractical. If

n

is the number of data sources in the network, time complexity per epoch should be

O

(

log

n

) to achieve real-time performance. To achieve this time complexity, our algorithms are based on efficient dynamic data structures that are continuously updated rather than recomputed. Specifically, we use a

doubly-balanced interval tree

, a new data structure where both the tree and the edge sets of each node are balanced.

As far as we know, no one has applied TINs for data terrain visualization before this work. Our dynamic isoline computation algorithm is also new. Experimental results confirm both the efficiency and the scalability of our approach.

Defending against denial-of-service(DoS) attacks is one of the hardest security problems on the Internet today. One difficulty to thwart these attacks is totrace the source of the attacks because they often use incorrect, or spoofed IP source addresses to disguise the true origin Traceback mechanisms are a critical part of the defense against IP spoofing and DoS attacks, as well as being of forensic value to law enforcement. Currently proposed IP traceback mechanisms are inadequate to address the traceback. problem for the following reasons: they require DoS victims to gather thousands of packets to reconstruct a single attack path; they do not scale to large scale Distributed DoS attacks; and they do not support incremental deployment. This study suggests to find the attack origin through MAC address marking of the attack origin. It is based on an IP trace algorithm, called Marking Algorithm. It modifies the Marking Algorithm so that we can convey the MAC address of the intervening routers, and as a result it can trace the exact IP address of the original attacker. To improve the detection time, our algorithm also contains a technique to improve the packet arrival rate. By adjusting marking probability according to the distance from the packet origin, we were able to decrease the number of needed packets to traceback the IP address.

In this study, we compare the performance of well-known neural networks, namely, back-propagation (BP) algorithm, Neuro-Fuzzy network and Support Vector Machine (SVM) using the standard three database sets: Wisconsin breast cancer, Iris and wine data. Since such database have been useful for evaluating performance of a group of machine learning algorithms, a series of experiments have been carried out for three algorithms using the cross validation method. Results suggest that SVM outperforms the others and the Neuro-Fuzzy network is better than the BP algorithm for this data set.

This paper presents an improved multi-objective diversity control oriented genetic algorithm (MODCGA-II). The performance comparison between the MODCGA-II, a non-dominated sorting genetic algorithm II (NSGA-II) and an improved strength Pareto evolutionary algorithm (SPEA-II) is carried out where different two- and three-objective benchmark problems with specific multi-objective characteristics are used. The results indicate that the two-objective MODCGA-II solutions are better than the solutions generated by the NSGA-II and SPEA-II in terms of the closeness to the true Pareto optimal solutions and the uniformity of solution distribution along the Pareto front. In contrast, the NSGA-II in overall produces the best solutions in three-objective problems. As a result, the limitation of the proposed algorithm is identified.

The depth information in the face represents personal features in detail. In particular, the surface curvatures extracted from the face contain the most important personal facial information. The principal component analysis using the surface curvature reduces the data dimensions with less degradation of original information, and the proposed 3D face recognition algorithm collaborated into them. The recognition for the eigenface referred from the maximum and minimum curvatures is performed. To classify the faces, the cascade architectures of fuzzy neural networks, which can guarantee a high recognition rate as well as parsimonious knowledge base, are considered. Experimental results on a 46 person data set of 3D images demonstrate the effectiveness of the proposed method.

The approximation capability of fuzzy systems heavily depends on the shapes of the chosen fuzzy membership functions. When fuzzy systems are applied in adaptive control, computational complexity and generalization capability are another two important indexes we must consider. Inspired by the conclusion drawn by S.Mitaim and B.Kosko and wavelet analysis and SVM, the scaling kernel-based fuzzy system SKFS(Scaling Kernel-based Fuzzy System) is presented as a new simplified fuzzy system in this paper, based on Sinc x membership functions. SKFS can approximate any function in

L

2

(

R

), with much less computational complexity than classical fuzzy systems. Compared with another simplified fuzzy system GKFS(Gaussian Kernel-based Fuzzy System) using Gaussian membership functions, SKFS has a better approximation and generalization capabilities, especially in the coexistence of linearity and nonlinearity. Therefore, SKFS is very suitable for fuzzy control. Finally, several experiment results are used to demonstrate the effectiveness of the new simplified fuzzy system SKFS.

The design of parallel programs and parallel programming languages is a trade-off. On one hand the programs should be efficient. But the efficiency should not come at the price of non portability and unpredictability of performances. The portability of code is needed to allow code reuse on a wide variety of architectures and to allow the existence of legacy code. The predictability of performances is needed to guarantee that the efficiency will always be achieved, whatever is the used architecture.

Dijkstra’s algorithm is arguably the most popular computational solution to finding single source shortest paths. Increasing complexity of road networks, however, has posed serious performance challenge. While heuristic procedures based on geometric constructs of the networks would appear to improve performance, the fallacy of depreciated accuracy has been an obstacle to the wider application of heuristics in the search for shortest paths. The authors presented a shortest path algorithm that employs limited search heuristics guided by spatial arrangement of networks. The algorithm was tested for its efficiency and accuracy in finding one-to-one and one-to-all shortest paths among systematically sampled nodes on a selection of real-world networks of various complexity and connectivity. Our algorithm was shown to outperform other theoretically optimal solutions to the shortest path problem and with only little accuracy lost. More importantly, the confidence and accuracy levels were both controllable and predictable.

It is increasingly popular to adopt DSM systems to maximize parallelism beyond the limits of SMP. Wherein, a proper cache coherence scheme should be efficient at the memory overhead for maintaining the directories because of its significant impact on overall performance of the system. In this paper, we propose a new hybrid directory scheme which reduces the memory overhead of the directory and improves the memory access time by using our new hybrid directory scheme. We evaluate the performance of our proposed scheme by running six applications on an execution-driven simulator (RSIM). The simulation results show that the performance of a system with hybrid directory can achieve close to that of a multiprocessor with bit-vector directory.

Present paper is aimed to work out efficient algorithm of multi-chain manipulator path planning in 3D space with static polygonal obstacles. The resulting solution is based on navigational maps approach. Using this approach, manipulator features are considered as intellectual agent, and reachability information is stored in compact form. This enables fast adaptation to arbitrary parameters of manipulator and workspace. The paper describes two algorithms: (i) a local walkthrough with obstacle avoidance, and (ii) incremental navigational map building, performed at running stage. Both algorithms make an extensive use of the specific features of the problem. Working simultaneously, they allow real-time manipulator path planning, as well as self-learning in idle mode. Algorithms are implemented as a demonstration program.

Since operating systems (OSs) file systems are designed for a wide variety of applications, their performance may become suboptimal when the workload has a large proportion of certain atypical applications, such as a database management system (DBMS). Consequently most DBMS manufacturers have implemented their own file manager relegating the OS file system. This paper describes a novel page replacement strategy (Least Likely to Use) for buffer management in DBMSs, which takes advantage of very valuable information from the DBMS query planner. This strategy was implemented on an experimental DBMS and compared with other replacement strategies (LRU, Q2 and LIRS) which are used in OSs and DBMSs. The experimental results show that the proposed strategy yields an improvement in response time for most types of queries and attains a maximum of 97-284% improvement for some cases.

Visualization of large-scale data inherently requires dimensionality reduction to 1D, 2D, or 3D space. Autoassociative neural networks with bottleneck layer are commonly used as a nonlinear dimensionality reduction technique. However, many real-world problems suffer from incomplete data sets, i.e. some values may be missing. Common methods dealing with missing data include deletion of all cases with missing values from the data set or replacement with mean or “normal” values for specific variables. Such methods are appropriate when just a few values are missing. But in the case when a substantial portion of data is missing, these methods may significantly bias the results of modeling. To overcome this difficulty, we propose a modified learning procedure for the autoassociative neural network that directly takes into account missing values. The outputs of the trained network may be used for substitution of the missing values in the original data set.

This survey examines research in the area of race detection tech-niques. Diverse flavors of on-the-fly, ahead-of-time and post-mortem techniques are covered. This survey tries to present advantages and limitations exhibited by different race detection techniques.

Four knowledge sharing techniques based on fuzzy-Q learning are investigated in this paper. These knowledge sharing techniques are ‘Shared Memory’, ‘Adaptive Weighted Strategy Sharing’, ‘Exploration Guided Method’, and ‘Greatest Mass Method’. Different robot expertness measures are applied to these knowledge sharing techniques in order to improve learning performance. We proposed a new robot expertness measure based on regret evaluation. The regret takes uncertainty bounds of two best actions, i.e. greedy action and the second best action, into account. Simulations were performed to compare the effectiveness of the three expertness measures i.e. expertness based on accumulated rewards, on average move and on regret measure, when applied to different sharing techniques. Our proposed measure resulted in better performance than the other expertness measures. Analysis and comparison of different knowledge sharing techniques are also provided herein.

Symbolic Trajectory Evaluation (STE) is a formal verification technique for hardware. The current STE semantics is not faithful to the proving power of existing STE tools, which obscures the STE theory unnecessarily. In this paper, we present a new

closure semantics

for STE which does match the proving power of STE model-checkers, and makes STE easier to understand.

Many studies have shown that the imbalance of network channel traffic is of critical effect on the overall performance of multicomputer systems. In this paper, we analytically model the traffic rate crossing the network channels of a hypercube network under different working conditions. The effect of different parameters on the shaping of non-uniformity and traffic imbalance over network channels, are considered and analytical models for each case are proposed.

In this paper, we envision a solution for the problem of capturing an intruder in one of the most popular interconnection topologies, namely the pyramid. A set of agents collaborate to capture a hostile intruder in the network. While the agents can move in the network one hop at a time, the intruder is assumed to be arbitrarily fast, i.e. it can traverse any number of nodes contiguously as far as there are no agents in those nodes. Here we consider a new version of the problem where each agent can replicate new agents when needed, i.e. the algorithm starts with a single agent and new agents are created on demand. In particular, we propose two different algorithms on the pyramid network and we will later discuss about the merits of each algorithm based on some performance criteria.

A novel speech enhancement method based on empirical mode decomposition is proposed. The method is a fully data driven approach. Noisy speech signal is decomposed adaptively into oscillatory components called Intrinsic Mode Functions (IMFs) using a process called sifting. The empirical mode decomposition denoising involves thresholding each IMFs. A nonlinear function is introduced for amplitude thresholding. And then reconstructs the estimated speech signal using the processed IMFs. The experimental results show significant improvement in output SNR and quality as compared to recently reported results.

We present a method to convert the construction of binary decision diagrams (BDDs) into extended resolution proofs. Besides in proof checking, proofs are fundamental to many applications and our results allow the use of BDDs instead—or in combination with—established proof generation techniques, based for instance on clause learning. We have implemented a proof generator for propositional logic formulae in conjunctive normal form, called EBDDRES. We present details of our implementation and also report on experimental results. To our knowledge this is the first step towards a practical application of extended resolution.

Difference Systems of Sets (DSS) are combinatorial structures that are used in code synchronization. A DSS is

optimal

if the associated code has minimum redundancy for the given block length

n

, alphabet size

q

, and error-correcting capacity

ρ

. An algorithm is described for finding optimal DSS that admit prescribed symmetries defined by automorphisms of the cyclic group of order

n

, together with optimal DSS found by this algorithm.

Wireless local area networks (WLANs) are quickly becoming ubiquitous in our every day life. The increasing demand for ubiquitous services imposes more security threats to communications due to open mediums in wireless networks. The further widespread deployment of WLANs, however, depends on whether secure networking can be achieved. We propose a simple scheme for implementing authentication based on the One-Time Password (OTP) mechanism. The authentication protocol is proposed to solve the weak authentication and security flaw problem of the WEP in 802.11 WLAN. Further we have simulated the implementation of proposed scheme and EAP-OTP and analyzed the performance in terms of different performance metrics such as response time and authentication delay.

This paper drew up a personalized recommender system model combined the text categorization with the pagerank. The document or the page was considered in two sides: the content of the document and the domain it belonged to. The features were extracted in order to form the feature vector, which would be used in computing the difference between the documents or keywords with the user’s interests and the given domain. It set up the structure of four block levels in information management of a website. The link information was downloaded in the domain block level, which is the top level of the structure. In the host block level, the links were divided into two parts, the inter-link and the intra-link. All links were setup with different weights. The stationary eigenvector of the link matrix was calculated. The final order of documents was determined by the vector distance and the eigenvector of the link matrix.

In the embedded domain, not only performance, but also memory and energy are important concerns. A dual instruction set ARM processor, which supports a reduced Thumb instruction set with a smaller instruction length in addition to a full instruction set, provides an opportunity for a flexible tradeoff between these requirements. For a given program, typically the Thumb code is smaller than the ARM code, but slower than the latter, because a program compiled into the Thumb instruction set executes a larger number of instructions than the same program compiled into the ARM instruction set. Motivated by this observation, we propose a new Multi-objective Ant Colony Optimization (MOACO) algorithm that can be used to enable a flexible tradeoff between the code size and execution time of a program by using the two instruction sets selectively for different parts of a program. Our proposed approach determines the instruction set to be used for each function using a subset selection technique, and the execution time is the total one based on the profiling analyses of the dynamic behavior of a program. The experimental results show that our proposed technique can be effectively used to make the tradeoff between a program’s code size and execution time and can provide much flexibility in code generation for dual instruction set processors in general.

Developing an effective flow control algorithm to avoid congestion is a hot topic in computer network society. This paper gives a mathematical model for general network at first, then discrete control theory is proposed as a key tool to design a new flow control algorithm for congestion avoidance in high speed network, the proposed algorithm assures the stability of network system. The simulation results show that the proposed method can adjust the sending rate and queue level in buffer rapidly and effectively. Moreover the method is easy to implement and apply to high speed computer network.

This paper firstly provides an short introduction to least square support vector machine (LSSVM), a new class of kernel-based techniques introduced in statistical learning theory and structural risk minimization, then designs a training algorithm for LSSVM, and uses LSSVM to model and control nonlinear systems. Simulation experiments are performed and indicate that the proposed method provides satisfactory performance with excellent generalization property and achieves superior modeling performance to the conventional method based on neural networks, at same time achieves favourable control performance.

Regular expression pattern matching is widely used in computational biology. Searching through a database of sequences for a motif (a simple regular expression), or its variations is an important interactive process which requires fast motif-matching algorithms. In this paper, we explore and evaluate various representations of the database of sequences using suffix trees for two types of query problems for a given regular expression: 1) Find the first match, and 2) Find all matches. Answering Problem 1 increases the level and effectiveness of interactive motif exploration. We propose a framework in which Problem 1 can be solved in a faster manner than existing solutions while not slowing down the solution of Problem 2. We apply several heuristics both at the level of suffix tree creation resulting in modified tree representations, and at the regular expression matching level in which we search subtrees in a given predefined order by simulating a deterministic finite automaton that we create from the given regular expression. The focus of our work is to develop a method for faster retrieval of PROSITE motif (a restricted regular expression) matches from a protein sequence database. We show empirically the effectiveness of our solution using several real protein data sets.