View Communities

Technical Reports (Computing Science)

Technical Reports Collection
Number of results to display per page
Items in this Collection
  1. Measuring the Size of Large No-Limit Poker Games [Download]

    Title: Measuring the Size of Large No-Limit 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 "no-limit" variants. In this paper, we describe a simple algorithm for quickly computing the size of two-player no-limit 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 no-limit poker games played in the Annual Computer Poker Competition.
    Subjects: Artificial Intelligence, poker, game theory
    Date Created: Feb 26, 2013
  2. Support for Document Entry in a Multimedia Database [Download]

    Title: Support for Document Entry in a Multimedia Database
    Creator: El-Medani, Sherine
    Description: Technical report TR96-23. 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 meta-information about the document structure. A generic meta type system was designed to model such meta-information. This type system consists of a number of built-in 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
  3. A Generic Type System for an Object-Oriented Multimedia Database System [Download]

    Title: A Generic Type System for an Object-Oriented Multimedia Database System
    Creator: Schone, Manuela
    Description: Technical report TR96-14. 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 object-oriented 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 built-in 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
  4. Characterization of Solutions to block triangular Hankel Systems [Download]

    Title: Characterization of Solutions to block triangular Hankel Systems
    Creator: Kossowski, P.
    Description: Technical report TR95-06. A full characterization of solutions is given for a certain class of under-determined 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
  5. Well-covered graphs: some new sub-classes and complexity results [Download]

    Title: Well-covered graphs: some new sub-classes and complexity results
    Creator: Sankaranarayana, Ramesh
    Description: Technical report TR94-02. 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. Well-covered graphs are of interest because while the problem of finding the size of a maximum independent set is NP-complete for graphs in general, it is in P for well-covered graphs. Many of the existing results in this area deal with characterizations of families of well-covered 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 well-covered 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 fill-in, recognition, Steiner tree, and vertex cover. While most of the above problems prove to be as difficult for well-covered 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 well-covered graphs. This leads to the concept of a maximal intersection of independent sets. Based on this, a hierarchy of four new sub-classes of well-covered 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, Well-covered graphs, new sub-classes, characterization
    Date Created: 1994
  6. Mutable Object State for Object-Oriented Logic Programming: A Survey [Download]

    Title: Mutable Object State for Object-Oriented Logic Programming: A Survey
    Creator: Alexiev, Vladimir
    Description: Technical report TR93-15. One of the most difficult problems on the way to an integration of Object-Oriented 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 state-of-the-art 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: Object-Oriented Logic Programming, survey, mutable object state
    Date Created: 1993
  7. Classifying Newgroup Questions on JTree and JButton [Download]

    Title: Classifying Newgroup Questions on JTree and JButton
    Creator: Hou, Daqing
    Description: Technical report TR05-07. In this study, we collected and analyzed 190 and 110 questions about JTree and JButton, respectively, from the Swing forum at 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
  8. Automatic Estimation of 3D Transformations using Skeletons for Object Alignment [Download]

    Title: Automatic Estimation of 3D Transformations using Skeletons for Object Alignment
    Creator: Wang, Tao
    Description: Technical report TR05-32. An algorithm for automatic estimation of 3D transformations between two objects is presented in this paper. Skeletons of the 3D objects are created with a fully parallel thinning algorithm and feature point pairs (land markers) are extracted from skeletons automatically, and least squares method is applied to solve an over-determined linear system to estimate the 3D transformation. Experiments show that this method works quite well with high accuracy when the translations and rotation angles are small, even when there is some noise. The estimation process requires about 900 ms on an Intel Centrino Laptop with 512 MB memory, for a complex model with about 37,000 object points and 500 object points for its skeletons.
    Subjects: Computer Vision and Multimedia Communications
    Date Created: 2005
  9. Aggregation Convergecast Scheduling in Wireless Sensor Networks [Download]

    Title: Aggregation Convergecast Scheduling in Wireless Sensor Networks
    Creator: Malhotra, Baljeet
    Description: Technical report TR09-14. We consider the problem of aggregation convergecast scheduling in wireless sensor networks. Aggregation convergecast differs from regular convergecast in that it accommodates transmission dependencies that allow in-network aggregation to be performed. We formulate the abstract problem of aggregation convergecast and review the existing literature. We observe that existing schemes adopt essentially a two phase approach, consisting of, first, a tree construction and, second, a scheduling phase. Following a similar approach, we propose two new improvements, one to each of the two phases. Starting with a new lower bound on the schedule length, we make use of it in the tree construction step. The tree construction step consists of solutions to instances of bipartite graph semi-matching. The scheduling step is a weight-based priority scheme that obeys dependency (tree) and interference constraints. The combination of both improvements is demonstrated to outperform all existing solutions in the literature. We also study the impact of each of the two improvements alone and pay attention to cases where the tree construction is obviated due to the existence of extrinsic dependency constraints.
    Subjects: Database Systems
    Date Created: 2009
  10. Modeling Time: Back to Basics [Download]

    Title: Modeling Time: Back to Basics
    Creator: Goralwalla, Iqbal
    Description: Technical report TR96-03. Most of the work in modeling time in information systems has concentrated on issues such as support for historical information and providing query facilities to manipulate such information. In doing so, some simplistic view of the underling nature of time has been assumed. However, the domain of time is far from being simplistic. In this paper, we outline the various issues which arise in modeling basic temporal entities and propose solutions to these issues. More specifically, we note that the nature of temporal information can either be anchored (e.g., October 25, 1995) or unanchored (e.g., week), and is usually available in multiple granularities (e.g., the airline flight departure and arrival times are usually given in minutes, while the history of the salary of an employee is usually recorded in days). Physical temporal information also needs to be represented in a manner so as to be human readable. This is achieved using calenders. In this work, we show how both anchored and unanchored temporal entities are represented within the context of calenders. We discuss how calenders provide relationships between multiple granularities and facilitate the conversion of anchored and unanchored times from one granularity to another. We also give the semantics of various operations on anchored and unanchored times.
    Subjects: temporal databases, granularity, calenders, object models
    Date Created: 1996