Information Processing Letters

article

Resource-bounded measure on probabilistic classes

Philippe Moser

Information Processing Letters > 2008 > 106 > 6 > 241-245

We extend Lutz's resource-bounded measure to probabilistic classes, and obtain notions of resource-bounded measure on probabilistic complexity classes such as BPE and BPEXP. Unlike former attempts, our resource bounded measure notions satisfy all three basic measure properties, that is every singleton {L} has measure zero, the whole space has measure one, and “enumerable infinite unions” of measure...

article

Editorial Board

Information Processing Letters > 2008 > 106 > 6 > IFC

article

Rotation symmetry in algebraically generated cryptographic substitution tables

Vincent Rijmen, Paulo S.L.M. Barreto, Décio L. Gazzoni Filho

Information Processing Letters > 2008 > 106 > 6 > 246-250

Using some elementary properties of normal bases, we are able to show that bijective substitution tables generated from power maps or exponentiations over finite fields are linear equivalent to rotation-symmetric S-boxes. In the other direction, we show that rotation-symmetric S-boxes can always be described as a sum of power maps over finite fields.

article

Ant colony optimization with partial order reduction for discovering safety property violations in concurrent models

Francisco Chicano, Enrique Alba

Information Processing Letters > 2008 > 106 > 6 > 221-231

In this article we analyze the combination of ACOhg, a new metaheuristic algorithm, plus partial order reduction applied to the problem of finding safety property violations in concurrent models using a model checking approach. ACOhg is a new kind of ant colony optimization algorithm inspired by the foraging behavior of real ants equipped with internal resorts to search in very large search landscapes...

article

Should one always use repeated squaring for modular exponentiation?

Shmuel T. Klein

Information Processing Letters > 2008 > 106 > 6 > 232-237

Modular exponentiation is a frequent task, in particular for many cryptographic applications. To accelerate modular exponentiation for very large integers one may use repeated squaring, which is based on representing the exponent in the standard binary numeration system. We show here that for certain applications, replacing the standard system by one based on Fibonacci numbers may yield a new line...

article

The probability of “undefined” (non-converging) output in generating the universal probability distribution

Ray J. Solomonoff

Information Processing Letters > 2008 > 106 > 6 > 238-240

In order to generate a universal probability distribution to extrapolate a binary string x of length i, we feed random bits into a universal device, M. When we find an input string that gives an output matching x, we continue the successful input with random bits until M produces a zero or one as output. The relative probabilities of these two continuations can give a normalized prediction for the...

article

Dynamic bottleneck optimization for k-edge and 2-vertex connectivity

Orestis A. Telelis, Vassilis Zissimopoulos

Information Processing Letters > 2008 > 106 > 6 > 251-257

We consider the problem of updating efficiently the minimum value b over a weighted graph, so that edges with a cost less than b induce a spanning subgraph satisfying a k-edge or 2-vertex connectivity constraint, when the cost of an edge of the graph is updated. Our results include update algorithms of almost linear time (up to poly-logarithmic factors) in the number of vertices for all considered...

article

Vertex vulnerability parameters of Kronecker products of complete graphs

Aygul Mamut, Elkin Vumar

Information Processing Letters > 2008 > 106 > 6 > 258-262

Let G1 and G2 be two graphs. The Kronecker product G1×G2 of G1 and G2 has vertex set V(G1×G2)=V(G1)×V(G2) and edge set E(G1×G2)={(u1,v1)(u2,v2):u1u2∈E(G1) and v1v2∈E(G2)}. In this paper, we determine some vertex vulnerability parameters of the Kronecker product of complete graphs Km×Kn for n⩾m⩾2 and n⩾3.

INFONA - science communication portal

Information Processing Letters

Resource-bounded measure on probabilistic classes

Editorial Board

Rotation symmetry in algebraically generated cryptographic substitution tables

Ant colony optimization with partial order reduction for discovering safety property violations in concurrent models

Should one always use repeated squaring for modular exponentiation?

The probability of “undefined” (non-converging) output in generating the universal probability distribution

Dynamic bottleneck optimization for k-edge and 2-vertex connectivity

Vertex vulnerability parameters of Kronecker products of complete graphs

Filter options

Publication date

Keywords

INFONA - science communication portal

Information Processing Letters

Add recipient

Sending message cancelled

Are you sure you want to cancel sending this message?

Send message

Filter options

Publication date

Date range setting

Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.

Keywords

Reporting an error / abuse

Sending the report failed

Accessibility options