Search

In the sliding window streaming model the goal is to compute an output value that only depends on the last n symbols from the data stream. Thereby, only space sublinear in the window size n should be used. Quite often randomization is used in order to achieve this goal. In the literature, one finds two different correctness criteria for randomized sliding window algorithms: (i) one can require that for every data stream and every time instant t, the algorithm computes a correct output value with high probability, or (ii) one can require that for every data stream the probability that the algorithm computes at every time instant a correct output value is high. Condition (ii) is stronger than (i) and is called "strict correctness" in this paper. The main result of this paper states that every strictly correct randomized sliding window algorithm can be derandomized without increasing the worst-case space consumption. [ABSTRACT FROM AUTHOR]

We study the complexity of algorithmic problems for matrices that are represented by multi-terminal decision diagrams (MTDD). These are a variant of ordered decision diagrams, where the terminal nodes are labeled with arbitrary elements of a semiring (instead of 0 and 1). A simple example shows that the product of two MTDD-represented matrices cannot be represented by an MTDD of polynomial size. To overcome this deficiency, we extended MTDDs to + MTDDs by allowing componentwise symbolic addition of variables (of the same dimension) in rules. It is shown that accessing an entry, equality checking, matrix multiplication, and other basic matrix operations can be solved in polynomial time for + MTDD-represented matrices. On the other hand, testing whether the determinant of a MTDD-represented matrix vanishes is P S P A C E-complete, and the same problem is N P-complete for + MTDD-represented diagonal matrices. Computing a specific entry in a product of MTDD-represented matrices is # P-complete. [ABSTRACT FROM AUTHOR]

One-counter automata (OCA) are pushdown automata which operate only on a unary stack alphabet. We study the computational complexity of model checking computation tree logic (CTL) on transition systems induced by OCA. A PSPACE upper bound is inherited from the modal μ-calculus for this problem proved by Serre. First, we analyze the periodic behavior of CTL over OCA and derive a model checking algorithm whose running time is exponential only in the number of control locations and a syntactic notion of the formula that we call leftward until depth. In particular, model checking fixed OCA against CTL formulas with a fixed leftward until depth is in P. This generalizes a corresponding recent result of Göller, Mayr, and To for the expression complexity of CTL's fragment EF. Second, we prove that already over some fixed OCA, CTL model checking is PSPACE-hard, i.e., expression complexity is PSPACE-hard. Third, we show that there already exists a fixed CTL formula for which model checking of OCA is PSPACE-hard, i.e., data complexity is PSPACE-hard as well. To obtain the latter result, we employ two results from complexity theory: (i) Converting a natural number in Chinese remainder presentation into binary presentation is in logspace-uniform NC¹ and (ii) PSPACE is AC0-serializable. We demonstrate that our approach can be used to obtain further results. We show that model checking CTL's fragment EF over OCA is hard for PNP, thus establishing a matching lower bound. Moreover, we show that the following problem is hard for PSPACE: Given a one-counter Markov decision process, a set of target states with counter value zero each, and an initial state, to decide whether the probability that the initial state will eventually reach one of the target states is arbitrarily close to 1. This improves a recently proved lower bound for every level of the boolean hierarchy shown by Brázdil et al. Finally, we prove that there is a fixed CTL formula for which model checking 2-clock timed automata is PSPACE-hard, generalizing a PSPACE-hardness result for the combined complexity by Laroussinie, Markey, and Schnoebelen. [ABSTRACT FROM AUTHOR]

Abstract: We show that the membership problem in a finitely generated submonoid of a graph group (also called a right-angled Artin group or a free partially commutative group) is decidable if and only if the independence graph (commutation graph) is a transitive forest. As a consequence we obtain the first example of a finitely presented group with a decidable generalized word problem that does not have a decidable membership problem for finitely generated submonoids. We also show that the rational subset membership problem is decidable for a graph group if and only if the independence graph is a transitive forest, answering a question of Kambites, Silva, and the second author [M. Kambites, P.V. Silva, B. Steinberg, On the rational subset problem for groups, J. Algebra 309 (2) (2007) 622–639]. Finally we prove that for certain amalgamated free products and HNN-extensions the rational subset and submonoid membership problems are recursively equivalent. In particular, this applies to finitely generated groups with two or more ends that are either torsion-free or residually finite. [Copyright &y& Elsevier]

Let G be a finitely generated virtually-free group. We consider the Birget–Rhodes expansion of G, which yields an inverse monoid and which is denoted by IM(G) in the following. We show that for a finite idempotent presentation P, the word problem of a quotient monoid IM(G)/P can be solved in linear time on a RAM. The uniform word problem, where G and the presentation P are also part of the input, is EXPTIME-complete. With IM(G)/P we associate a relational structure, which contains for every rational subset L of IM(G)/P a binary relation, consisting of all pairs (x,y) such that y can be obtained from x by right multiplication with an element from L. We prove that the first-order theory of this structure is decidable. This result implies that the emptiness problem for Boolean combinations of rational subsets of IM(G)/P is decidable, which, in turn implies the decidability of the submonoid membership problem of IM(G)/P. These results were known previously for free groups, only. Moreover, we provide a new algorithmic approach for these problems, which seems to be of independent interest even for free groups. We also show that one cannot expect decidability results in much larger frameworks than virtually-free groups because the subgroup membership problem of a subgroup H in an arbitrary group G can be reduced to a word problem of some IM(G)/P, where P depends only on H. A consequence is that there is a hyperbolic group G and a finite idempotent presentation P such that the word problem is undecidable for some finitely generated submonoid of IM(G)/P. In particular, the word problem of IM(G)/P is undecidable. [ABSTRACT FROM AUTHOR]

We consider a compressed form of the word problem for finitely presented monoids, where the input consists of two compressed representations of words over the generators of a monoid M, and we ask whether these two words represent the same monoid element of M. Words are compressed using straight-line programs, i.e., context-free grammars that generate exactly one word. For several classes of finitely presented monoids we obtain completeness results for complexity classes in the range from P to EXPSPACE. As a by-product of our results on compressed word problems we obtain a fixed deterministic context-free language with a PSPACE-complete compressed membership problem. The existence of such a language was open so far. Finally, we will investigate the complexity of the compressed membership problem for various circuit complexity classes. [ABSTRACT FROM AUTHOR]

Online fault-diagnosis is applied to various systems to enable an automatic monitoring and, if applicable, the recovery from faults to prevent the system from failing. For a sound decision on occurred faults, typically a large amount of sensor measurements and state variables has to be gathered, analyzed and evaluated in real-time. Due to the complexity and the nature of distributed systems all this data needs to be communicated among the network, which is an expensive affair in terms of communication resources and time. In this paper we present compression strategies that utilize the fact that many of these data streams are highly correlated and can be compressed simultaneously. Experimental results show that this can lead to better compression ratios compared to an individual compression of the data streams. Moreover, the algorithms support real-time constraints for time-triggered architectures and enable the data to be transmitted by means of shorter messages, leading to a reduced communication time and improved scheduling results. With an example data set we show that, depending on the parameters of the compression algorithm, more than one third of the bits (34.3%) in the data communication can be saved while only on about 0.2% of all data values a slight loss of accuracy occurs. This means 99.8% of the data values can be correctly delivered without any loss but with a significant reduction of bandwidth demands. [ABSTRACT FROM AUTHOR]

It is shown that every tree of size n over a fixed set of σ different ranked symbols can be produced by a so called straight-line linear context-free tree grammar of size O ( n log σ ⁡ n ) , which can be used as a compressed representation of the input tree. Two algorithms for computing such tree grammar are presented: One working in logarithmic space and the other working in linear time. As a consequence, it is shown that every arithmetical formula of size n , in which only m ≤ n different variables occur, can be transformed (in linear time as well as in logspace) into an arithmetical circuit of size O ( n ⋅ log ⁡ m log ⁡ n ) and depth O ( log ⁡ n ) . This refines a classical result of Brent from 1974, according to which an arithmetical formula of size n can be transformed into a logarithmic depth circuit of size O ( n ) . [ABSTRACT FROM AUTHOR]