Open Access. Powered by Scholars. Published by Universities.®

Other Mathematics Commons™

Open Access. Powered by Scholars. Published by Universities.®

Computer Sciences

Institution
Keyword
Publication Year
Publication
Publication Type

Articles 121 - 136 of 136

Full-Text Articles in Other Mathematics

Pokémon® Cards And The Shortest Common Superstring, Mark Stamp, Austin Stamp Jan 2004

Pokémon® Cards And The Shortest Common Superstring, Mark Stamp, Austin Stamp

Faculty Publications, Computer Science

Evidence is presented that certain sequences of Pokémon cards are determined by selecting consecutive elements from a longer sequence. We then consider the problem of recovering the shortest common superstring (SCS), i.e., the shortest string that contains each of the Pokémon card sequences as a consecutive substring. The SCS problem arises in many applications, most notably in DNA sequencing.

Go to article

Algebraic Semantics For Coalgebraic Logics, Clemens Kupke, Alexander Kurz, Dirk Pattinson Jan 2004

Algebraic Semantics For Coalgebraic Logics, Clemens Kupke, Alexander Kurz, Dirk Pattinson

Engineering Faculty Articles and Research

With coalgebras usually being defined in terms of an endofunctor T on sets, this paper shows that modal logics for T-coalgebras can be naturally described as functors L on boolean algebras. Building on this idea, we study soundness, completeness and expressiveness of coalgebraic logics from the perspective of duality theory. That is, given a logic L for coalgebras of an endofunctor T, we construct an endofunctor L such that L-algebras provide a sound and complete (algebraic) semantics of the logic. We show that if L is dual to T, then soundness and completeness of the algebraic semantics immediately yield the …

Go to article

Preface, Thomas Hildebrandt, Alexander Kurz Jan 2004

Preface, Thomas Hildebrandt, Alexander Kurz

Engineering Faculty Articles and Research

No abstract provided.

Go to article

Coalgebras And Modal Expansions Of Logics, Alexander Kurz, Alessandra Palmigiano Jan 2004

Coalgebras And Modal Expansions Of Logics, Alexander Kurz, Alessandra Palmigiano

Engineering Faculty Articles and Research

In this paper we construct a setting in which the question of when a logic supports a classical modal expansion can be made precise. Given a fully selfextensional logic S, we find sufficient conditions under which the Vietoris endofunctor V on S-referential algebras can be defined and we propose to define the modal expansions of S as the logic that arises from the V-coalgebras. As an example, we also show how the Vietoris endofunctor on referential algebras extends the Vietoris endofunctor on Stone spaces. From another point of view, we examine when a category of ‘spaces’ (X,A), ie sets X …

Go to article

Stone Coalgebras, Clemens Kupke, Alexander Kurz, Yde Venema Jan 2003

Stone Coalgebras, Clemens Kupke, Alexander Kurz, Yde Venema

Engineering Faculty Articles and Research

In this paper we argue that the category of Stone spaces forms an interesting base category for coalgebras, in particular, if one considers the Vietoris functor as an analogue to the power set functor. We prove that the so-called descriptive general frames, which play a fundamental role in the semantics of modal logics, can be seen as Stone coalgebras in a natural way. This yields a duality between the category of modal algebras and that of coalgebras over the Vietoris functor. Building on this idea, we introduce the notion of a Vietoris polynomial functor over the category of Stone spaces. …

Go to article

Preface, Alexander Kurz Jan 2002

Preface, Alexander Kurz

Engineering Faculty Articles and Research

No abstract provided.

Go to article

Modal Predicates And Coequations, Alexander Kurz, Jiří Rosický Jan 2002

Modal Predicates And Coequations, Alexander Kurz, Jiří Rosický

Engineering Faculty Articles and Research

We show how coalgebras can be presented by operations and equations. This is a special case of Linton’s approach to algebras over a general base category X, namely where X is taken as the dual of sets. Since the resulting equations generalise coalgebraic coequations to situations without cofree coalgebras, we call them coequations. We prove a general co-Birkhoff theorem describing covarieties of coalgebras by means of coequations. We argue that the resulting coequational logic generalises modal logic.

Go to article

Definability, Canonical Models, And Compactness For Finitary Coalgebraic Modal Logic, Alexander Kurz, Dirk Pattinson Jan 2002

Definability, Canonical Models, And Compactness For Finitary Coalgebraic Modal Logic, Alexander Kurz, Dirk Pattinson

Engineering Faculty Articles and Research

This paper studies coalgebras from the perspective of the finitary observations that can be made of their behaviours. Based on the terminal sequence, notions of finitary behaviours and finitary predicates are introduced. A category Behω(T) of coalgebras with morphisms preserving finitary behaviours is defined. We then investigate definability and compactness for finitary coalgebraic modal logic, show that the final object in Behω(T) generalises the notion of a canonical model in modal logic, and study the topology induced on a coalgebra by the finitary part of the terminal sequence.

Go to article

Modal Rules Are Co-Implications, Alexander Kurz Jan 2001

Modal Rules Are Co-Implications, Alexander Kurz

Engineering Faculty Articles and Research

In [13], it was shown that modal logic for coalgebras dualises—concerning definability— equational logic for algebras. This paper establishes that, similarly, modal rules dualise implications:It is shown that a class of coalgebras is definable by modal rules iff it is closed under H (images) and Σ (disjoint unions). As a corollary the expressive power of rules of infinitary modal logic on Kripke frames is characterised.

Go to article

Rush Hour® And Dijkstra’S Algorithm, Mark Stamp, Brad Engel, Mcintosh Ewell, Victor Morrow Jan 2001

Rush Hour® And Dijkstra’S Algorithm, Mark Stamp, Brad Engel, Mcintosh Ewell, Victor Morrow

Faculty Publications, Computer Science

The game of Rush Hour® includes a 6 × 6 grid and game pieces representing cars and trucks. The object of the puzzle is to move a special car out of a gridlocked “traffic jam.” In this note we apply Dijkstra’s algorithm and a breadth-first search to solve any Rush Hour configuration.

Go to article

Notes On Coalgebras, Cofibrations And Concurrency, Alexander Kurz, Dirk Pattinson Jan 2000

Notes On Coalgebras, Cofibrations And Concurrency, Alexander Kurz, Dirk Pattinson

Engineering Faculty Articles and Research

We consider categories of coalgebras as (co)-fibred over a base category of parameters and analyse categorical constructions in the total category of deterministic and non-deterministic coalgebras.

Go to article

(Ω, Ξ)-Logic: On The Algebraic Extension Of Coalgebraic Specifications, Rolf Hennicker, Alexander Kurz Jan 1999

(Ω, Ξ)-Logic: On The Algebraic Extension Of Coalgebraic Specifications, Rolf Hennicker, Alexander Kurz

Engineering Faculty Articles and Research

We present an extension of standard coalgebraic specification techniques for statebased systems which allows us to integrate constants and n-ary operations in a smooth way and, moreover, leads to a simplification of the coalgebraic structure of the models of a specification. The framework of (Ω,Ξ)-logic can be considered as the result of a translation of concepts of observational logic (cf. [9]) into the coalgebraic world. As a particular outcome we obtain the notion of an (Ω, Ξ)- structure and a sound and complete proof system for (first-order) observational properties of specifications.

Go to article

Representations, Approximations, And Algorithms For Mathematical Speech Processing, Laura R. Suzuki Jun 1998

Representations, Approximations, And Algorithms For Mathematical Speech Processing, Laura R. Suzuki

Theses and Dissertations

Representing speech signals such that specific characteristics of speech are included is essential in many Air Force and DoD signal processing applications. A mathematical construct called a frame is presented which captures the important time-varying characteristic of speech. Roughly speaking, frames generalize the idea of an orthogonal basis in a Hilbert space, Specific spaces applicable to speech are L2(R) and the Hardy spaces Hp(D) for p> 1 where D is the unit disk in the complex plane. Results are given for representations in the Hardy spaces involving Carleson's inequalities (and its extensions), …

Go to article

Random Walks On Wheels, Matthew Lee, Mark Stamp Jan 1997

Random Walks On Wheels, Matthew Lee, Mark Stamp

Faculty Publications, Computer Science

Suppose two particles occupy distinct vertices of a wheel graph and at each step the two particles move independently to adjacent vertices. In this paper we find the expected number of moves until the particles land on the same vertex.

Go to article

Some Applications Of Sophisticated Mathematics To Randomized Computing, Ronald I. Greenberg Aug 1996

Some Applications Of Sophisticated Mathematics To Randomized Computing, Ronald I. Greenberg

Computer Science: Faculty Publications and Other Works

No abstract provided.

Go to article

Shadow Casting Phenomena At Newgrange, Frank Prendergast Jan 1991

Shadow Casting Phenomena At Newgrange, Frank Prendergast

Articles

A digital model of the Newgrange passage tomb and surrounding ring of monoliths known as the Great Circle is used to investigate sunrise shadow casting phenomena at the monument. Diurnal variation in shadow directions and lengths are analysed for their potential use in the Bronze Age to indicate the passage of seasonal time. Computer-aided simulations are developed from a photogrammetric survey to accurately show how three of the largest monoliths, located closest to the tomb entrance and archaeologically coded GC1, GC-1 and GC-2, cast their shadows onto the vertical face of the entrance kerbstone, coded K1. The phenomena occur at …

Go to article

First Prev