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

Theory and Algorithms Commons

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

1,172 Full-Text Articles 1,495 Authors 259,866 Downloads 103 Institutions

All Articles in Theory and Algorithms

Faceted Search

1,172 full-text articles. Page 1 of 40.

Smt-Based Constraint Answer Set Solver Ezsmt+ For Non-Tight Programs, Da Shen, Yuliya Lierler 2018 University of Nebraska at Omaha

Smt-Based Constraint Answer Set Solver Ezsmt+ For Non-Tight Programs, Da Shen, Yuliya Lierler

Yuliya Lierler

Constraint answer set programming integrates answer set programming with constraint processing. System Ezsmt+ is a constraint answer set programming tool that utilizes satisfiability modulo theory solvers for search. The truly unique feature of ezsmt+ is its capability to process linear as well as nonlinear constraints simultaneously containing integer and real variables.


Colenda @ The University Of Pennsylvania: Using A Decoupled, Pluggable Architecture For Object Processing, Kate Lynch 2018 University of Pennsylvania

Colenda @ The University Of Pennsylvania: Using A Decoupled, Pluggable Architecture For Object Processing, Kate Lynch

Scholarship at Penn Libraries

This poster details the architecture of the repository and the deliverables of the first major release of Colenda, the open-source repository software developed at Penn Libraries. Staff in Digital Library Development & Systems created Colenda, a long-term preservation ecosystem including Samvera, an open-source software framework for repository development, at its core. Colenda is a Samvera instance that provides materials-agnostic fuThis poster details the architecture of the repository and the deliverables of the first major release of Colenda, the open-source repository software developed at Penn Libraries. Staff in Digital Library Development & Systems created Colenda, a long-term preservation ecosystem including Samvera, an open-source ...


Rationality And Efficient Verifiable Computation, Matteo Campanelli 2018 The Graduate Center, City University of New York

Rationality And Efficient Verifiable Computation, Matteo Campanelli

All Dissertations, Theses, and Capstone Projects

In this thesis, we study protocols for delegating computation in a model where one of the parties is rational. In our model, a delegator outsources the computation of a function f on input x to a worker, who receives a (possibly monetary) reward. Our goal is to design very efficient delegation schemes where a worker is economically incentivized to provide the correct result f(x). In this work we strive for not relying on cryptographic assumptions, in particular our results do not require the existence of one-way functions.

We provide several results within the framework of rational proofs introduced by ...


High Performance Sparse Multivariate Polynomials: Fundamental Data Structures And Algorithms, Alex Brandt 2018 The University of Western Ontario

High Performance Sparse Multivariate Polynomials: Fundamental Data Structures And Algorithms, Alex Brandt

Electronic Thesis and Dissertation Repository

Polynomials may be represented sparsely in an effort to conserve memory usage and provide a succinct and natural representation. Moreover, polynomials which are themselves sparse – have very few non-zero terms – will have wasted memory and computation time if represented, and operated on, densely. This waste is exacerbated as the number of variables increases. We provide practical implementations of sparse multivariate data structures focused on data locality and cache complexity. We look to develop high-performance algorithms and implementations of fundamental polynomial operations, using these sparse data structures, such as arithmetic (addition, subtraction, multiplication, and division) and interpolation. We revisit a sparse ...


Expected Length Of The Longest Chain In Linear Hashing, Pongthip Srivarangkul, Hemanta K. Maji 2018 PurdueUniversity

Expected Length Of The Longest Chain In Linear Hashing, Pongthip Srivarangkul, Hemanta K. Maji

The Summer Undergraduate Research Fellowship (SURF) Symposium

Hash table with chaining is a data structure that chains objects with identical hash values together with an entry or a memory address. It works by calculating a hash value from an input then placing the input in the hash table entry. When we place two inputs in the same entry, they chain together in a linear linked list. We are interested in the expected length of the longest chain in linear hashing and methods to reduce the length because the worst-case look-up time is directly proportional to it.

The linear hash function used to calculate hash value is defined ...


A Divide-And-Conquer Approach To Syntax-Guided Synthesis, Peiyuan Shen, Xiaokang Qiu 2018 Purdue University

A Divide-And-Conquer Approach To Syntax-Guided Synthesis, Peiyuan Shen, Xiaokang Qiu

The Summer Undergraduate Research Fellowship (SURF) Symposium

Program synthesis aims to generate programs automatically from user-provided specifications. One critical research thrust is called Syntax-Guideds Synthesis. In addition to semantic specifications, the user should also provide a syntactic template of the desired program, which helps the synthesizer reduce the search space. The traditional symbolic approaches, such as CounterExample-Guided Inductive Synthesis (CEGIS) framework, does not scale to large search spaces. The goal of this project is to explore a compositional, divide-n-conquer approach that heuristically divides the synthesis task into subtasks and solves them separately. The idea is to decompose the function to be synthesized by creating a set of ...


Data Center Application Security: Lateral Movement Detection Of Malware Using Behavioral Models, Harinder Pal Singh Bhasin, Elizabeth Ramsdell, Albert Alva, Rajiv Sreedhar, Medha Bhadkamkar 2018 Southen Methodist University, Dallas, Texas

Data Center Application Security: Lateral Movement Detection Of Malware Using Behavioral Models, Harinder Pal Singh Bhasin, Elizabeth Ramsdell, Albert Alva, Rajiv Sreedhar, Medha Bhadkamkar

SMU Data Science Review

Data center security traditionally is implemented at the external network access points, i.e., the perimeter of the data center network, and focuses on preventing malicious software from entering the data center. However, these defenses do not cover all possible entry points for malicious software, and they are not 100% effective at preventing infiltration through the connection points. Therefore, security is required within the data center to detect malicious software activity including its lateral movement within the data center. In this paper, we present a machine learning-based network traffic analysis approach to detect the lateral movement of malicious software within ...


Supervised Machine Learning Bot Detection Techniques To Identify Social Twitter Bots, Phillip George Efthimion, Scott Payne, Nicholas Proferes 2018 Southern Methodist University

Supervised Machine Learning Bot Detection Techniques To Identify Social Twitter Bots, Phillip George Efthimion, Scott Payne, Nicholas Proferes

SMU Data Science Review

In this paper, we present novel bot detection algorithms to identify Twitter bot accounts and to determine their prevalence in current online discourse. On social media, bots are ubiquitous. Bot accounts are problematic because they can manipulate information, spread misinformation, and promote unverified information, which can adversely affect public opinion on various topics, such as product sales and political campaigns. Detecting bot activity is complex because many bots are actively trying to avoid detection. We present a novel, complex machine learning algorithm utilizing a range of features including: length of user names, reposting rate, temporal patterns, sentiment expression, followers-to-friends ratio ...


Machine Learning To Predict College Course Success, Anthony R.Y. Dalton, Justin Beer, Sriharshasai Kommanapalli, James S. Lanich Ph.D. 2018 Southern Methodist University

Machine Learning To Predict College Course Success, Anthony R.Y. Dalton, Justin Beer, Sriharshasai Kommanapalli, James S. Lanich Ph.D.

SMU Data Science Review

In this paper, we present an analysis of the predictive ability of machine learning on the success of students in college courses in a California Community College. The California Legislature passed assembly bill 705 in order to place students in non-remedial coursework, based on high school transcripts, to increase college completion. We utilize machine learning methods on de-identified student high school transcript data to create predictive algorithms on whether or not the student will be successful in college-level English and Mathematics coursework. To satisfy the bill’s requirements, we first use exploratory data analysis on applicable transcript variables. Then we ...


Second-Order Know-How Strategies, Pavel Naumov, Jia Tao 2018 Lafayette College

Second-Order Know-How Strategies, Pavel Naumov, Jia Tao

Faculty Research and Reports

The fact that a coalition has a strategy does not mean that the coalition knows what the strategy is. If the coalition knows the strategy, then such a strategy is called a know-how strategy of the coalition. The paper proposes the notion of a second-order know-how strategy for the case when one coalition knows what the strategy of another coalition is. The main technical result is a sound and complete logical system describing the interplay between the distributed knowledge modality and the second-order coalition know-how modality.


Smt-Based Answer Set Solver Cmodels-Diff (System Description), Da Shen, Yuliya Lierler 2018 University of Nebraska at Omaha

Smt-Based Answer Set Solver Cmodels-Diff (System Description), Da Shen, Yuliya Lierler

Yuliya Lierler

Many answer set solvers utilize Satisfiability solvers for search. SMT solvers extend Satisfiability solvers. This paper presents the CMODELS-DIFF system that uses SMT solvers to find answer sets of a logic program. Its theoretical foundation is based on Niemala's characterization of answer sets of a logic program via so called level rankings. The comparative experimental analysis demonstrates that CMODELS-DIFF is a viable answer set solver.


Temporal And Spatiotemporal Investigation Of Tourist Attraction Visit Sentiment On Twitter, Jose J. Padilla, Hamdi Kavak, Christopher J. Lynch, Ross J. Gore, Saikou Y. Diallo 2018 Old Dominion University

Temporal And Spatiotemporal Investigation Of Tourist Attraction Visit Sentiment On Twitter, Jose J. Padilla, Hamdi Kavak, Christopher J. Lynch, Ross J. Gore, Saikou Y. Diallo

VMASC Publications

In this paper, we propose a sentiment-based approach to investigate the temporal and spatiotemporal effects on tourists' emotions when visiting a city's tourist destinations. Our approach consists of four steps: data collection and preprocessing from social media; visitor origin identification; visit sentiment identification; and temporal and spatiotemporal analysis. The temporal and spatiotemporal dimensions include day of the year, season of the year, day of the week, location sentiment progression, enjoyment measure, and multi-location sentiment progression. We apply this approach to the city of Chicago using over eight million tweets. Results show that seasonal weather, as well as special days ...


Finding Spanning Trees In Strongly Connected Graphs With Per-Vertex Degree Constraints, Samuel Benjamin Chase 2018 California Polytechnic State University

Finding Spanning Trees In Strongly Connected Graphs With Per-Vertex Degree Constraints, Samuel Benjamin Chase

Computer Science

No abstract provided.


Iterated Local Search Algorithms For Bike Route Generation, Aidan Pieper 2018 Union College

Iterated Local Search Algorithms For Bike Route Generation, Aidan Pieper

Honors Theses

Planning routes for recreational cyclists is challenging because they prefer longer more scenic routes, not the shortest one. This problem can be modeled as an instance of the Arc Orienteering Problem (AOP), a known NP-Hard optimization problem. Because no known algorithms exist to solve this optimization problem efficiently, we solve the AOP using heuristic algorithms which trade accuracy for speed. We implement and evaluate two different Iterated Local Search (ILS) heuristic algorithms using an open source routing engine called GraphHopper and the OpenStreetMap data set. We propose ILS variants which our experimental results show can produce better routes at the ...


Funqual: User-Defined, Statically-Checked Call Graph Constraints In C++, Andrew P. Nelson 2018 Cal Poly, SLO

Funqual: User-Defined, Statically-Checked Call Graph Constraints In C++, Andrew P. Nelson

Master's Theses and Project Reports

Static analysis tools can aid programmers by reporting potential programming mistakes prior to the execution of a program. Funqual is a static analysis tool that reads C++17 code ``in the wild'' and checks that the function call graph follows a set of rules which can be defined by the user. This sort of analysis can help the programmer to avoid errors such as accidentally calling blocking functions in time-sensitive contexts or accidentally allocating memory in heap-sensitive environments. To accomplish this, we create a type system whereby functions can be given user-defined type qualifiers and where users can define their ...


Word Blending And Other Formal Models Of Bio-Operations, Zihao Wang 2018 The University of Western Ontario

Word Blending And Other Formal Models Of Bio-Operations, Zihao Wang

Electronic Thesis and Dissertation Repository

As part of ongoing efforts to view biological processes as computations, several formal models of DNA-based processes have been proposed and studied in the formal language literature. In this thesis, we survey some classical formal language word and language operations, as well as several bio-operations, and we propose a new operation inspired by a DNA recombination lab protocol known as Cross-pairing Polymerase Chain Reaction, or XPCR. More precisely, we define and study a word operation called word blending which models a special case of XPCR, where two words x w p and q w y sharing a non-empty overlap part ...


Applications Of Artificial Intelligence In Power Systems, Samin Rastgoufard 2018 srastgou

Applications Of Artificial Intelligence In Power Systems, Samin Rastgoufard

University of New Orleans Theses and Dissertations

Artificial intelligence tools, which are fast, robust and adaptive can overcome the drawbacks of traditional solutions for several power systems problems. In this work, applications of AI techniques have been studied for solving two important problems in power systems.

The first problem is static security evaluation (SSE). The objective of SSE is to identify the contingencies in planning and operations of power systems. Numerical conventional solutions are time-consuming, computationally expensive, and are not suitable for online applications. SSE may be considered as a binary-classification, multi-classification or regression problem. In this work, multi-support vector machine is combined with several evolutionary computation ...


Minimization Techniques For Symbolic Automata, Jonathan Homburg 2018 University of Connecticut

Minimization Techniques For Symbolic Automata, Jonathan Homburg

Honors Scholar Theses

Symbolic finite automata (SFAs) are generalizations of classical finite state automata. Whereas the transitions of classical automata are labeled by characters from some alphabet, the transitions of symbolic automata are labeled by predicates over a Boolean algebra defined on the alphabet. This allows for SFAs to be efficiently constructed over extremely large, and possibly infinite, alphabets. This thesis examines an existing incremental algorithm for the minimization of deterministic finite automata. Several extensions of this algorithm to de- terministic symbolic automata are introduced. Although more efficient algorithms already exist for deterministic SFA minimization, the presented algorithms are uniquely designed to minimize ...


Computational Complexity Of Determining The Rigidity Of Ftam Assemblies, Ian Perkins 2018 University of Arkansas, Fayetteville

Computational Complexity Of Determining The Rigidity Of Ftam Assemblies, Ian Perkins

Computer Science and Computer Engineering Undergraduate Honors Theses

In this paper, we discuss a tile-based self-assembly model called the Folding Tile Assembly Model (FTAM). We briefly define what makes the FTAM unique in its ability to have folding 2D tiles. We also discuss the difficulty of determining the computational complexity of certain FTAM properties despite it being simpler for less dynamic models. Specifically, we discuss the property of rigidity in FTAM assemblies by devising a simple definition of rigidity, so that it is easier to determine its complexity. We use a reduction between an assembly and a 3SAT instance along with a series of proofs to give a ...


Tamscript - High Level Programming Interface For The Abstract Tile Assembly Model, Perry Mills 2018 University of Arkansas, Fayetteville

Tamscript - High Level Programming Interface For The Abstract Tile Assembly Model, Perry Mills

Computer Science and Computer Engineering Undergraduate Honors Theses

This paper describes a programming interface, TAMScript, for use with the PyTAS simulator. The interface allows for the dynamic generation of tile types as the simulation progresses, with the goal of reducing complexity for researchers. This paper begins with an introduction to the PyTAS software and a description of the 3D model which it simulates. Next, the changes made to support a dynamic generation scheme are detailed, and some of the potential benefits of this scheme are outlined. Then several of the example scripts which have been written using the TAMScript interface are reviewed. Finally, the potential for future research ...


Digital Commons powered by bepress