Displaying similar documents to “Time and space complexity of reversible pebbling”

Equivalences and Congruences on Infinite Conway Games

Furio Honsell, Marina Lenisa, Rekha Redamalla (2012)

RAIRO - Theoretical Informatics and Applications

Similarity:

Taking the view that infinite plays are , we study and . These admit a sharp presentation, where non-terminating games are seen as a and game contructors, such as , as . We have shown, in a previous paper, that Conway’s theory of terminating games can be rephrased naturally in terms of game . Namely, various conceptually independent notions of can be defined and shown to coincide on Conway’s terminating games. These are...

Equivalences and Congruences on Infinite Conway Games

Furio Honsell, Marina Lenisa, Rekha Redamalla (2012)

RAIRO - Theoretical Informatics and Applications

Similarity:

Taking the view that infinite plays are , we study and . These admit a sharp presentation, where non-terminating games are seen as a and game contructors, such as , as . We have shown, in a previous paper, that Conway’s theory of terminating games can be rephrased naturally in terms of game . Namely, various conceptually independent notions of can be defined and shown to coincide on Conway’s terminating games. These are...

Dynamic Programming Principle for tug-of-war games with noise

Juan J. Manfredi, Mikko Parviainen, Julio D. Rossi (2012)

ESAIM: Control, Optimisation and Calculus of Variations

Similarity:

We consider a two-player zero-sum-game in a bounded open domain Ω described as follows: at a point x ∈ Ω, Players I and II play an ε-step tug-of-war game with probability α, and with probability β (α + β = 1), a random point in the ball of radius ε centered at x is chosen. Once the...

A note on constructing infinite binary words with polynomial subword complexity

Francine Blanchet-Sadri, Bob Chen, Sinziana Munteanu (2013)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

Most of the constructions of infinite words having polynomial subword complexity are quite complicated, , sequences of Toeplitz, sequences defined by billiards in the cube, etc. In this paper, we describe a simple method for constructing infinite words over a binary alphabet  {  }  with polynomial subword complexity . Assuming contains an infinite number of ’s, our method is based on the gap function which gives the distances between consecutive ’s. It is known that...

Complexity of infinite words associated with beta-expansions

Christiane Frougny, Zuzana Masáková, Edita Pelantová (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

We study the complexity of the infinite word associated with the Rényi expansion of in an irrational base . When is the golden ratio, this is the well known Fibonacci word, which is Sturmian, and of complexity . For such that is finite we provide a simple description of the structure of special factors of the word . When =1 we show that . In the cases when or max} we show that the first difference of the complexity function takes value in for every , and consequently we determine...

Square-root rule of two-dimensional bandwidth problem

Lan Lin, Yixun Lin (2011)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

The bandwidth minimization problem is of significance in network communication and related areas. Let be a graph of vertices. The two-dimensional bandwidth () of is the minimum value of the maximum distance between adjacent vertices when is embedded into an  ×  grid in the plane. As a discrete optimization problem, determining () is NP-hard in general. However, exact results for this parameter can be derived for some special classes of graphs. This...

Algebraic and graph-theoretic properties of infinite -posets

Zoltán Ésik, Zoltán L. Németh (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

A -labeled -poset is an (at most) countable set, labeled in the set , equipped with partial orders. The collection of all -labeled -posets is naturally equipped with binary product operations and -ary product operations. Moreover, the -ary product operations give rise to -power operations. We show that those -labeled -posets that can be generated from the singletons by the binary and -ary product operations form the free algebra on in a variety axiomatizable...

Computing and proving with pivots

Frédéric Meunier (2013)

RAIRO - Operations Research - Recherche Opérationnelle

Similarity:

A simple idea used in many combinatorial algorithms is the idea of . Originally, it comes from the method proposed by Gauss in the 19th century for solving systems of linear equations. This method had been extended in 1947 by Dantzig for the famous simplex algorithm used for solving linear programs. From since, a pivoting algorithm is a method exploring subsets of a ground set and going from one subset to a new one ′ by deleting an element inside and adding an element outside : ′ =  ...

Corrigendum: Complexity of infinite words associated with beta-expansions

Christiane Frougny, Zuzana Masáková, Edita Pelantová (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

We add a sufficient condition for validity of Propo- sition 4.10 in the paper Frougny (2004). This condition is not a necessary one, it is nevertheless convenient, since anyway most of the statements in the paper Frougny (2004) use it.


Closure properties of hyper-minimized automata

Andrzej Szepietowski (2011)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

Two deterministic finite automata are almost equivalent if they disagree in acceptance only for finitely many inputs. An automaton is hyper-minimized if no automaton with fewer states is almost equivalent to . A regular language is canonical if the minimal automaton accepting is hyper-minimized. The asymptotic state complexity () of a regular language is the number of states of a hyper-minimized automaton for a language finitely different from . In this paper we show...

Closure properties of hyper-minimized automata

Andrzej Szepietowski (2012)

RAIRO - Theoretical Informatics and Applications

Similarity:

Two deterministic finite automata are almost equivalent if they disagree in acceptance only for finitely many inputs. An automaton is hyper-minimized if no automaton with fewer states is almost equivalent to . A regular language is canonical if the minimal automaton accepting is hyper-minimized. The asymptotic state complexity () of a regular language is the number of states of a hyper-minimized automaton...

Differential approximation of NP-hard problems with equal size feasible solutions

Jérôme Monnot (2010)

RAIRO - Operations Research

Similarity:

In this paper, we focus on some specific optimization problems from graph theory, those for which all feasible solutions have an equal size that depends on the instance size. Once having provided a formal definition of this class of problems, we try to extract some of its basic properties; most of these are deduced from the equivalence, under differential approximation, between two versions of a problem  which only differ on a linear transformation of their objective functions. This...