View Communities
Technical Reports (Computing Science)
Technical Reports Collection
Items in this Collection

Measuring the Size of Large NoLimit Poker Games [Download]
Title: Measuring the Size of Large NoLimit Poker Games Creator: Johanson, Michael Description: In the field of computational game theory, games are often compared in terms of their size. This can be measured in several ways, including the number of unique game states, the number of decision points, and the total number of legal actions over all decision points. These numbers are either known or estimated for a wide range of classic games such as chess and checkers. In the stochastic and imperfect information game of poker, these sizes are easily computed in "limit" games which restrict the players' available actions, but until now had only been estimated for the more complicated "nolimit" variants. In this paper, we describe a simple algorithm for quickly computing the size of twoplayer nolimit poker games, provide an implementation of this algorithm, and present for the first time precise counts of the number of game states, information sets, actions and terminal nodes in the nolimit poker games played in the Annual Computer Poker Competition. Subjects: Artificial Intelligence, poker, game theory Date Created: Feb 26, 2013 
Support for Document Entry in a Multimedia Database [Download]
Title: Support for Document Entry in a Multimedia Database Creator: ElMedani, Sherine Description: Technical report TR9623. This Technical Report describes a document entry system that supports the automatic insertion of documents with arbitrary types into a multimedia database. The documents conform to the international standards of SGML and HyTime. This is achieved by instantiating objects in the database to represent the document components. These are persistent objects that can be queried and retrieved using a query interface. To achieve this goal, the database has to be queried dynamically to retrieve metainformation about the document structure. A generic meta type system was designed to model such metainformation. This type system consists of a number of builtin types that model the characteristics common to SGML document components. Whenever support for a new class of documents is added to the system, meta types modeling the characteristics specific to this class are dynamically generated and added to the meta type system. To insert documents conforming to this class into the database, two system components were developed: the SGML Parser and the Instance Generator. The SGML Parser validates the SGML documents to ensure database consistency. The Instance Generator instantiates the appropriate database objects to represent the document. Subjects: Multimedia databases, SGML Parser, Instance Generator, document entry system, dynamic querying Date Created: 1996 
A Generic Type System for an ObjectOriented Multimedia Database System [Download]
Title: A Generic Type System for an ObjectOriented Multimedia Database System Creator: Schone, Manuela Description: Technical report TR9614. This Technical Report is based upon an M.Sc. thesis in the Department of Computing Science at the University of Alberta. It describes the design of a generic multimedia database system that supports a wide class of documents. The design is characterized by an objectoriented approach and a strict adherence to the international standards SGML and HyTime. In order to support different multimedia applications, a multimedia type system must be flexible and extensible. This is achieved by defining a number of builtin types that model primitive multimedia objects, the spatial and temporal relationships between them, and characteristics that are common to all SGML documents and their components. Whenever support for a new class of documents is added to the multimedia database system, types modeling the characteristics specific to this class of documents are dynamically created and added to the type system. These types model the components and structure of the new document class. Subjects: Database Systems Date Created: 1996 
Characterization of Solutions to block triangular Hankel Systems [Download]
Title: Characterization of Solutions to block triangular Hankel Systems Creator: Kossowski, P. Description: Technical report TR9506. A full characterization of solutions is given for a certain class of underdetermined triangular block Hankel systems of linear equations. Solutions of these systems correspond to Pade' approximants for bivariate power series with coefficients from a field. Subjects: bivariate Pade' aprroximants, block Hankel matrices Date Created: 1995 
Wellcovered graphs: some new subclasses and complexity results [Download]
Title: Wellcovered graphs: some new subclasses and complexity results Creator: Sankaranarayana, Ramesh Description: Technical report TR9402. A graph is said to be well covered if every maximal independent set has the same size, and very well covered if every maximal independent set contains exactly half the vertices in the graph. Wellcovered graphs are of interest because while the problem of finding the size of a maximum independent set is NPcomplete for graphs in general, it is in P for wellcovered graphs. Many of the existing results in this area deal with characterizations of families of wellcovered graphs. This thesis focuses on the algorithmic properties of this family. The first part of this thesis looks at the algorithmic complexities of the following problems for the families of wellcovered and very well covered graphs: chromatic number, clique cover, clique partition, dominating cycle, dominating set, Hamiltonian cycle, Hamiltonian path, independent set, independent dominating set, maximum cut, minimum fillin, recognition, Steiner tree, and vertex cover. While most of the above problems prove to be as difficult for wellcovered graphs as for graphs in general, a number of them become tractable when restricted to the family of very well covered graphs. In the second part of this thesis, an alternative characterization is given for the family of wellcovered graphs. This leads to the concept of a maximal intersection of independent sets. Based on this, a hierarchy of four new subclasses of wellcovered graphs is defined. The families are characterized and the algorithmic complexities of the above mentioned problems are studied for these families. It is also shown that the last class in the hierarchy is exactly the family of very well covered graphs without isolated vertices. A generalization of Favaron's theorem for very well covered graphs is also proved. Subjects: very well covered graphs, complexity results, Wellcovered graphs, new subclasses, characterization Date Created: 1994 
Mutable Object State for ObjectOriented Logic Programming: A Survey [Download]
Title: Mutable Object State for ObjectOriented Logic Programming: A Survey Creator: Alexiev, Vladimir Description: Technical report TR9315. One of the most difficult problems on the way to an integration of ObjectOriented and Logic Programming is the modeling of changeable object state(i.e. object dynamics) in a particular logic in order not to forfeit the declarative nature of LP. Classical logic is largely unsuitable for such a task, because it adopts a general (both temporally and spatially), Platonic notion of validity, whereas object state changes over time and is local to an object. This paper presents the problem and surveys the stateoftheart approaches to its solution, as well as some emerging, promising new approaches. The paper tries to relate the different approaches, to evaluate their merits and deficiencies and to identify promising directions for development. The emphasis in this survey is on efficient implementation of state change, one which would be suitable for the lowest fundamental level of a general OOLP language. The following approaches are covered: Assert/Retract, Declarative Database Updates and Transaction Logic, Modal and Dynamic Logics, Perpetual Objects, Logical Objects and Linear Objects, Linear Logic, Rewriting Logic and MaudeLog. Subjects: ObjectOriented Logic Programming, survey, mutable object state Date Created: 1993 
Classifying Newgroup Questions on JTree and JButton [Download]
Title: Classifying Newgroup Questions on JTree and JButton Creator: Hou, Daqing Description: Technical report TR0507. In this study, we collected and analyzed 190 and 110 questions about JTree and JButton, respectively, from the Swing forum at forum.java.sun.com. We classified these questions by the design features of these two components. This classification leads to a better understanding why certain features are particularly difficult and the identification of problems with documentation. Subjects: Jtree, Jbutton, software development Date Created: 2005 
On the Comparison Cost of Partial Orders [Download]
Title: On the Comparison Cost of Partial Orders Creator: Culberson, Joseph Description: Technical report TR8801. A great deal of effort has been directed towards determining the minimum number of binary comparisons sufficient to produce various partial orders given some partial order. For example, the sorting problem considers the minimum number of comparisons sufficient to construct a total order starting from n elements. The merging problem considers the minimum number of comparisons sufficient to construct a total order from two total orders. The searching problem can be seen as a special case of the merging problem in which one of the total orders is a singleton. The selection problem considers the minimum number of comparisons sufficient to select the ith largest of n elements. Little, however, is known about the minimum number of comparisons sufficient to produce an arbitrary partial order. In this paper we briefly survey the known results on this problem and we present some first results on partial orders which can be produced using either restricted types of comparisons or a limited number of comparisons. Subjects: comparison based algorithms, lower bounds, poset, sorting, partial order Date Created: 1988 
Downward Path Preserving State Space Abstractions [Download]
Title: Downward Path Preserving State Space Abstractions Creator: Zilles, Sandra Description: Technical report TR0904. Abstraction is a popular technique for speeding up planning and search. A problem that often arises in using abstraction is the generation of abstract states, called spurious states, from which the goal state is reachable in the abstract space but for which there is no corresponding state in the original space from which the goal state can be reached. The experiments in this paper demonstrate that this problem may arise even when standard abstraction methodsare applied to benchmark planning problem domains: spurious states cause the pattern databases representing the heuristics to be excessively large and slow down planning and search by reducing the heuristic values. Known automated techniques to get rid of a large portion of spurious states turn out to avoid the memory problem, while at the same time not avoiding the problem of bad heuristic quality. The main contribution of this paper is theoretical. We formally define a characteristic property  the downward path preserving property (DPP)  that guarantees an abstraction will not contain spurious states. How this property can be achieved is studied both for techniques focussing on automated domainindependent abstraction and for techniques focussing on domainspecific abstraction. We analyze the computational complexity of (i) testing the downward path preserving property for a given state space and abstraction and of (ii) determining whether this property is achievable at all for a given state space. Strong hardness results show a close connection between these decision problems and the plan existence problem in typical planning settings including SAS+ and propositional STRIPS. On the positive side, we identify formal conditions under which finding downward path preserving abstractions is provably tractable and show that some popular heuristic search and planning domains have an encoding that matches these conditions. This includes a new encoding of the Blocks World domain, for which DPP abstractions can be easily defined. Subjects: downward path preserving property, abstraction, spurious states Date Created: 2009 
Using SIMD Registers and Instructions to Enable InstructionLevel Parallelism in Sorting Algorithms [Download]
Title: Using SIMD Registers and Instructions to Enable InstructionLevel Parallelism in Sorting Algorithms Creator: Furtak, Timothy Description: Technical report TR0702. Most contemporary processors offer some version of Single Instruction Multiple Data (SIMD) machinery  vector registers and instructions to manipulate data stored in such registers. The central idea of this paper is to use these SIMD resources to improve the performance of the tail of recursive sorting algorithms. When a recursive computation reaches a set threshold, data is loaded into the vector registers, manipulated inregister, and the result stored back to memory. Four implementations of sorting with two different SIMD machinery  x8664's SSE2 and G5's AltiVec  demonstrate that this idea delivers significant performance improvement. The improvements provided by the tail optimization of sorting are orthogonal to the gains obtained through empirical search for a suitable sorting algorithm. When integrated with the Dynamically Tuned Sorting Library (DTSL), this new code generation strategy improves the performance of DTSL by up to 18%. Performance of dheaps is similarly improved by up to 35%. Subjects: Sorting networks, Vectorization, Sorting, Instructionlevel parallelism, Quicksort, dHeaps, SIMD, SSE Date Created: 2007