32nd International Symposium on
Mathematical Foundations of Computer Science
August 26 – August 31, 2007
Accepted Submissions
This is the list of all accepted papers together with their abstracts. The papers are listed in the order of their submission.
| State Complexity of Basic Operations on Suffix-Free Regular Languages by Yo-Sub Han and Kai Salomaa |
| Abstract: We investigate the state complexity of basic operations for suffix-free regular languages. The state complexity of an operation for regular languages is the number of states that are necessary and sufficient in the worst-case for the minimal deterministic finite-state automaton (DFA) that accepts the language obtained from the operation. We establish the precise state complexity of catenation, Kleene star, reversal and the Boolean operations for suffix-free regular languages. |
| Combinatorial Proof that Subprojective Constraint Satisfaction Problems are NP-Complete - A New Dichotomy Conjecture by Jaroslav Nesetril and Mark Siggers |
| Abstract: We introduce a new general polynomial-time construction- the fibre construction- which reduces any constraint satisfaction problem CSP(H) to the constraint satisfaction problem CSP(P) where P is any subprojective relational system. As a consequence we get a new proof (not using universal algebra) that CSP(P) is NP-complete for any subprojective (and thus for any projective) relational system. The fibre construction allows us to prove the NP-completeness part of the conjectured Dichotomy Classification of CSPs, previously obtained by algebraic methods. We show that this conjectured Dichotomy Classification is equivalent to the dichotomy of whether or not the template is subprojective. This approach is flexible enough to yield solutions to other interesting problems. In particular, it applies to bounded degree coloring problems and, with slight modification, to large girth coloring problems. Thus we use it to reduce the Feder-Hell-Huang and Kosto\v cka-Ne\v set\v ril-Smol\'{\i}kov\' a problems to the Dichotomy Classification of coloring problems. |
| Dobrushin conditions for systematic scan with block dynamics by Kasper Pedersen |
| Abstract: We study the mixing time of systematic scan Markov chains on finite spin systems. It is known that, in a single site setting, the mixing time of systematic scan can be bounded in terms of the influences sites have on each other. We generalise this technique for bounding the mixing time of systematic scan to block dynamics, a setting in which a (constant size) set of sites are updated simultaneously. In particular we consider the parameter $\alpha$, corresponding to the maximum influence on any site, and show that if $\alpha<1$ then the corresponding systematic scan Markov chain mixes rapidly. As applications of this method we prove $O(\log n)$ mixing of systematic scan (for any scan order) for heat-bath updates of edges for proper $q$-colourings of a general graph with maximum vertex-degree $\Delta$ when $q\geq2\Delta$. We also apply the method to improve the number of colours required in order to obtain mixing in $O(\log n)$ scans for systematic scan for heat-bath updates on trees, using some suitable block updates. |
| What are Iteration Theories? by Jiri Adamek, Stefan Milius and Jiri Velebil |
| Abstract: We prove that iteration theories can be introduced as algebras for the monad ${\mathbb{R}}{\mathrm{at}}$ on the category of signatures assigning to every signature $\Sigma$ the rational-$\Sigma$-tree signature. This supports the claim that iteration theories axiomatize precisely the equational properties of least fixed points in domain theory: ${\mathbb{R}}{\mathrm{at}}$ is the monad of free rational theories and every rational theory has a continuous completion. |
| VPSPACE and a transfer theorem over the complex field by Pascal Koiran and Sylvain Perifel |
| Abstract: We extend the transfer theorem of [KP07] to the complex field. That is, we investigate the links between the class VPSPACE of families of polynomials and the Blum-Shub-Smale model of computation over C. Roughly speaking, a family of polynomials is in VPSPACE if its coefficients can be computed in polynomial space. Our main result is that if (uniform, constant-free) VPSPACE families can be evaluated efficiently then the class PAR_C of decision problems that can be solved in parallel polynomial time over the complex field collapses to P_C. As a result, one must first be able to show that there are VPSPACE families which are hard to evaluate in order to separate P from NP over C, or even from PAR_C. |
| Approximation Algorithms for the Maximum Internal Spanning Tree Problem by Gabor Salamon |
| Abstract: We consider the Maximum Internal Spanning Tree problem which is to find a spanning tree of a given graph having a maximum number of non-leaf nodes. From an optimization point of view, this problem is equivalent to the Minimum Leaf Spanning Tree problem, and is NP-hard as being a generalization of the Hamiltonian Path problem. Although, there is no constant approximation for the Minimum Leaf Spanning Tree problem, Maximum Internal Spanning Tree can be approximated within a factor of 2.
In this paper we improve this factor by giving a 9/5-approximation algorithm. We also deal with the node-weighted case, when the weight-sum of internal nodes is to be maximized. For this problem, we show a (2*Delta-3)-approximation for general graphs, and a 2-approximation for claw-free graphs. All of our algorithms are based on local improvement steps. |
| NP by means of lifts and shadows by Gabor Kun and Jaroslav Nesetril |
| Abstract: We show that every NP problem is polynomially equivalent to a simple combinatorial problem: the membership problem for a special class of digraphs. These classes are defined by means of shadows (projections) and by finitely many forbidden colored (lifted) subgraphs. Our characterization is motivated by the analysis of syntactical subclasses with the full computational power of NP, which were first studied by Feder and Vardi. Our approach applies to many combinatorial problems and it induces the characterization of coloring problems (CSP) defined by means of shadows. This turns out to be related to homomorphism dualities. We list several applications. Particularly, we show a surprising richness of coloring problems when restricted to most frequent graph classes. Using results of Nesetril and Ossona de Mendez for bounded expansion classes (which include bounded degree and proper minor closed classes) we prove that the restriction of every class defined as the shadow of finitely many colored subgraphs equals to the restriction of a coloring (CSP) class. |
| Well Supported Approximate Equilibria in Bimatrix Games: A Graph Theoretic Approach by Spyros Kontogiannis and Paul Spirakis |
| Abstract: In view of the apparent intractability of constructing Nash equilibria (NE in short) in polynomial time, even for bimatrix games, understanding the limitations of the approximability of the problem is an important challenge. In this work we study the existence and tractability of a notion of approximate equilibria in bimatrix games, called \emph{well supported approximate Nash Equilibria} (SuppNE in short). Roughly speaking, while the typical notion of approximate NE demands that each player gets a payoff at most an additive constant $\e>0$ smaller than its best possible payoff (given the opponent's strategy), in a SuppNE each it is assumed that each player adopts with positive probability only \emph{approximate pure best responses}, ie, actions whose payoffs are at most additive constant $\e>0$ smaller than the most profitable action (given again the opponent's strategy).
As a first step we prove the existence of $\e-$SuppNE for any constant $\e\in(0,1)$, with only logarithmic support sizes for both players. This immediately implies a subexponential--time construction of such a SuppNE, by support enumeration. Consequently we propose a graph theoretic approach for the polynomial--time construction of SuppNE in win lose and normalized bimatrix games (ie, whose payoff matrices take values from $\{0,1\}$ and $[0,1]$ respectively), whose quality depends on the \emph{girth} of the Nash Dynamics graph in the win lose game, or a proper win lose image of the original normalized game. Our constructions are very successful in sparse games with large girth: We manage to construct $\order{1}-$SuppNE for win lose games and $\frac{1+\order{1}}{2}-$SuppNE for normalized games. In particular, for very sparse win lose games we construct an exact NE in polynomial time. It is noted that the supports of this NE may be \emph{arbitrary} and the ranks of the payoff matrices are also arbitrary. Therefore, an attack based on support enumeration, or the consideration of payoff matrices with fixed ranks, would not be necessarily applicable in such games. Finally we prove the simplicity of constructing SuppNE both in random normalized games and in random win lose games. In the former case we prove that the uniform full mix is an $\order{1}-$SuppNE, while in the case of win lose games, we show that (with high probability) there is either a PNE or a $0.5$-SuppNE with support sizes only $2$. |
| Communication in Networks with Random Dependent Faults by Evangelos Kranakis, Michel Paquette and Andrzej Pelc |
| Abstract: The aim of this paper is to study communication in networks where nodes fail in a random dependent way. In order to capture fault dependencies, we introduce the {\em neighborhood fault} model, where damaging events, called {\em spots}, occur randomly and {\em independently} with probability $p$ at nodes of a network, and cause faults in the given node and all of its neighbors. Faults at distance at most $2$ become dependent in this model and are positively correlated. We investigate the impact of spot probability on feasibility and time of communication in the fault-free part of the network. We show a network which supports fast communication with high probability, if $p \leq 1/c\log n$. We also show that communication is not feasible with high probability in most classes of networks, for constant spot probabilities. For smaller spot probabilities, high probability communication is supported even by bounded degree networks. It is shown that the torus supports communication with high probability when $p$ decreases faster than $1/n^{1/2}$, and does not when $p \in 1/O(n^{1/2})$. Furthermore, a network built of tori is designed, with the same fault-tolerance properties and additionally supporting fast communication. We show, however, that networks of degree bounded by a constant $d$ do not support communication with high probability, if $p \in 1/O(n^{1/d})$. While communication in networks with independent faults was widely studied, this is the first analytic paper which investigates network communication for random dependent faults. |
| Online and Offline Access to Short Lists by Torben Hagerup |
| Abstract: We consider the list-update problem introduced by Sleator and Tarjan, specializing it to the case of accesses only and focusing on short lists. We describe a new optimal offline algorithm, faster than the best previous algorithm when the number of accesses is sufficiently large relative to the number l of items. We also give a simple optimal offline algorithm for l=3. Taking c_l to denote the best competitive ratio of a randomized online algorithm for the list-access problem with l items, we demonstrate that c_3=6/5 and give new upper and lower bounds on c_4. Finally we prove a strengthened lower bound for general l. |
| An Improved Claw Finding Algorithm Using Quantum Walk by Seiichiro Tani |
| Abstract: The claw finding problem has been studied in terms of query complexity as one of the problems closely connected to cryptography. For given those two functions, $f$ and $g$, as an oracle which have domains of size $N$ and $M$ $(N\leq M)$, respectively, and the same range, the goal of the problem is to find $i$ and $j$ $(i\neq j)$ such that $f(i)=g(j)$. This paper gives a quantum-walk-based algorithm that solves this problem; it improves the previous upper bounds. Our algorithm can be generalized to find a claw of $k$ functions for any integer $k>1$ where the domains of the functions may have different size. |
| On the complexity of game isomorphism by Joaquim Gabarro, Maria Serna and Alina Garcia |
| Abstract: We consider the question of when two games are equivalent and the computational complexity of deciding such a property for strategic games. We introduce three types of isomorphisms depending on which structure of the game is preserved: strict, weak, and local. We show that the computational complexity of the game isomorphism problem depends on the level of succinctness of the description of the input games but it is independent on the way the isomorphism is defined. Utilities or preferences in games can be represented by Turing machines (general form) or tables (explicit form). When the games are given in general form, we show that the game isomorphism problem is equivalent to the circuit isomorphism problem. When the games are given in explicit form, we show that the game isomorphism problem is equivalent to the graph isomorphism problem. |
| Hardness Results for Tournament Isomorphism and Automorphism by Fabian Wagner |
| Abstract: A tournament is a graph, in which each pair of distinct vertices is connected by exactly one directed edge. Tournaments are an important graph class, for which isomorphism testing seems to be easier to compute than for the isomorphism problem of general graphs. We show, that tournament isomorphism and tournament automorphism is hard under DLOGTIME uniform AC^0 many-one reductions for the complexity classes NL, C=L, PL (probabilistic logarithmic space), for logarithmic space modular counting classes ModkL with odd k >= 3 and for DET, the class of problems, NC^1 reducible to the determinant. These lower bounds have been proven for graph isomorphism, see [27]. |
| Efficient Provably-Secure Hierarchical Key Assignment Schemes by Alfredo De Santis, Anna Lisa Ferrara and Barbara Masucci |
| Abstract: A hierarchical key assignment scheme is a method to assign some private information and encryption keys to a set of classes in a partially ordered hierarchy, in such a way that the private information of a higher class can be used to derive the keys of all classes lower down in the hierarchy. In this paper we design and analyze hierarchical key assignment schemes which are provably-secure and support dynamic updates to the hierarchy with local changes to the public information and without requiring any private information to be re-distributed. -We first show an encryption based construction which is provably secure with respect to key indistinguishability, requires a single computational assumption and improves on previous proposals. -Then, we show how to reduce key derivation time at the expense of an increment of the amount of public information, by improving a previous result. -Finally, we show a construction using as a building block a public-key broadcast encryption scheme. In particular, one of our constructions provides constant private information and public information linear in the number of classes in the hierarchy. |
| Optimal gossiping in directed geometric radio networks in presence of dynamical faults by Andrea Clementi, Angelo Monti, Francesco Pasquale and Riccardo Silvestri |
| Abstract: We study deterministic fault-tolerant gossiping protocols in directed Geometric Radio Networks (in short, directed GRN). Unpredictable node and link faults may happen during every time slot of the protocol's execution. We first consider the "single-message" model where every node can send at most one message per time slot. We provide a protocol that, on any directed GRN "G" of "n" nodes, completes gossiping in O(n \Delta) time (where "\Delta" is the maximal in-degree of "G") and has message complexity O(n^2). Both bounds are then shown to be optimal. As for the "combined-message" model, we give a protocol working in optimal completion time O(D\Delta) (where "D" is the maximal source eccentricity) and message complexity O(Dn). Finally, our protocol performs the (single) broadcast operation within the same optimal time and optimal message complexity O(n). |
| Uncover low degree vertices and minimise the mess: independent sets in random regular graphs by William Duckworth and Michele Zito |
| Abstract: We present algorithmic lower bounds on the size of the largest independent sets of vertices in a random $d$-regular graph. Our bounds hold with probability approaching one as the size of the graph tends to infinity. |
| The Complexity of Solitaire by Pierre McKenzie and Luc Longpré |
| Abstract: Klondike is the well-known 52-card Solitaire game available on almost every computer. The problem of determining whether an n-card Klondike initial configuration can lead to a win is shown NP-complete. The problem remains NP-complete when only three suits are allowed instead of the usual four. When only two suits of opposite color are available, the problem is shown NL-hard. When the only two suits have the same color, two restrictions are shown in AC0 and in NL respectively. When a single suit is allowed, the problem drops in complexity down to AC0[3], that is, the problem is solvable by a family of constant depth unbounded fan-in {AND, OR, MOD3}-circuits. Other cases are studied: for example, ``no King'' variant with an arbitrary number of suits of the same color and with an empty ``pile'' is NL-complete. |
| Small alliances in graphs by Rodolfo Carvajal, Martín Matamala, Nicolás Schabanel and Iván Rapaport |
| Abstract: Let $G=(V,E)$ be a graph.
A nonempty subset $S \subseteq V$
is a (strong defensive) \emph{alliance} of $G$ if every node in $S$
has at least as many neighbors in $S$ than in $V \setminus S$. This work
is motivated by the following observation: when $G$ is a locally structured graph
its nodes typically belong to small alliances. Despite the fact that
finding the smallest alliance in a graph is NP-hard, we can at least compute
in polynomial time $depth_G(v)$,
{\emph{the minimum distance one has to move away from
an arbitrary node $v$ in order to find an alliance containing $v$}}.
We define $depth(G)$ as the sum of $depth_G(v)$ taken over all the nodes $v \in V$. We prove that the depth of $G$ can be at most $\frac{1}{4}(3n^2+1)$ and it can be computed in time $O(n^3)$. Intuitively, the value $depth(G)$ should be small for clustered graphs. This is the case for the plane grid, which has a depth $2n$. We generalize previous fact by proving that the depth of any bridgeless planar graphs of degree 3 and 4 is at most $\frac{15}{2}n$. The idea that clustered graphs are those having a lot of small alliances leads us to another, probabilistic approach. We analyze the value of $r_p(G)=\PP\{S\text{ contains an alliance}\}$, when $S \subseteq V$ is randomly chosen (each node independently with probability $p$). This probability goes to 1 for planar regular graphs of degree 3 and 4. Finally, we generalize an already known result by proving that if the minimum degree of the graph is logarithmically lower bounded and if $S$ is a big random set $(p> \frac{1}{2})$, then also $r_p(G) \to 1$ as $n \to {\infty}$. |
| Analysis of maximal repetitions in strings by Maxime Crochemore and Lucian Ilie |
| Abstract: The cornerstone of any algorithm computing all repetitions in strings of length $n$ in ${\mathcal O}(n)$ time is the fact that the number of maximal repetitions (runs) is linear. Therefore, the most important part of the analysis of the running time of such algorithms is counting the number of runs. Kolpakov and Kucherov~[FOCS'99] proved it to be $cn$ but could not provide any value for $c$. Recently, Rytter~[STACS'06] proved that $c\le 5$. His analysis has been improved by Puglisi et al. to obtain $3.48$ and by Rytter to $3.44$ (both submitted). The conjecture of Kolpakov and Kucherov, supported by computations, is that $c=1$. Here we improve dramatically the previous results by proving that $c\le 1.6$ and show how it could be improved by computer verification down to $1.18$ or less. While the conjecture may be very difficult to prove, we believe that our work provides a good approximation for all practical purposes. For the stronger result concerning the linearity of the sum of exponents, we give the first explicit bound: $5.6n$. Kolpakov and Kucherov did not have any and Rytter considered ``unsatisfactory" the bound that could be deduced from his proof. Our bound could be as well improved by computer verification down to $2.9n$ or less. |
| Series-parallel languages on scattered and countable posets by Nicolas Bedon and Chloé Rispal |
| Abstract: We initiate a study on automata recognizing labelled posets constructed from scattered and countable linear orderings. More precisely, the class of labelled-posets considered in this paper is the smallest containing letters, closed under finite parallel operation and sequential product indexed by all countable and scattered linear orderings. The first result of this paper establishes that those labelled-posets are precisely the $N$-free ones. The second result is a Kleene-like theorem, which establishes that the class of languages of labelled-posets accepted by branching automata is exactly the class of rational languages. This generalizes both the finite (Lodaya and Weil) and $\omega$-labelled-posets (Kuske) cases, and the Kleene-like theorem on words on linear orderings (Bruyre and Carton). |
| Packing and Squeezing Subgraphs into Planar Graphs by Fabrizio Frati, Markus Geyer and Michael Kaufmann |
| Abstract: We consider the following problem: Given a set $S$ of graphs, each of $n$ vertices, construct an $n$-vertex planar graph $G$ containing all the graphs of $S$ as subgraphs. We distinguish the variant in which any two graphs of $S$ are required to have disjoint edges in $G$ (known as 'packing') from the variant in which distinct graphs of $S$ can share edges in $G$ (called 'squeezing'). About the packing variant we show that an arbitrary tree and an arbitrary spider tree can always be packed in a planar graph, improving in this way partial results recently given on this problem. Concerning the squeezing variant, we establish which classes of graphs can generally be squeezed in a planar graph, and which classes cannot. |
| Real Time Language Recognition on 2D Cellular Automata: Dealing with Non-Convex Neighborhoods by Martin Delacourt and Victor Poupet |
| Abstract: In this paper we study language recognition by two-dimensional cellular automata on different possible neighborhoods. Since it is known that all complete neighborhoods are linearly equivalent we focus on a natural sub-linear complexity class: the real time. We show that any complete neighborhood V is sufficient to recognize in real time any language that can be recognized in real-time by a cellular automaton working on the convex hull of V. |
| New Approximability Results for 2-Dimensional Packing Problems by Klaus Jansen and Roberto Solis-Oba |
| Abstract: In the strip packing problem it is desired to pack a set of rectangles, each of width and length at most $1$, into a strip of unit width and minimum length. In this paper we present asymptotic polynomial time approximation schemes (APTAS) for this problem without and with $90^o$ rotations. The additive constant in the approximation ratios of both algorithms is $1$, thus improving on the additive term in the approximation ratios of the algorithm by Kenyon and R\'emila (for the problem without rotations) and Jansen and van Stee (for the problem with rotations), both of which have a much larger additive constant $O(1/\varepsilon^2)$, $\varepsilon > 0$. The algorithms were derived from the study of the following rectangle packing problem: Given a set $R$ of rectangles with positive profits, the goal is to pack a subset of $R$ into a unit size square bin $[0,1] \times [0,1]$ so that the total profit of the rectangles that are packed is maximized. We present algorithms that for any value $\epsilon > 0$ find a subset $R' \subseteq R$ of rectangles of total profit at least $(1-\epsilon) OPT$, where $OPT$ is the profit of an optimum solution, and pack them (either without rotations or with $90^o$ rotations) into the augmented bin $[0,1] \times [0,1+\epsilon]$. |
| Hard Problems on Quadratic Forms and a New Cryptographic Primitive by Rupert J. Hartung and Claus-Peter Schnorr. |
| Abstract: We introduce computational problems on ternary indefinite integral quadratic forms which we assume to be hard, namely the problems of finding representations of integers and transformations between equivalent forms. As an application we present an identification scheme which is a proof of knowledge and conditionally zero-knowledge. Finally, we show that assuming a variant of the Cohen-Lenstra Heuristics on class numbers, some related problems are NP-complete under randomized reductions. |
| Semisimple algebras of almost minimal rank over the reals by Markus Bläser and Andreas Meyer |
| Abstract: A famous lower bound for the bilinear complexity of the multiplication in associative algebras is the Alder--Strassen bound. Algebras for which this bound is tight are called algebras of minimal rank. After 25 years of research, these algebras are now well understood. We start the investigation of the algebras for which the Alder--Strassen bound is off by one. As a first result we completely characterize the semisimple algebras over $\R$ whose bilinear complexity is by one larger than the Alder--Strassen bound. |
| On Approximation of Bookmark Assignments by Yuichi Asahiro, Eiji Miyano, Toshihide Murata and Hirotaka Ono |
| Abstract: Consider a rooted directed acyclic graph $G = (V, E)$ with root $r$, representing a collection $V$ of web pages connected via a set $E$ of hyperlinks. Each node $v$ is associated with the probability that a user wants to access the node $v$. The access cost is defined as the expected number of steps required to reach a node from the root $r$. A bookmark is an additional shortcut from $r$ to a node of $G$, which may reduce the access cost. The bookmark assignment problem is to find a set of bookmarks that achieves the greatest improvement in the access cost. For the problem, the paper presents a polynomial time approximation algorithm with factor $(1-1/e)$, and shows that there exists no polynomial time approximation algorithm with a better constant factor than $(1-1/e)$ unless ${\cal NP}\subseteq DTIME(N^{O(\log\log N)})$, where $N$ is the size of the inputs. |
| Real Computational Universality: The Word Problem for a class of groups with infinite presentation by Klaus Meer and Martin Ziegler |
| Abstract: The word problem for discrete groups is well-known to be undecidable by a Turing Machine; more precisely, it is reducible both to and from and thus equivalent to the discrete Halting Problem. The present work introduces and studies a real extension of the word problem for a certain class of groups which are presented as quotient groups of a free group and a normal subgroup. As main difference with discrete groups, these groups may be generated by UNcountably many generators with index running over certain sets of real numbers. This includes a variety of groups which are not captured by the finite framework of the classical word problem. Our contribution extends computational group theory from the discrete to the Blum-Shub-Smale (BSS) model of real number computation. It provides a step towards applying BSS theory, in addition to semi-algebraic geometry, also to further areas of mathematics. The main result establishes the word problem for such groups to be not only semi-decidable (and thus reducible FROM) but also reducible TO the Halting Problem for such machines. It thus gives the first non-trivial example of a problem COMPLETE, that is, computationally universal for this model. |
| Properties Complementary to Program Self-Reference by John Case and Samuel Moelius |
| Abstract: In computability theory, program self-reference is formalized by the not-necessarily-constructive form of Kleenes Recursion Theorem (krt). In a programming system in which krt holds, for any preassigned, algorithmic task, there exists a program that, in a sense, creates a copy of itself, and then performs that task on the self-copy. Herein, properties complementary to krt are considered. Of particular interest are those properties involving the implementation of control structures. One main result is that no property involving the implementation of denotational control structures is complementary to krt. This is in contrast to a result of Royer, which showed that implementation of if-then-else --- a denotational control structure --- is complementary to the constructive form of Kleenes Recursion Theorem. Examples of non-denotational control structures whose implementation is complementary to krt are then given. Some such control structures so nearly resemble denotational control structures that they might be called quasi-denotational. |
| Congestion Games with Player-Specific Constants by Marios Mavronicolas, Igal Milchtaich, Burkhard Monien and Karsten Tiemann |
| Abstract: We consider a special case of weighted congestion games with player-specific latency functions where each player uses for each particular resource a fixed (non-decreasing) delay function together with a player-specific constant. For each particular resource, the resource-specific delay function and the player-specific constant (for that resource) are composed by means of a group operation (such as addition or multiplication) into a player-specific latency function. We assume that the underlying group is a totally ordered abelian group.
In this way, we obtain the class of (weighted) congestion games with player-specific constants; we observe that this class is contained in the new intuitive class of dominance (weighted) congestion games. We focus on pure Nash equilibria for congestion games with player-specific constants; for these equilibria, we study questions of existence, computational complexity and convergence via improvement or best-reply steps of players. Our findings are as follows: Games on parallel links: - Every unweighted congestion game has an ordinal potential; hence, it has the Finite Improvement Property and a pure Nash equilibrium. - There is a weighted congestion game with 3 players on 3 parallel links that does not have the Finite Best-Reply Property (and hence neither the Finite Improvement Property). - There is a particular best-reply cycle for general weighted congestion games with player-specific latency functions and 3 players whose outlaw implies the existence of a pure Nash equilibrium. This cycle is indeed outlawed for dominance (weighted) congestion games with 3 players -- and hence for (weighted) congestion games with player-specific constants and 3 players. Hence, (weighted) congestion games with player-specific constants and 3 players have a pure Nash equilibrium. Network congestion games: For unweighted symmetric network congestion games with player-specific additive constants, it is PLS-complete to find a pure Nash equilibrium. Arbitrary (non-network) congestion games: Every weighted congestion game with linear delay functions and player-specific additive constants (and hence with affine player-specific latency functions has an ordinal potential; hence, it has the Finite Improvement Property and a pure Nash equilibrium. |
| Finding Patterns In Given Intervals by Maxime Crochemore, Costas Iliopoulos and M Sohel Rahman |
| Abstract: In this paper, we study the pattern matching problem in given intervals. Depending on whether the intervals are given a priori for pre-processing, or during the query along with the pattern or, even in both cases, we develop solutions for different variants of this problem. In particular, we present efficient indexing schemes for each of the above variants of the problem. |
| Towards a Rice Theorem on Traces of Cellular Automata by Pierre Guillon and Julien Cervelle |
| Abstract: The trace subshift of a cellular automaton is the subshift of all possible columns that may appear in a space-time diagram. We prove the undecidability of a rather large class of problems over trace subshifts of cellular automata. |
| Dynamic Matchings in Convex Bipartite Graphs by Gerth Stølting Brodal, Loukas Georgiadis, Kristoffer Arnsfelt Hansen and Irit Katriel |
| Abstract: We consider the problem of maintaining a maximum matching in a convex bipartite graph $G=(V,E)$ under a set of update operations which includes insertions and deletions of vertices and edges. It is not hard to show that it is impossible to maintain an explicit representation of a maximum matching in sub-linear time per operation, even in the amortized sense. Despite this difficulty, we develop a data structure which maintains the set of vertices that participate in a maximum matching in $O(\log^2{|V|})$ amortized time per update and reports the status of a vertex (matched or unmatched) in constant worst-case time. Our structure can report the mate of a matched vertex in the maximum matching in worst-case $O(\min \{ k \log^2{|V|} + \log{|V|}, |V| \log{|V|}\})$ time, where $k$ is the number of update operations since the last query for the same pair of vertices was made. Also, we give an $O(\sqrt{|V|} \log^2{|V|})$-time amortized bound for this pair query. |
| A Linear Time Algorithm for the $k$ Maximal Sums Problem by Gerth Stølting Brodal and Allan Grønlund Jørgensen |
| Abstract: Finding the sub-vector with the largest sum in a sequence of $n$ reals is known as the maximum sum problem. Finding the $\K$ sub-vectors with the largest sums is a natural extension of this, and is known as the $\K$ maximal sums problem. In this paper we design an optimal $O(n+\K)$ time algorithm for the $\K$ maximal sums problem. We use this algorithm to obtain algorithms solving the two dimensional $\K$ maximal sums problem, where the input is an $m \times n$ matrix, in time $O(m^2\cdot n + \K)$ with $m\leq n$, and the general $d$ dimensional problem in $O(n^{2d-1} + \K)$ time. The space usage of all the algorithms can be reduced to $O(n^{d-1}+\K)$. This leads to the first algorithm for the $\K$ maximal sums problem in one dimension using $O(n+\K$) time and $O(k)$ space. |
| Traces of term-automatic graphs by Antoine Meyer |
| Abstract: In formal language theory, many families of languages are defined using grammars or finite acceptors like pushdown automata and Turing machines. For instance, context-sensitive languages are the languages generated by growing grammars, or equivalently those accepted by Turing machines whose work tape size is proportional to that of their input. A few years ago, a new characterization of context-sensitive languages as the path languages of rational graphs (infinite graphs defined by sets of finite-state transducers) was established. We investigate a similar characterization in the more general framework of graphs defined by term transducers. In particular, we show that the languages of term-automatic graphs between regular sets of vertices coincide with the languages accepted by alternating linearly bounded Turing machines. As a technical tool, we also introduce an arborescent variant of tiling systems, which provides yet another characterization of these languages. |
| Selfish Load Balancing under Partial Knowledge by Elias Koutsoupias, Panagiota Panagopoulou and Paul Spirakis |
| Abstract: We consider $n$ selfish agents or players, each having a load, who want to place their loads to one of two bins. The agents have an incomplete picture of the world: They know some loads exactly and only a probability distribution for the rest. We study Nash equilibria for this model, we compute the Price of Anarchy for some cases and show that sometimes extra information adversely affects the Divergence Ratio (a kind of subjective Price of Anarchy). |
| Rewriting Conjunctive Queries Determined by Views by Foto Afrati |
| Abstract: Answering queries using views is the problem which examines how to derive the answers to a query when we only have the answers to a set of views. Constructing rewritings is a widely studied technique to derive those answers. In this paper we consider the problem of existence of rewritings in the case where the answers to the views uniquely determine the answers to the query. Specifically, we say that a view set V determines a query Q if for any two databases D1,D2 it holds: V(D1) = V(D2) implies Q(D1)=Q(D2). We consider the case where query and views are defined by conjunctive queries and investigate the question: If a view set V determines a query Q, is there an equivalent rewriting of Q using V? We present here interesting cases where there are such rewritings in the language of conjunctive queries. Interestingly, we identify a class of conjunctive queries, CQ-path for which a view set can produce equivalent rewritings for ``almost all'' queries which are determined by this view set. We introduce a problem which relates determinacy to query equivalence. We show that there are cases where restricted results can carry over to broader classes of queries. |
| On time lookahead algorithms for the online data acknowledgement problem by Csanad Imreh and Tamas Nemet |
| Abstract: In this work we investigate semi-online algorithms for the data acknowledgement problem, which have the extra information about the arrival time of the packets in the following time interval of length c. We present an algorithm with the smallest possible competitive ratio for the maximum of delay type objective function. In the case of the sum of delay type objective function we present an 1+O(1/c)-competitive algorithm. Moreover we show that no algorithm may have smaller competitive ratio than 1+\Omega(1/c^2)$ |
| Relating complete and partial solution for problems similar to graph automorphism by Takayuki Nagoya and Seinosuke Toda |
| Abstract: It is known that, given a graph G, finding a pair of vertices (v,w) where v is mapped to w by some non-trivial automorphism on G is as hard as computing a non-trivial automorphism. In this paper, we prove that, given a graph G, computing even a single vertex that is mapped to other vertex by a non-trivial automorphism is as hard as computing a non-trivial automorphism. We also prove that RightGA has same property. On the other hand, we prove that if PrefixGA has this property then GI is polynomial-time Turing reducible to GA. |
| Complexity Upper Bounds for Classical Locally Random Reductions Using a Quantum Computational Argument by Rahul Tripathi |
| Abstract: We use a \emph{quantum computational} argument to prove, for any integer k >= 2, a complexity upper bound for nonadaptive k-query classical locally random reductions (LRRs) that allow bounded-errors. Extending and improving a recent result of Pavan and Vinodchandran [PV], we prove that if a set L has a nonadaptive 2-query classical LRR to functions g and h, where both g and h can output O(log n) bits, such that the reduction succeeds with probability at least 1/2 + 1/\poly(n), then L is in PP^{NP}/poly. Previous complexity upper bound for nonadaptive 2-query classical LRRs was known only for much restricted LRRs: LRRs in which the target
functions can only take values in {0,1,2} and the error probability is zero [PV]. For k > 2, we prove that if a set L has a nonadaptive k-query classical LRR to
\emph{boolean} functions g_1, g_2, ..., g_k such that the reduction succeeds with probability at least 2/3 and the distribution on (k/2+ \sqrt{k})-element subsets of queries depends only on the input length, then L is in PP^{NP}/poly. Previously, for no constant k > 2, complexity upper bound for nonadaptive k-query classical LRRs was known even for LRRs that do not make errors.
Our proofs follow a two stage argument: (1) simulate a nonadaptive k-query classical LRR by a 1-query quantum \emph{weak} LRR, and (2) upper bound the complexity of this quantum weak LRR. To carry out the two stages, we formally define nonadaptive quantum weak LRRs, and prove that if a set L has a 1-query quantum weak LRR to a function g, where g can output \emph{polynomial} number of bits, such that the reduction succeeds with probability at least 1/2 + 1/poly(n), then L is in PP^{NP}/poly. |
| Linear Circuits, Two-Variable Logic and Weakly Blocked Monoids by Andreas Krebs, Christoph Behle and John Mark Mercer |
| Abstract: Following recent works connecting two-variable logic to circuits and monoids, we establish, for numerical predicate sets P satisfying a certain closure property, a one-to-one correspondence between FO[<,P]-uniform linear circuits, two-variable formulas with P predicates, and weak block products of monoids. In particular, we consider the case of linear TC0, majority quantifiers, and finitely typed monoids. This correspondence will hold for any numerical predicate set which is FO[<]-closed and whose predicates do not depend on the input length. |
| Extending the Notion of Rationality of Selfish Agents: Second Order Nash Equilibria by Vittorio Biló and Michele Flammini |
| Abstract: Motivated by the increasing interest of the Computer Science community in the study and understanding of non-cooperative systems, we present a novel model for formalizing the rational behavior of agents with a more farsighted view of the consequences of their actions. This approach yields a framework creating new equilibria, which we call Second Order equilibria, starting from a ground set of traditional ones. By applying our approach to pure Nash equilibria, we define the set of Second Order Nash equilibria and present their applications to the Prisoner's Dilemma game, to an instance of Braess's Paradox in the $Wardrop$ model and to the $KP$ model with identical machines. |
| Expander Properties and the Cover Time of Random Intersection Graphs by Sotiris Nikoletseas, Christoforos Raptopoulos and Paul Spirakis |
| Abstract: We investigate important combinatorial and algorithmic properties of $G_{n, m, p}$ random intersection graphs. In particular, we prove that with high probability (a) random intersection graphs are expanders, (b) random walks on such graphs are ``rapidly mixing" (in particular they mix in logarithmic time) and (c) the cover time of random walks on such graphs is optimal (i.e. it is $\Theta(n \log{n})$). All results are proved for $p$ very close to the connectivity threshold and for the interesting, non-trivial range where random intersection graphs differ from classical $G_{n, p}$ random graphs. |
| Adapting parallel algorithms to the W-Stream model, with applications to graph problems by Camil Demetrescu, Bruno Escoffier, Gabriel Moruz and Andrea Ribichini |
| Abstract: In this paper we show how parallel algorithms can be turned into efficient streaming algorithms for several classical combinatorial problems in the $\wstr$ model. In this model, at each pass one input stream is read and one output stream is written; streams are pipelined in such a way that the output stream produced at pass $i$ is given as input stream at pass $i+1$. Our techniques give new insights on developing streaming algorithms and yield optimal algorithms (up to polylog factors) for several classical problems in this model including sorting, connectivity, minimum spanning tree, biconnected components, and maximal independent set. |
| The Maximum Solution Problem on Graphs by Peter Jonsson, Gustav Nordh and Johan Thapper |
| Abstract: We study the complexity of the problem {\sc Max Sol} which is a natural optimisation version of the graph homomorphism problem. Given a fixed target graph $H$ with $V(H) \subseteq \mathbb{N}$, an instance of the problem is a graph $G$ and the goal is to find a homomorphism $f: G \rightarrow H$ which maximises $\sum_{g \in G} f(g)$. {\sc Max Sol} can be seen as a restriction of the {\sc Min Hom}-problem [Gutin et al., Disc. App. Math., 154 (2006), pp. 881-889] and as a natural generalisation of {\sc Max Ones} to larger domains. We present new tools with which we classify the complexity of {\sc Max Sol} for graphs with degree less than or equal to $2$ as well as for small graphs ($|V(H)| \leq 4$). We also study an extension of {\sc Max Sol} where value lists and arbitrary weights are allowed; somewhat surprisingly, this problem is polynomial-time equivalent to {\sc Min Hom}. |
| Exact algorithms for $L(2,1)$-labeling of graphs by Jan Kratochvil, Dieter Kratsch and Mathieu Liedloff |
| Abstract: The notion of distance constrained graph labelings, motivated by the Frequency Assignment Problem, reads as follows: A mapping from the vertex set of a graph $G=(V,E)$ into an interval of integers $[0..k]$ is an $L(2,1)$-labeling of $G$ of span $k$ if any two adjacent vertices are mapped onto integers that are at least 2 apart, and every two vertices with a common neighbor are mapped onto distinct integers. It is known that for any fixed $k\ge 4$, deciding the existence of such a labeling is an NP-complete problem. We present exact exponential time algorithms that are faster than the naive $O((k+1)^n)$ algorithm that would try all possible mappings. The improvement is best seen in the first NP-complete case of $k=4$ -- here the running time of our algorithm is $O(1.3161^n)$. |
| The Power of Two Prices: Beyond Cross-Monotonicity by Yvonne Bleischwitz, Burkhard Monien, Florian Schoppmann and Karsten Tiemann |
| Abstract: Assuming strict consumer sovereignty (CS*), when can a cost-sharing mechanism simultaneously satisfy group-strategyproofness (GSP) and $\beta$-budget-balance ($\beta$-BB)? Moulin gave very simple mechanisms that are GSP and 1-BB for submodular costs. In this work, we consider arbitrary (not necessarily submodular) symmetric costs, which only depend on the number of served agents: - Already for 4 agents, we show that symmetry of costs is not sufficient for the existence of a GSP and 1-BB mechanism any more. However, for only 3 agents, we give a GSP and 1-BB mechanism. - We introduce two-price cost-sharing forms (2P-CSFs) that define agents' cost-shares. We present a novel mechanism that is GSP given any such 2P-CSF. If costs are subadditive, we give an algorithm to compute 2P-CSFs that are 4/3-BB. We show that, in general, this is the best 2P-CSFs can yield. Yet, this is a significant improvement over 2-BB, which is the best Moulin mechanisms can achieve. - We apply our technique to the scheduling problem of minimizing makespan and obtain a quadratic-time algorithm for computing GSP and (4d)/3-BB mechanisms (d is the number of different processing times). For the case of identical jobs and identical machines, we give a 2P-CSF that is even 1-BB. - For a specific non-symmetric setting, we extend our techniques to guarantee GSP and 1-BB. A common key feature of all our mechanisms is a preference order on the set of agents. Higher cost-shares are always payed by least preferred agents. |
| Transition Graphs of Rewriting Systems over Unranked Trees by Alex Spelten and Christof Löding |
| Abstract: We investigate algorithmic properties of infinite transition graphs that are generated by rewriting systems over unranked trees. Two kinds of such rewriting systems are studied. For the first, we construct a reduction to ranked trees via an encoding and to standard ground tree rewriting, thus showing that the generated classes of transition graphs coincide. In the second rewriting formalism, we use subtree rewriting combined with a new operation called flat prefix rewriting and show that strictly more transition graphs are obtained while the first-order theory with reachability relation remains decidable. |
| On The Complexity Of Computing Treelength by Daniel Lokshtanov |
| Abstract: We resolve the computational complexity of determining the treelength of a graph, thereby solving an open problem of Dourusboure and Gavoille, who introduced this parameter, and asked to determine the complexity of recognizing graphs of bounded treelength. While recognizing graphs with treelength 1 is easily seen as equivalent to recognizing chordal graphs, which can be done in linear time, the computational complexity of recognizing graphs with treelength 2 was unknown until this result. We show that the problem of determining whether a given graph has treelength at most k is NP-complete for every fixed k ≥ 2, and use this result to show that treelength in weighted graphs is hard to approximate within a factor smaller than 3/2. Additionally, we show that treelength can be computed in time O(1.8899^n) by giving an exact exponential time algorithm for the Chordal Sandwich problem and showing how this algorithm can be used to compute the treelength of a graph. |
| Nearly Private Information Retrieval by Amit Chakrabarti and Anna Shubina |
| Abstract: A private information retrieval scheme is a protocol whereby a client
obtains a record from a database without the database operators
learning anything about which record the client requested. This
concept is well studied in the theoretical computer science
literature. Here, we study a generalization of this idea where we
allow a small amount of information about the client's intent to be
leaked.
Despite having relaxed the privacy requirement, we are able to prove three fairly strong lower bounds on such schemes, for various parameter settings. These bounds extend previously known lower bounds in the traditional setting of perfect privacy and, in one case, improve upon the previous best result that handled imperfect privacy. |
| On (k,l)-Leaf Powers by Andreas Brandstadt and Peter Wagner |
| Abstract: We say that, for $k \ge 2$ and $\ell>k$, a tree $T$ is a {\em $(k,\ell)$-leaf root of a graph $G=(V_G,E_G)$} if $V_G$ is the set of leaves of $T$, for all edges $xy \in E_G$, the distance $d_T(x,y)$ in $T$ is at most $k$ and, for all non-edges $xy \not\in E_G$, $d_T(x,y)$ is at least $\ell$. A graph~$G$ is a {\em $(k,\ell)$-leaf power} if it has a $(k,\ell)$-leaf root. This new notion generalises the concept of $k$-leaf power which was introduced and studied by Nishimura, Ragde and Thilikos motivated by the search for underlying phylogenetic trees. Recently, a lot of work has been done on $k$-leaf powers and roots as well as on their variants phylogenetic roots and Steiner roots. For $k=3$ and $k=4$, structural characterisations and linear time recognition algorithms of $k$-leaf powers are known, and, recently, a polynomial time recognition of 5-leaf powers was given. For larger $k$, the recognition problem is open. We give structural characterisations of $(k,\ell)$-leaf powers, for some $k$ and $\ell$, which also imply an efficient recognition of these classes, and in this way we also improve and extend a recent paper by Kennedy, Lin and Yan on strictly chordal graphs and leaf powers. |
| Finding Paths between Graph Colourings: PSPACE-completeness and Superpolynomial Distances by Paul Bonsma and Luis Cereceda |
| Abstract: Suppose we are given a graph $G$ together with two proper
vertex $k$-colourings of $G$, $\alpha$ and $\beta$. How easily can we decide
whether it is possible to transform $\alpha$ into $\beta$ by recolouring
vertices of $G$ one at a time, making sure we always have a proper
$k$-colouring of $G$? This decision problem is trivial for $k=2$, and decidable
in polynomial time for $k=3$. Here we prove it is PSPACE-complete for all $k
\ge 4$, even for bipartite graphs, as well as for: (i) planar graphs and $4 \le
k \le 6$, and (ii) bipartite planar graphs and $k=4$. The values of $k$ in (i)
and (ii) are tight.
We also exhibit, for every $k \ge 4$, a class of graphs $\{G_{N,k}:N\in \mathbb{N}^*\}$, together with two $k$-colourings for each $G_{N,k}$, such that the minimum number of recolouring steps required to transform the first colouring into the second is superpolynomial in the size of the graph. This is in stark contrast to the $k=3$ case, where it is known that the minimum number of recolouring steps is at most quadratic in the number of vertices. The graphs $G_{N,k}$ can also be taken to be bipartite, as well as (i) planar for $4 \le k \le 6$, and (ii) planar and bipartite for $k=4$. This provides a remarkable correspondence between the tractability of the problem and its underlying structure. |
| Space-conscious compression by Travis Gagie and Giovanni Manzini |
| Abstract: Compression is most important when space is in short supply, so compression algorithms are often implemented in limited memory. Most analyses ignore memory constraints as an implementation detail, however, creating a gap between theory and practice. In this paper we consider the effect of memory limitations on compression algorithms. In the first part we assume the memory available is fixed and prove nearly tight upper and lower bounds on how much memory is needed to compress a string close to its $k$-th order entropy. In the second part we assume the memory available grows (slowly) as more and more characters are read. In this setting we show that the rate of growth of the available memory determines the speed at which the compression ratio approaches the entropy. In particular, we establish a relationship between the rate of growth of the sliding window in the LZ77 algorithm and its convergence rate. |
| Shuffle expressions and words with nested data by Mikolaj Bojanczyk and Henrik Bjorklund |
| Abstract: In this paper, we develop a theory that connects: a) words with nested data values and b) shuffle expressions. We study two cases, which we call ordered and unordered. In the unordered case, we show that emptiness (of the two related problems) is decidable. In the ordered case, we prove undecidability. As a proof vehicle for the latter, we introduce the notion of higher-order multicounter automata. |
| Reachability Problems in Quaternion Matrix and Rotation Semigroups by Paul Bell and Igor Potapov |
| Abstract: We examine computational problems on quaternion matrix and rotation semigroups. It is shown that in the ultimate case of quaternion matrices, in which multiplication is still associative, most of the decision problems for matrix semigroups are undecidable in dimension two. The geometric interpretation of matrix problems over quaternions is presented in terms of rotation problems for the 2 and 3-sphere. In particular we show that the reachability of the rotation problem is undecidable on the 3-sphere and other rotation problems can be formulated as matrix problems over complex and hypercomplex numbers. |
| Optimal Randomized Comparison Based Algorithms for Collision by Riko Jacob |
| Abstract: We consider the well known problem of finding two identical elements, called a collision, in a list of~$n$ numbers. Here, the (very fast) comparison based algorithms are randomized and will only report existing collisions, and do this with (small) probability~$p$, the success probability. We find a trade-off between~$p$ and the running time~$t$, and show that this trade-off is optimal up to a constant factor. For worst-case running time~$t$, the optimal success probability is % $p=\Theta\left(\min\{{t}/{n},1\}{t}/(n\log t)\right)$. For expected running time~$t$, the success probability is~$p=\Theta\left(t/(n\log n)\right)$. |
| Height-Deterministic Pushdown Automata by Dirk Nowotka and Jiri Srba |
| Abstract: We define the notion of height-deterministic pushdown automata, a model where for any given input string the stack heights during any (nondeterministic) computation on the input are a priori fixed. Different subclasses of height-deterministic pushdown automata, strictly containing the class of regular languages and still closed under boolean language operations, are considered. Several of such language classes have been described in the literature. Here, we suggest a natural and intuitive model that subsumes all the formalisms proposed so far by employing height-deterministic pushdown automata. Decidability and complexity questions are also considered. |
| A $1+\phi$ lower bound for truthful scheduling by Elias Koutsoupias and Angelina Vidali |
| Abstract: We give an improved lower bound for the approximation ratio of truthful mechanisms for the unrelated machines scheduling problem. The mechanism design version of the problem which was proposed and studied in the seminal paper of Nisan and Ronen is at the core of the emerging area of Algorithmic Game Theory. The new lower bound is a step towards the final resolution of this important problem. |
| Minimizing variants of visibly pushdown automata by Patrick Chervet and Igor Walukiewicz |
| Abstract: The minimization problem for visibly pushdown automata (VPA) is studied. Two subclasses of VPA are introduced: call driven automata, and blocks automata. For the first class, minimization results are presented unifying and generalizing those present in the literature. A drawback of this class, and all other classes known till now, is that it is exponentially less succint than VPA. The second class, block automata, is introduced to address this problem. These automata are as succint as VPA. A minimization procedure for them is presented that requires one additional parameter to be fixed. An example of an exponential gain in succintness is presented. |
| Progresses in the Analysis of Stochastic 2D Cellular Automata: a Study of Asynchronous 2D Minority by Damien Regnault, Nicolas Schabanel and Eric Thierry |
| Abstract: Cellular automata are often used to model systems in physics,
social sciences, biology that are inherently asynchronous. Over the past 20
years, studies have demonstrated that the behavior of cellular automata
drastically changed under asynchronous updates. Still, the few mathematical
analyses of asynchronism focus on one-dimensional probabilistic cellular
automata, either on single examples or on specific classes. As for other
classic dynamical systems in physics, extending known methods from one- to
two-dimensional systems is a long lasting challenging problem.
In this paper, we address the problem of analysing an apparently simple 2D asynchronous cellular automaton: 2D Minority where each cell, when fired, updates to the minority state of its neighborhood. Our experiments reveal that in spite of its simplicity, the minority rule exhibits a quite complex response to asynchronism. By focusing on the fully asynchronous regime, we are however able to describe completly the asymptotic behavior of this dynamics as long as the initial configuration satisfies some natural constraints. Besides these technical results, we have strong reasons to believe that our technics relying on defining an energy function from the transition table of the automaton may be extended to the wider class of threshold automata. |
| Structural analysis of gapped motifs of a string by Esko Ukkonen |
| Abstract: We investigate the structure of the set of gapped motifs (repeated patterns with don't cares) of a given string of symbols. A natural equivalence classification is introduced for the motifs, based on their pattern of occurences, and another classification for the occurrence patterns, based on the induced motifs. Quadratic-time algorithms are given for finding a maximal representative for an equivalence class while the problems of finding a minimal representative are shown NP-complete. Maximal gapped motifs are shown to be composed of blocks that are maximal non-gapped motifs. These can be found using suffix-tree techniques. This leads to a bound on the number of gapped motifs that have a fixed number of non-gapped blocks. |