More Like this

1. Extensions of two constructions of Ahmad

   https://doi.org/10.3233/COM-210380  

   Goh, Jun Le; Lempp, Steffen; Ng, Keng Meng; Soskova, Mariya I. (December 2022, Computability)

   Brattka, Vasco; Greenberg, Noam; Kalimullin, Iskander; Soskova, Mariya (Ed.)

   In her 1990 thesis, Ahmad showed that there is a so-called “Ahmad pair”, i.e., there are incomparable Σ 2 0 -enumeration degrees  a 0 and  a 1 such that every enumeration degree x < a 0 is ⩽ a 1 . At the same time, she also showed that there is no “symmetric Ahmad pair”, i.e., there are no incomparable Σ 2 0 -enumeration degrees  a 0 and  a 1 such that every enumeration degree x 0 < a 0 is ⩽ a 1 and such that every enumeration degree x 1 < a 1 is ⩽ a 0 . In this paper, we first present a direct proof of Ahmad’s second result. We then show that her first result cannot be extended to an “Ahmad triple”, i.e., there are no Σ 2 0 -enumeration degrees  a 0 , a 1 and  a 2 such that both ( a 0 , a 1 ) and ( a 1 , a 2 ) are an Ahmad pair. On the other hand, there is a “weak Ahmad triple”, i.e., there are pairwise incomparable Σ 2 0 -enumeration degrees  a 0 , a 1 and  a 2 such that every enumeration degree x < a 0 is also ⩽ a 1 or ⩽ a 2 ; however neither ( a 0 , a 1 ) nor ( a 0 , a 2 ) is an Ahmad pair. 

   more » « less
2. Strategy Graphs for Influence Diagrams

   https://doi.org/10.1613/jair.1.13865  

   Hansen, Eric A.; Shi, Jinchuan; Kastrantas, James (September 2022, Journal of Artificial Intelligence Research)

   An influence diagram is a graphical model of a Bayesian decision problem that is solved by finding a strategy that maximizes expected utility. When an influence diagram is solved by variable elimination or a related dynamic programming algorithm, it is traditional to represent a strategy as a sequence of policies, one for each decision variable, where a policy maps the relevant history for a decision to an action. We propose an alternative representation of a strategy as a graph, called a strategy graph, and show how to modify a variable elimination algorithm so that it constructs a strategy graph. We consider both a classic variable elimination algorithm for influence diagrams and a recent extension of this algorithm that has more relaxed constraints on elimination order that allow improved performance. We consider the advantages of representing a strategy as a graph and, in particular, how to simplify a strategy graph so that it is easier to interpret and analyze. 

   more » « less
3. Polygons with Prescribed Angles in 2D and 3D

   Efrat, A; Fulek, R; Kobourov, S; Toth, C (October 2020, 28th International Symposium on Graph Drawing and Network Visualization (GD))

   We consider the construction of a polygon P with n vertices whose turning angles at the vertices are given by a sequence A = (α0 , . . . , αn−1 ), αi ∈ (−π,π), for i ∈ {0,...,n − 1}. The problem of realizing A by a polygon can be seen as that of constructing a straight-line drawing of a graph with prescribed angles at vertices, and hence, it is a special case of the well studied problem of constructing an angle graph. In 2D, we characterize sequences A for which every generic polygon P ⊂ R2 realizing A has at least c crossings, and describe an efficient algorithm that constructs, for a given sequence A, a generic polygon P ⊂ R2 that realizes A with the minimum number of crossings. In 3D, we describe an efficient algorithm that tests whether a given sequence A can be realized by a (not necessarily generic) polygon P ⊂ R3, and for every realizable sequence finds a realization. 

   more » « less
4. Polygons with Prescribed Angles in 2D and 3D

   https://doi.org/10.1007/978-3-030-68766-3_11  

   Efrat, Alon; Fulek, Radoslav; Kobourov, Stephen; Toth, Csaba D. (February 2021, Graph Drawing and Network Visualization)

   null (Ed.)

   We consider the construction of a polygon P with n vertices whose turning angles at the vertices are given by a sequence A=(α0,…,αn−1) , αi∈(−π,π) , for i∈{0,…,n−1} . The problem of realizing A by a polygon can be seen as that of constructing a straight-line drawing of a graph with prescribed angles at vertices, and hence, it is a special case of the well studied problem of constructing an angle graph. In 2D, we characterize sequences A for which every generic polygon P⊂R2 realizing A has at least c crossings, for every c∈N , and describe an efficient algorithm that constructs, for a given sequence A, a generic polygon P⊂R2 that realizes A with the minimum number of crossings. In 3D, we describe an efficient algorithm that tests whether a given sequence A can be realized by a (not necessarily generic) polygon P⊂R3 , and for every realizable sequence the algorithm finds a realization. 

   more » « less
5. Verification and convergence study of a spectral-element numerical methodology for fluid-structure interaction

   https://doi.org/doi.org/10.1016/j.jcpx.2021.100084  

   Xu, YiQin; Peet, Yulia T (March 2021, Journal of computational physics)

   A high-order in space spectral-element methodology for the solution of a strongly coupled fluid-structure interaction (FSI) problem is developed. A methodology is based on a partitioned solution of incompressible fluid equations on body-fitted grids, and nonlinearly-elastic solid deformation equations coupled via a fixed-point iteration approach with Aitken relaxation. A comprehensive verification strategy of the developed methodology is presented, including h-, p-and temporal refinement studies. An expected order of convergence is demonstrated first separately for the corresponding fluid and solid solvers, followed by a self-convergence study on a coupled FSI problem (self-convergence refers to a convergence to a reference solution obtained with the same solver at higher resolution). To this end, a new three-dimensional fluid-structure interaction benchmark is proposed for a verification of the FSI codes, which consists of a fluid flow in a channel with one rigid and one flexible wall. It is shown that, due to a consistent problem formulation, including initial and boundary conditions, a high-order spatial convergence on a fully coupled FSI problem can be demonstrated. Finally, a developed framework is applied successfully to a Direct Numerical Simulation of a turbulent flow in a channel interacting with a compliant wall, where the fluid-structure interface is fully resolved. 

   more » « less