A Uniform Paradigm to Succinctly Encode Various Families of Trees

We propose a uniform method to encode various types of trees succinctly. These families include ordered (ordinal), k-ary (cardinal), and unordered (free) trees. We will show the approach is intrinsically suitable for obtaining entropy-based encodings of trees (such as the degree-distribution entropy). Previously-existing succinct encodings of trees use ad hoc techniques to encode each particular family of trees. Additionally, the succinct encodings obtained using the uniform approach improve upon the existing succinct encodings of each family of trees; in the case of ordered trees, it simplifies the encoding while supporting the full set of navigational operations. It also simplifies the implementation of many supported operations. The approach applied to k-ary trees yields a succinct encoding that supports both cardinal-type operations (e.g. determining the child label i) as well as the full set of ordinal-type operations (e.g. reporting the number of siblings to the left of a node). Previous work on succinct encodings of k-ary trees does not support both types of operations simultaneously (Benoit et al. in Algorithmica 43(4):275–292, 2005; Raman et al. in ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 233–242, 2002). For unordered trees, the approach achieves the first succinct encoding. The approach is based on two recursive decompositions of trees into subtrees. Recursive decomposition of a structure into substructures is a common technique in succinct encodings and has even been used to encode (ordered) trees (Geary et al. in ACM Trans. Algorithms 2(4):510–534, 2006; He et al. in ICALP, pp. 509–520, 2007) and dynamic binary trees (Munro et al. in ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 529–536, 2001; Storm in Representing dynamic binary trees succinctly, Master’s thesis, 2000). The main distinction of the approach in this paper is that a tree is decomposed into subtrees in a manner that the subtrees are maximally isolated from each other. This intermediate decomposition result is interesting in its own right and has proved useful in other applications (Farzan et al. in ICALP (1), pp. 451–462, 2009; Farzan and Munro in ICALP (1), pp. 439–450, 2009; Farzan and Kamali in ICALP, 2011).     

Explicit and Efficient Hash Families Suffice for Cuckoo Hashing with a Stash

It is shown that for cuckoo hashing with a stash as proposed by Kirsch et al. (Proc. 16th European Symposium on Algorithms (ESA), pp. 611–622, Springer, Berlin, 2008) families of very simple hash functions can be used, maintaining the favorable performance guarantees: with constant stash size s the probability of a rehash is O(1/n ^s+1), the lookup time and the deletion time are O(s) in the worst case, and the amortized expected insertion time is O(s) as well. Instead of the full randomness needed for the analysis of Kirsch et al. and of Kutzelnigg (Discrete Math. Theor. Comput. Sci., 12(3):81–102, 2010) (resp. Θ(logn)-wise independence for standard cuckoo hashing) the new approach even works with 2-wise independent hash families as building blocks. Both construction and analysis build upon the work of Dietzfelbinger and Woelfel (Proc. 35th ACM Symp. on Theory of Computing (STOC), pp. 629–638, 2003). The analysis, which can also be applied to the fully random case, utilizes a graph counting argument and is much simpler than previous proofs. The results can be generalized to situations where the stash size is non-constant.     

Fast Phylogeny Reconstruction Through Learning of Ancestral Sequences

Given natural limitations on the length DNA sequences, designing phylogenetic reconstruction methods which are reliable under limited information is a crucial endeavor. There have been two approaches to this problem: reconstructing partial but reliable information about the tree (Mossel in IEEE Comput. Biol. Bioinform. 4:108–116, 2007; Daskalakis et al. in SIAM J. Discrete Math. 25:872–893, 2011; Daskalakis et al. in Proc. of RECOMB 2006, pp. 281–295, 2006; Gronau et al. in Proc. of the 19th Annual SODA 2008, pp. 379–388, 2008), and reaching “deeper” in the tree through reconstruction of ancestral sequences. In the latter category, Daskalakis et al. (Proc. of the 38th Annual STOC, pp. 159–168, 2006) settled an important conjecture of M. Steel (My favourite conjecture. Preprint, 2001), showing that, under the CFN model of evolution, all trees on n leaves with edge lengths bounded by the Ising model phase transition can be recovered with high probability from genomes of length O(logn) with a polynomial time algorithm. Their methods had a running time of O(n ¹⁰). Here we enhance our methods from Daskalakis et al. (Proc. of RECOMB 2006, pp. 281–295, 2006) with the learning of ancestral sequences and provide an algorithm for reconstructing a sub-forest of the tree which is reliable given available data, without requiring a-priori known bounds on the edge lengths of the tree. Our methods are based on an intuitive minimum spanning tree approach and run in O(n ³) time. For the case of full reconstruction of trees with edges under the phase transition, we maintain the same asymptotic sequence length requirements as in Daskalakis et al. (Proc. of the 38th Annual STOC, pp. 159–168, 2006), despite the considerably faster running time.     

2-Transitivity is Insufficient for Local Testability

A basic goal in property testing is to identify a minimal set of features that make a property testable. For the case when the property to be tested is membership in a binary linear error-correcting code, Alon et al. (Trans Inf Theory, 51(11):4032–4039, 2005) had conjectured that the presence of a single low-weight codeword in the dual, and “2-transitivity” of the code (i.e., the code being invariant under a 2-transitive group of permutations on the coordinates of the code) suffice to get local testability. We refute this conjecture by giving a family of error-correcting codes where the coordinates of the codewords form a large field of characteristic two, and the code is invariant under affine transformations of the domain. This class of properties was introduced by Kaufman & Sudan (STOC, 2008) as a setting where many results in algebraic property testing generalize. Our result shows a complementary virtue: This family also can be useful in producing counterexamples to natural conjectures.     

Queaps

A new priority queue structure, the queap, is introduced. The queap executes insertion in O(1) amortized time and extract-min in O(log (k+2)) amortized time if there are k items that have been in the heap longer than the item to be extracted. Thus if the operations on the queap are first-in first-out, as on a queue, each operation will execute in constant time. This idea of trying to make operations on the least recently accessed items fast, which we call the queueish property, is a natural complement to the working set property of certain data structures, such as splay trees and pairing heaps, where operations on the most recently accessed data execute quickly. However, we show that the queueish property is in some sense more difficult than the working set property by demonstrating that it is impossible to create a queueish binary search tree, but that many search data structures can be made almost queueish with a O(log logn) amortized extra cost per operation.     

A unified framework for evaluating test criteria in model-checking-assisted test case generation

Testing is often cited as one of the most costly operations in testing dependable systems (Heimdahl et al. 2001). A particular challenging task in testing is test-case generation. To improve the efficiency of test-case generation and reduce its cost, recently automated formal verification techniques such as model checking are extended to automate test-case generation processes. In model-checking-assisted test-case generation, a test criterion is formulated as temporal logical formulae, which are used by a model checker to generate test cases satisfying the test criterion. Traditional test criteria such as branch coverage criterion and newer temporal-logic-inspired criteria such as property coverage criteria (Tan et al. 2004) are used with model-checking-assisted test generation. Two key questions in model-checking-assisted test generation are how efficiently a model checker may generate test suites for these criteria and how effective these test suites are. To answer these questions, we developed a unified framework for evaluating (1) the effectiveness of the test criteria used with model-checking-assisted test-case generation and (2) the efficiency of test-case generation for these criteria. The benefits of this work are three-fold: first, the computational study carried out in this work provides some measurements of the effectiveness and efficiency of various test criteria used with model-checking-assisted test case generation. These performance measurements are important factors to consider when a practitioner selects appropriate test criteria for an application of model-checking-assisted test generation. Second, we propose a unified test generation framework based on generalized Büchi automata. The framework uses the same model checker, in this case, SPIN model checker (Holzmann 1997), to generate test cases for different criteria and compare them on a consistent basis. Last but not least, we describe in great details the methodology and automated test generation environment that we developed on the basis of our unified framework. Such details would be of interest to researchers and practitioners who want to use and extend this unified framework and its accompanying tools.     

A Comparison of Iterated Optimal Stopping and Local Policy Iteration for American Options Under Regime Switching

A theoretical analysis tool, iterated optimal stopping, has been used as the basis of a numerical algorithm for American options under regime switching (Le and Wang in SIAM J Control Optim 48(8):5193–5213, 2010). Similar methods have also been proposed for American options under jump diffusion (Bayraktar and Xing in Math Methods Oper Res 70:505–525, 2009) and Asian options under jump diffusion (Bayraktar and Xing in Math Fin 21(1):117–143, 2011). An alternative method, local policy iteration, has been suggested in Huang et al. (SIAM J Sci Comput 33(5):2144–2168, 2011), and Salmi and Toivanen (Appl Numer Math 61:821–831, 2011). Worst case upper bounds on the convergence rates of these two methods suggest that local policy iteration should be preferred over iterated optimal stopping (Huang et al. in SIAM J Sci Comput 33(5):2144–2168, 2011). In this article, numerical tests are presented which indicate that the observed performance of these two methods is consistent with the worst case upper bounds. In addition, while these two methods seem quite different, we show that either one can be converted into the other by a simple rearrangement of two loops.     

On anonymizing transactions with sensitive items

K-anonymity (Samarati and Sweeny 1998; Samarati, IEEE Trans Knowl Data Eng, 13(6):1010–1027, 2001; Sweeny, Int J Uncertain, Fuzziness Knowl-Based Syst, 10(5):557–570, 2002) and its variants, l-diversity (Machanavajjhala et al., ACM TKDD, 2007) and tcloseness (Li et al. 2007) among others are anonymization techniques for relational data and transaction data, which are used to protect privacy against re-identification attacks. A relational dataset D is k-anonymous if every record in D has at least k-1 other records with identical quasi-identifier attribute values. The combination of released data with external data will never allow the recipient to associate each released record with less than k individuals (Samarati, IEEE Trans Knowl Data Eng, 13(6):1010–1027, 2001). However, the current concept of k-anonymity on transaction data treats all items as quasi-identifiers. The anonymized data set has k identical transactions in groups and suffers from lower data utility (He and Naughton 2009; He et al. 2011; Liu and Wang 2010; Terrovitis et al., VLDB J, 20(1):83–106, 2011; Terrovitis et al. 2008). To improve the utility of anonymized transaction data, this work proposes a novel anonymity concept on transaction data that contain both quasi-identifier items (QID) and sensitive items (SI). A transaction that contains sensitive items must have at least k-1 other identical transactions (Ghinita et al. IEEE TKDE, 33(2):161–174, 2011; Xu et al. 2008). For a transaction that does not contain a sensitive item, no anonymization is required. A transaction dataset that satisfies this property is said to be sensitive k-anonymous. Three algorithms, Sensitive Transaction Neighbors (STN) Gray Sort Clustering (GSC) and Nearest Neighbors for K-anonymization (K-NN), are developed. These algorithms use adding/deleting QID items and only adding SI to achieve sensitive k-anonymity on transaction data. Additionally, a simple “privacy value” is proposed to evaluate the degree of privacy for different types of k-anonymity on transaction data. Extensive numerical simulations were carried out to demonstrate the characteristics of the proposed algorithms and also compared to other types of k-anonymity approaches. The results show that each technique possesses its own advantage under different criteria such as running time, operation, and information loss. The results obtained here can be used as a guideline of the selection of anonymization technique on different data sets and for different applications.     

A Self-stabilizing Algorithm for the Median Problem in?Partial Rectangular Grids and Their Relatives

Given a graph G=(V,E), a vertex v of G is a median vertex if it minimizes the sum of the distances to all other vertices of G. The median problem consists of finding the set of all median vertices of G. In this note, we present self-stabilizing algorithms for the median problem in partial rectangular grids and relatives. Our algorithms are based on the fact that partial rectangular grids can be isometrically embedded into the Cartesian product of two trees, to which we apply the algorithm proposed by Antonoiu and Srimani (J. Comput. Syst. Sci. 58:215–221, 1999) and Bruell et al. (SIAM J. Comput. 29:600–614, 1999) for computing the medians in trees. Then we extend our approach from partial rectangular grids to a more general class of plane quadrangulations. We also show that the characterization of medians of trees given by Gerstel and Zaks (Networks 24:23–29, 1994) extends to cube-free median graphs, a class of graphs which includes these quadrangulations.     

Some notes on the abstraction operation for multi-terminal binary decision diagrams

The starting point of this work are inaccurate statements found in the literature for Multi-terminal Binary Decision Diagrams (MTBDDs) (Bahar et al., Form. Methods Syst. Des. 10(2/3):171–206, 1997; Siegle, Behaviour analysis of communication systems: compositional modelling, compact representation and analysis of performability properties, 2002; Kuntz, Symbolic semantics and verification of stochastic process algebras, 2006) regarding the well-definedness of the MTBDD abstraction operation. The statements try to relate an operation ? on a set of terminal values M to the property that the abstraction over this operation does depend on the order of the abstracted variables. This paper gives a necessary and sufficient condition for the independence of the abstraction operation of the order of the abstracted variables in the case of an underlying monoid and it treats the more general setting of a magma.     

Algebraic flux correction for nonconforming finite element discretizations of scalar transport problems

This paper is concerned with the extension of the algebraic flux-correction (AFC) approach (Kuzmin in Computational fluid and solid mechanics, Elsevier, Amsterdam, pp 887–888, 2001; J Comput Phys 219:513–531, 2006; Comput Appl Math 218:79–87, 2008; J Comput Phys 228:2517–2534, 2009; Flux-corrected transport: principles, algorithms, and applications, 2nd edn. Springer, Berlin, pp 145–192, 2012; J Comput Appl Math 236:2317–2337, 2012; Kuzmin et al. in Comput Methods Appl Mech Eng 193:4915–4946, 2004; Int J Numer Methods Fluids 42:265–295, 2003; Kuzmin and Möller in Flux-corrected transport: principles, algorithms, and applications. Springer, Berlin, 2005; Kuzmin and Turek in J Comput Phys 175:525–558, 2002; J Comput Phys 198:131–158, 2004) to nonconforming finite element methods for the linear transport equation. Accurate nonoscillatory approximations to convection-dominated flows are obtained by stabilizing the continuous Galerkin method by solution-dependent artificial diffusion. Its magnitude is controlled by a flux limiter. This concept dates back to flux-corrected transport schemes. The unique feature of AFC is that all information is extracted from the system matrices which are manipulated to satisfy certain mathematical constraints. AFC schemes have been devised with conforming $P_1$ and $Q_1$ finite elements in mind but this is not a prerequisite. Here, we consider their extension to the nonconforming Crouzeix–Raviart element (Crouzeix and Raviart in RAIRO R3 7:33–76, 1973) on triangular meshes and its quadrilateral counterpart, the class of rotated bilinear Rannacher–Turek elements (Rannacher and Turek in Numer Methods PDEs 8:97–111, 1992). The underlying design principles of AFC schemes are shown to hold for (some variant of) both elements. However, numerical tests for a purely convective flow and a convection–diffusion problem demonstrate that flux-corrected solutions are overdiffusive for the Crouzeix–Raviart element. Good resolution of smooth and discontinuous profiles is attested to $Q_1^\mathrm{nc}$ approximations on quadrilateral meshes. A synthetic benchmark is used to quantify the artificial diffusion present in conforming and nonconforming high-resolution schemes of AFC-type. Finally, the implementation of efficient sparse matrix–vector multiplications is addressed.     

Multi-player epistemic games: Guiding the enactment of classroom knowledge-building communities

Teachers and students face many challenges in shifting from traditional classroom cultures to enacting the Knowledge-Building Communities model (KBC model) supported by the CSCL environment, Knowledge Forum (Bereiter, 2002; Bereiter & Scardamalia, 1993; Scardamalia, 2002; Scardamalia & Bereiter, 2006). Enacting the model involves socializing students into knowledge work, similar to disciplinary communities. A useful construct in the field of the Learning Sciences for understanding knowledge work is “epistemic games” (Collins & Ferguson, 1993; Morrison & Collins 1995; Perkins, 1997). We propose that a powerful means for supporting classroom enactments of the KBC model entails conceptualizing Knowledge Forum as a collective space for playing multi-player epistemic games. Participation in knowledge-building communities is then scaffolded through learning the moves of such games. We have designed scaffolding tools that highlight particular knowledge-building moves for practice and reflection as a means of supporting students and teachers in coming to understand how to collectively work together toward the progressive improvement of ideas. In order to examine our design theories in practice, we present research on Ideas First, a design-based research program involving enactments of the KBC model in Singaporean primary science classrooms (Bielaczyc & Ow, 2007, 2010; Ow & Bielaczyc, 2007; 2008).     

Comments and further improvements on “pth moment stability of stochastic neural networks with Markov volatilities”

In a very recent paper, Peng and Liu (Neural Comput Appl 20:543–547, 2011) investigated the pth moment stability of the stochastic Grossberg–Hopfield neural networks with Markov volatilities by Mao et al. (Bernoulli 6:73–90, 2000, Theorem 4.1). We should point out that Mao et al. (Bernoulli 6:73–90, 2000, Theorem 4.1) investigated the pth moment exponentially stable for a class of stochastic dynamical systems with constant delay; however, this theorem cannot apply to the case of variable time delays. It is also worthy to emphasize that Peng and Liu (Neural Comput Appl 20:543–547, 2011) discussed by Mao et al. (Bernoulli 6:73–90, 2000, Theorem 4.1) the pth moment exponentially stable for the Grossberg–Hopfield neural networks with variable delays, and therefore, there are some gaps between Peng and Liu (Neural Comput Appl 20:543–547, 2011, Theorem 1) and Mao et al. (Bernoulli 6:73–90, 2000, Theorem 4.1). In this paper, we fill up this gap. Moreover, a numerical example is also provided to demonstrate the effectiveness and applicability of the theoretical results.     

Consistency properties and set based logic programming

Blair et al. (2001) developed an extension of logic programming called set based logic programming. In the theory of set based logic programming the atoms represent subsets of a fixed universe X and one is allowed to compose the one-step consequence operator with a monotonic idempotent operator O so as to ensure that the analogue of stable models in the theory are always closed under O. Marek et al. (1992, Ann Pure Appl Logic 96:231–276 1999) developed a generalization of Reiter’s normal default theories that can be applied to both default theories and logic programs which is based on an underlying consistency property. In this paper, we show how to extend the normal logic programming paradigm of Marek, Nerode, and Remmel to set based logic programming. We also show how one can obtain a new semantics for set based logic programming based on a consistency property.     

Min-domain retroactive ordering for Asynchronous Backtracking

Ordering heuristics are a powerful tool in CSP search algorithms. Among the most successful ordering heuristics are heuristics which enforce a fail first strategy by using the Min-domain property (Haralick and Elliott, Artif Intel 14:263–313, 1980; Bessiere and Regin, Mac and combined heuristics: two reasons to forsake FC (and CBJ?) on hard problems. In Proc. CP 96, pp. 61–75, Cambridge, MA, 1996; Smith and Grant, Trying harder to fail first. In European Conference on Artificial Intelligence, pp. 249–253, 1998; Dechter, Constraint Processing. Morgan Kaufman, 2003). Ordering heuristics have been introduced recently to asynchronous backtracking (ABT), for distributed constraints satisfaction (DisCSP) (Zivan and Meisels, Dynamic ordering for asynchronous backtracking on discsps. In CP-2005, pp. 32–46, Sigtes (Barcelona), Spain, 2005). However, the pioneering study of dynamically ordered ABT, ABT_DO, has shown that a straightforward implementation of the Min-domain heuristic does not produce the expected improvement over a static ordering. The present paper proposes an asynchronous dynamic ordering which does not follow the standard restrictions on the position of reordered agents in ABT_DO. Agents can be moved to a position that is higher than that of the target of the backtrack. Combining the Nogood-triggered heuristic and the Min-domain property in this new class of heuristics results in the best performing version of ABT_DO. The new version of retroactively ordered ABT is faster by a large factor than the best form of ABT.     

The stable topology for residuated lattices

The spectrum of a residuated lattice L is the set Spec(L) of all prime i-filters. It is well known that Spec(L) can be endowed with the spectral topology. The main scope of this paper is to introduce and study another topology on Spec(L),?the so called stable topology, which turns out to be coarser than the spectral one. With this and in view, we introduce the notions of pure i-filter for a residuated lattice and the notion of normal residuated lattice. So, we generalize to case of residuated lattice some results relative to MV-algebras (Belluce and Sessa in Quaest Math 23:269–277, 2000; Cavaccini et?al. in Math Japonica 45(2):303–310, 1997) or BL-algebras (Eslami and Haghani in Kybernetika 45:491–506, 2009; Leustean in Central Eur J Math 1(3): 382–397, 2003; Turunen and Sessa in Mult-Valued Log 6(1–2):229–249, 2001).     

The Duo-Item Bisection Auction

This paper proposes an iterative sealed-bid auction for selling multiple heterogeneous items to bidders interested in buying at most one item. It generalizes the single item bisection auction (Grigorieva et al. Econ Theory, 30:107–118, 2007) to the environment with multiple heterogeneous items. We focus on the case with two items for sale. We show that the auction elicits a minimal amount of information on preferences required to find the Vickrey–Clark–Groves outcome (Clarke, Public Choice, XI:17–33, 1971; Groves, Econometrica, 61:617–631, 1973; Vickrey, J Finance, 16:8–37, 1961), when there are two items for sale and an arbitrary number of bidders.     

Functional un|unparsing

Danvy??s functional unparsing problem (Danvy in J. Funct. Program. 8(6), 621?C625, 1998) is to implement a type-safe ??printf?? function, which converts a sequence of heterogeneous arguments to a string according to a given format. The dual problem is to implement a type-safe ??scanf?? function, which extracts a sequence of heterogeneous arguments from a string by interpreting (Friedman and Wand in LFP, pp. 348?C355, 1984 and in Essentials of Programming Languages, MIT Press, 2008) the same format as an equally heterogeneous sequence of patterns that binds zero or more variables. We derive multiple solutions to both problems (Wand in J. ACM 27(1), 164?C180, 1980) from their formal specifications (Wand in Theor. Comput. Sci. 20(1), 3?C32, 1982). On one hand, our solutions show how the Hindley-Milner type system, unextended, permits accessing heterogeneous sequences with the static assurance of type safety. On the other hand, our solutions demonstrate the use of control operators (Felleisen et al. in Proceedings of the 1988 ACM Conference on Lisp and Functional Programming, pp. 52?C62, ACM Press, New York, 1988; Wand in POPL 85: Conference Record of the Annual ACM Symposium on Principles of Programming Languages, vol. 16, ACM Press, New York, 1985; Meyer and Wand in Logics of Programs, Lecture Notes in Computer Science, vol. 193, pp. 219?C224, Springer, Berlin, 1985) to communicate with formats as coroutines (Wand in Proceedings of the 1980 ACM Conference on Lisp and Functional Programming, vol. 12, pp. 285?C299, ACM Press, New York, 1980 and Haynes et al. in LFP, pp. 293?C298, 1984).     

An optimal arc consistency algorithm for a particular case of sequence constraint

The AtMostSeqCard constraint is the conjunction of a cardinality constraint on a sequence of n variables and of n???q?+?1 constraints AtMost u on each subsequence of size q. This constraint is useful in car-sequencing and crew-rostering problems. In van Hoeve et al. (Constraints 14(2):273–292, 2009), two algorithms designed for the AmongSeq constraint were adapted to this constraint with an O(2 ^q n) and O(n ³) worst case time complexity, respectively. In Maher et al. (2008), another algorithm similarly adaptable to filter the AtMostSeqCard constraint with a time complexity of O(n ²) was proposed. In this paper, we introduce an algorithm for achieving arc consistency on the AtMostSeqCard constraint with an O(n) (hence optimal) worst case time complexity. Next, we show that this algorithm can be easily modified to achieve arc consistency on some extensions of this constraint. In particular, the conjunction of a set of m AtMostSeqCard constraints sharing the same scope can be filtered in O(nm). We then empirically study the efficiency of our propagator on instances of the car-sequencing and crew-rostering problems.