text:
// shmembench.cpp -- benchmark test for a bridged shared memory process
//    based on shmemserver.cpp and o2client.cpp
//
// Roger B. Dannenberg
// Jan 2022

/*
This test:
- initialize o2lite
- send/recv messages from O2 main thread to shared memory thread
*/

// o2usleep.h goes first to set _XOPEN_SOURCE to define usleep:
#include <stdlib.h>
#include "o2internal.h"
#include "pathtree.h"
#ifdef WIN32
#include <windows.h>
#include <mmsystem.h>
#else
#include <pthread.h>
pthread_t pt_thread_pid;
#endif
#include "sharedmem.h"

Bridge_info *smbridge = NULL;

int max_msg_count = 1000;
int n_addrs = 20;
bool client_running = true;
bool server_running = true;
int client_msg_count = 0;
int server_msg_count = 0;
char **client_addresses = NULL;
char **server_addresses = NULL;
/* with amortize, messages are sent in groups of 10, and server
   responds only to messages where the count is a multiple of 10
   (first count is 1). Response also contains 10 messages, from
   count-9 to count-0. The client side does the same up until the
   total message count reaches or passes client_msg_count.
 */
int amortize = false;

bool about_equal(double a, double b)
{
    return a / b > 0.999999 && a / b < 1.000001;
}

void client_test(O2msg_data_ptr data, const char *types,
                 O2arg_ptr *argv, int argc, const void *user_data)
{
    client_msg_count++;
    // the value we send is arbitrary, but we've already sent
    // 1 message with value 1, so the 2nd message will have 2, etc...
    int32_t i = client_msg_count + 1;

    // server will shut down when it gets data == -1
    if (client_msg_count >= max_msg_count) {
        i = -1;
        client_running = false;
    }
    if (amortize) {
        if (client_msg_count % 10 == 0) {
            for (int i = 0; i < 10; i++) {
                int count = client_msg_count + i - 10;
                o2_send_cmd(server_addresses[count % n_addrs], 0, "i", count);
            }
        }
    } else {
        o2_send_cmd(server_addresses[client_msg_count % n_addrs], 0, "i", i);
    }
    assert(client_msg_count == argv[0]->i32);
}

void *sharedmem();

int main(int argc, const char * argv[])
{
    o2_memory(malloc, free, NULL, 0, false);
    printf("Usage: shmembench [maxmsgs] [debugflags]\n");
    if (argc >= 2) {
        max_msg_count = atoi(argv[1]);
        printf("max_msg_count set to %d\n", max_msg_count);
        if (strchr(argv[1], 'a')) {
            amortize = true;
            printf("Found 'a'mortize: sending messages in groups of 10 to\n");
            printf("    amortize scheduling and polling costs.\n");
        }
    }
    if (argc >= 3) {
        o2_debug_flags(argv[2]);
        printf("debug flags are: %s\n", argv[2]);
    }
    if (argc > 3) {
        printf("WARNING: shmembench ignoring extra command line argments\n");
    }
    o2_initialize("test");

    // create the client service in the main thread here
    o2_service_new("client");

    // create methods for receiving messages here in the client service
    for (int i = 0; i < n_addrs; i++) {
        char path[100];
        sprintf(path, "/client/benchmark/%d", i);
        o2_method_new(path, "i", &client_test, NULL, false, true);
    }

    // create destination addresses in the server (shared mem thread)
    server_addresses = O2_MALLOCNT(n_addrs, char *);
    for (int i = 0; i < n_addrs; i++) {
        char path[100];
        sprintf(path, "!server/benchmark/%d", i);
        server_addresses[i] = O2_MALLOCNT(strlen(path) + 1, char);
        strcpy(server_addresses[i], path);
    }

    // create the server (shared memory thread)
    int res = o2_shmem_initialize();
    assert(res == O2_SUCCESS);

    smbridge = o2_shmem_inst_new();

    sharedmem(); // start and run the thread

    // we are the master clock
    o2_clock_set(NULL, NULL);

    // wait for the server to appear
    while (o2_status("server") < O2_REMOTE) {
        o2_poll();
        o2_sleep(2); // 2ms
    }
    printf("We discovered the server.\ntime is %g.\n", o2_time_get());

    double now = o2_time_get();
    while (o2_time_get() < now + 1) {
        o2_poll();
        o2_sleep(2);
    }

    printf("Here we go! ...\ntime is %g.\n", o2_time_get());
    o2_send_cmd("!server/benchmark/0", 0, "i", 1);
    if (amortize) {
        for (int i = 0; i < 9; i++) { // 9 more
            o2_send_cmd("!server/benchmark/0", 0, "i", 1 + i);
        }
    }

    while (client_running) {  // full speed busy wait
        o2_poll();
    }

    printf("** shmembench main ended run loop **\n");
    // wait 0.1s for thread to finish
    now = o2_time_get();
    while (o2_time_get() < now + 0.1) {
        o2_poll();
        o2_sleep(2); // 2ms
    }
    printf("*** shmembench main called o2_poll() for 0.1s after\n"
           "    shared mem process finished; calling o2_finish...\n");

    o2_finish();
}

/**************************** O2SM PROCESS **************************/
// switch to o2sm environment
#include "sharedmemclient.h"

// this is a handler for incoming messages. It simply sends a message
// back to one of the client addresses
//
void server_test(O2msg_data_ptr msg, const char *types,
                 O2arg_ptr *argv, int argc, const void *user_data)
{
    assert(argc == 1);
    o2_extract_start(msg);
    O2arg_ptr i_arg = o2_get_next(O2_INT32);
    assert(i_arg);
    int got_i = i_arg->i;

    server_msg_count++;
    if (got_i == -1) {
        server_running = false;
    } else {
        assert(server_msg_count == got_i);
        if (amortize) {
            if (server_msg_count % 10 == 0) {
                for (int i = 0; i < 10; i++) {
                    int count = server_msg_count + i - 10;
                    o2sm_send_cmd(client_addresses[count  % n_addrs], 0, "i", count);
                }
            }
        } else {
            o2sm_send_cmd(client_addresses[server_msg_count % n_addrs], 0, "i",
                          server_msg_count);
        }
    }
}

bool sift_called = false;

// handles types "sift"
void sift_han(O2msg_data_ptr msg, const char *types,
              O2arg_ptr *argv, int argc, const void *user_data)
{
    O2arg_ptr as, ai, af, at;
    o2_extract_start(msg);
    if (!(as = o2sm_get_next(O2_STRING)) || !(ai = o2sm_get_next(O2_INT32)) ||
        !(af = o2sm_get_next(O2_FLOAT)) || !(at = o2sm_get_next(O2_TIME))) {
        printf("sift_han problem getting parameters from message");
        assert(false);
    }
    printf("sift_han called\n");
    assert(user_data == (void *) 111);
    assert(streql(as->s, "this is a test"));
    assert(ai->i == 1234);
    assert(about_equal(af->f, 123.4));
    assert(about_equal(at->t, 567.89));
    sift_called = true;
}

O2_context o2sm_ctx;

void sharedmem_init()
{
    o2sm_initialize(&o2sm_ctx, smbridge);
    o2sm_service_new("sift", NULL);

    o2sm_method_new("/sift", "sift", &sift_han, (void *)111, false, false);

    printf("shmemthread detected connected\n");

    o2_send_start();
    o2_add_string("this is a test");
    o2_add_int32(1234);
    o2_add_float(123.4F);
    o2_add_time(567.89);
    o2sm_send_finish(0, "/sift", true);
    printf("sent sift msg\n");
}

static int phase = 0;
static O2time start_wait;

// perform whatever the thread does. Return false when done.
bool o2sm_act()
{
    o2sm_poll();
    if (phase == 0) {
        if (o2sm_time_get() < 0) { // not synchronized
            return true;
        } else {
            printf("shmemthread detected clock sync\n");
            start_wait = o2sm_time_get();
            phase++;
        }
    }
    if (phase == 1) {
        if (start_wait + 1 > o2sm_time_get() && !sift_called) {
            return true;
        } else {
            assert(sift_called);
            printf("shmemthread received loop-back message\n");
            // we are ready for the client, so announce the server services
            o2sm_service_new("server", NULL);
            // now create addresses and handlers to receive server messages
            client_addresses = O2_MALLOCNT(n_addrs, char *);
            server_addresses = O2_MALLOCNT(n_addrs, char *);
            for (int i = 0; i < n_addrs; i++) {
                char path[100];

                sprintf(path, "!client/benchmark/%d", i);
                client_addresses[i] = O2_MALLOCNT(strlen(path) + 1, char);
                strcpy(client_addresses[i], path);

                sprintf(path, "/server/benchmark/%d", i);
                server_addresses[i] = O2_MALLOCNT(strlen(path) + 1, char);
                strcpy(server_addresses[i], path);
                o2sm_method_new(path, "i", &server_test, NULL, false, true);
            }
            phase++;
        }
    }
    if (phase == 2) {
        if (server_running) {
            return true;
        } else {
            for (int i = 0; i < n_addrs; i++) {
                O2_FREE(client_addresses[i]);
                O2_FREE(server_addresses[i]);
            }
            O2_FREE(client_addresses);
            O2_FREE(server_addresses);

            o2sm_finish();

            printf("shmembench:\nSERVER DONE\n");
            phase++;
            return false;
        }
    }
    return true; // should never get here
}

#ifdef WIN32
bool shmem_initialized = false;

void CALLBACK o2sm_run_callback(UINT timer_id, UINT msg, DWORD_PTR data,
                                DWORD_PTR dw1, DWORD_PTR dw2)
{
    if (!shmem_initialized) {
        sharedmem_init();
        shmem_initialized = true;
    }
    if (!o2sm_act()) {
        timeKillEvent(timer_id);
    }
}

void *sharedmem()
{
    timeSetEvent(1, 0, &o2sm_run_callback, NULL, TIME_PERIODIC);
    return NULL;
}
#else
void *sharedmem_action(void *ignore)
{
    sharedmem_init();
    while (o2sm_act()) {
        ; // poll as fast as possible -- it's a benchmark
    }
    return NULL;
}

void *sharedmem()
{
    int res = pthread_create(&pt_thread_pid, NULL, &sharedmem_action, NULL);
    if (res != 0) {
        printf("ERROR: pthread_create failed\n");
    }
    return NULL;
}
#endif


text:
from testbase import TestBase
from influxparawrite import InfluxParaWrite

class test_212(TestBase):
    def run(self):
        self.env.sendSingleMetric(1,self.name,1)
        self.env.sendSingleMetric(2,self.name,2)
        self.env.sendSingleMetric(3,self.name,3)
        if self.env.countMetrics(1,self.name) != 3:
            return ["FAIL","node 1 wrong count"]
        if self.env.countMetrics(2,self.name) != 3:
            return ["FAIL","node 2 wrong count"]
        if self.env.countMetrics(3,self.name) != 3:
            return ["FAIL","node 3 wrong count"]
        self.env.partitionStart(3)
        ipw = InfluxParaWrite(self.env)
        ipw.start(1,3,'fullyPartitionNode',self.name)
        self.env.partitionStop(3)
        val = self.env.countMetrics(1,self.name)
        if val != ipw.count+3:
            return ["FAIL","node 1 wrong count 2: "+ str(val) + ' != '+str(ipw.count+3)]
        val = self.env.countMetrics(2,self.name)
        if val != ipw.count+3:
            return ["FAIL","node 2 wrong count 2: "+ str(val) + ' != '+str(ipw.count+3)]
        val = self.env.countMetrics(3,self.name)
        if val != ipw.count+3:
            return ["FAIL","node 3 wrong count 2: "+ str(val) + ' != '+str(ipw.count+3)]
        return ["PASS",""]
    def desc(self):
        return 'Partition away 3. Fire off multiple writes while partitioning the node. Remove the partition and query from that node'

redpajama_set_name: RedPajamaGithub


text:
/*
 * Created on 05.07.2005
 */
package commands;

import org.eclipse.draw2d.geometry.Rectangle;

import org.eclipse.gef.RequestConstants;
import org.eclipse.gef.commands.Command;
import org.eclipse.gef.requests.ChangeBoundsRequest;

import model.States;

/**
 * @author Daniel
 */
public class StatesSetConstraintCommand extends Command {
	/** Stores the new size and location. */
	private final Rectangle newBounds;

	/** Stores the old size and location. */
	private Rectangle oldBounds;

	/** A request to move/resize an edit part. */
	private final ChangeBoundsRequest request;

	/** State to manipulate. */
	private final States state;

	/**
	 * Create a command that can resize and/or move a state.
	 *
	 * @param state
	 *            the state to manipulate
	 * @param req
	 *            the move and resize request
	 * @param newBounds
	 *            the new size and location
	 * @throws IllegalArgumentException
	 *             if any of the parameters is null
	 */
	public StatesSetConstraintCommand(States state, ChangeBoundsRequest req,
			Rectangle newBounds) {
		if (state == null || req == null || newBounds == null) {
			throw new IllegalArgumentException();
		}
		this.state = state;
		this.request = req;
		this.newBounds = newBounds.getCopy();
		setLabel("Move / Resize");
	}

	/*
	 * (non-Javadoc)
	 *
	 * @see org.eclipse.gef.commands.Command#canExecute()
	 */
	public boolean canExecute() {
		Object type = request.getType();
		// make sure the Request is of a type we support:
		return (RequestConstants.REQ_MOVE.equals(type)
				|| RequestConstants.REQ_MOVE_CHILDREN.equals(type)
				|| RequestConstants.REQ_RESIZE.equals(type) || RequestConstants.REQ_RESIZE_CHILDREN
				.equals(type));
	}

	/*
	 * (non-Javadoc)
	 *
	 * @see org.eclipse.gef.commands.Command#execute()
	 */
	public void execute() {
		oldBounds = new Rectangle(state.getLocation(), state.getSize());
		redo();
	}

	/*
	 * (non-Javadoc)
	 *
	 * @see org.eclipse.gef.commands.Command#redo()
	 */
	public void redo() {
		state.setSize(newBounds.getSize());
		state.setLocation(newBounds.getLocation());
	}

	/*
	 * (non-Javadoc)
	 *
	 * @see org.eclipse.gef.commands.Command#undo()
	 */
	public void undo() {
		state.setSize(oldBounds.getSize());
		state.setLocation(oldBounds.getLocation());
	}
}


text:
\documentclass[10pt,a4paper,reqno]{amsart}

\usepackage[T1]{fontenc}
\usepackage{macros}
\usepackage{fullpage}
\usepackage{algorithm}
\usepackage{algpseudocode}
\usepackage{graphicx}

\usepackage{droid}
\usepackage{eulervm}

\begin{document}
\bibliographystyle{alpha}

\noindent Math 448 Fall 2011, Computer Algebra\\
\noindent Instructor: Sreekar M. Shastry\\
\noindent Solutions to the Final Examination\\
\noindent 24-Nov-2011 1430-1730, Ramanujan Hall in Sai Trinity \emph{(Happy Thanksgiving!)}

\bigskip

\begin{itemize}
    \item There are 9 problems. Each problem is worth 5 points. The maximum score is 45 points.
    \item Clearly state the results you invoke.
\end{itemize}

\bigskip

\noindent 1. (a) Write down a nondeterministic automaton which accepts the set
of strings over \(\{a,b,c\}\) such that the final letter has appeared before.

(b) Write down a regular expression which accepts the same language.

\bigskip

\emph{Solution.} (a)
    \begin{center}
        \includegraphics{resources/final-problem-1-nfa.pdf}
    \end{center}

(b) Put $r := \varepsilon + a + b + c$. Then the sought regular expression is
\[r^*ar^*a + r^*br^*b + r^*cr^*c.\]

\bigskip

\noindent 2. Show that the set of strings over \(\{0,1\}\) of the form $ww$ for some $w\in \{0,1\}^*$ is not a regular language.

\bigskip

\emph{Solution.} Write $L$ for the set in question and suppose for
contradiction that $L$ is regular. Then by the pumping lemma there exists $N >
0$ such that a given string $v = ww$ of length $> N$ may be decomposed as $v =
xyz$ with $xy^iz \in L$ for all $i \ge 0$ and $y \neq \varepsilon$ and $|xy|
\le N$. (This is the pumping lemma as stated in Hopcroft et al.) Let $$w_0 =
1\underbrace{00\cdots0}_{N}$$ be a 1 followed by $N$ zeros. Put $v_0 :=
w_0w_0$. Then $|v_0| = 2N+2 > N$ and the pumping lemma applies. For a word
$u\in \{0,1\}^*$ write $O(u) := \#\{\text{1's in } u\}$. Since $|xy| \le N <
|v_0|/2 = N+1$ it follows that $y$ can contain at most one of the 1's in $v_0$.
If $O(y) = 0$ then $xy^iz$ has the number of zeros before the middle 1 not
equal to the number of zeros after the middle one, and thus it cannot be of the
form $ww$ i.e.~cannot be in $L$. If $O(y)=1$ then for odd $i$, $xy^iz$ has an
odd number of ones and again it cannot be of the form $ww$.

\bigskip

\newcommand{\Mon}[1]{\ensuremath{\mathrm{Mon}\langle #1\rangle}}
\newcommand{\Grp}[1]{\ensuremath{\mathrm{Grp}\langle #1\rangle}}

\noindent 3. Let us recall some definitions. Let $X$ be a set and $\mathcal{R}$
be a subset of $X^*\times X^*$. We define \Mon{X|\mathcal{R}} to be the
quotient of $X^*$ modulo the congruence generated by $\mathcal{R}$. Let
$X^{\pm} := X\times \{1,-1\}$. We write $x$ or $x^1$ for $(x,1) \in X^\pm$ and
$x^{-1}$ for $(x,-1) \in X^\pm$. Put \[\mathcal{F}_X := \{(x^\alpha
x^{-\alpha}, \varepsilon) \in (X^\pm)^*\times (X^\pm)^* : x \in X, \alpha\in
\{1,-1\}\}\] and \[\Grp{X | \mathcal{S}} := \Mon{X^\pm | \mathcal{F}_X \cup
\mathcal{S}}.\] We also use the notation \(\Grp{x_1,\dots,x_s|U_1 = V_1, \dots,
U_t = V_t}\) to mean \Grp{X|\mathcal{S}} where $X = \{x_1,\dots,x_s\},
\mathcal{S} = \{(U_i,V_i)\}_{i=1}^t.$

Let $\mathbb{Z}$ be the additive group of integers and let $\mathbb{Z}/n$ be
the quotient by the subgroup $n\mathbb{Z}$.

Show that \Grp{x | x^n=1} is isomorphic to $\mathbb{Z}/n$.

\bigskip

\emph{Solution.} We define a map \(\mathbb{Z}\simeq
\{x,x^{-1}\}^*/\mathcal{F}_{\{x,x^{-1}\}}\rightarrow \mathbb{Z}/n\) by sending
$\varepsilon \mapsto 0, x\mapsto 1, x^{-1} \mapsto -1$. Here, the isomorphism
$\mathbb{Z}\simeq \{x,x^{-1}\}^*/\mathcal{F}_{\{x,x^{-1}\}}$ is just the fact
that $\{x,x^{-1}\}^*/\mathcal{F}_{\{x,x^{-1}\}}$ is the free group on one
generator, i.e.~$\mathbb{Z}$.

We now invoke the following proposition from the course notes.

\begin{prop} Let $M$ be a monoid and $Q$ be the quotient of $M$ mod the
    congruence $\sim$ generated by $S \subset M\times M$. Let $f: M \rightarrow
    N$ be a monoid homomorphism such that $f(s) = f(t)$ for all $(s,t)\in S$.
    Then there is a unique $g: Q \rightarrow N$ such that \[\xymatrix{ M
    \ar[rr]^f \ar[dr]_{x\mapsto [x]}& & N\\ & Q\ar[ur]_g } \] commutes.
\end{prop}

Thus we have a unique homomorphism of monoids $\Grp{x|x^n=1} \rightarrow
\mathbb{Z}/n$. Now we can write down a map $\mathbb{Z} \simeq
\{u,u^{-1}\}^*/\mathcal{F}_{\{u,u^{-1}\}} \rightarrow \Grp{x|x^n=1}$ by $u
\mapsto x$. Again we use the above proposition to get the monoid homomorphism
$\mathbb{Z}/n \rightarrow \Grp{x|x^n=1}$. One computes directly that the maps
are inverse (at this point, we have reduced to the intuitive proof from a first
course in group theory).

\bigskip

\noindent 4. Let $X$ be a set with at least two elements. Show that $X^*$ has
an infinite strictly increasing sequence of ideals.

\bigskip

\emph{Solution.} Recall that an ideal in a monoid $M$ is by definition a subset
$I \subset M$ such that $IM \subset I$ and $MI \subset I$. Let $a\in X$ are
distinct elements. For $n \ge 2$ put \[ I_n := \{w \in X^* : w(i) = w(j) = a
\text{ for some } 1 \le i < j \le n\}.\] One checks that the $I_n$ are ideals
and that we have \[I_2 \subsetneq I_3 \subsetneq \cdots\] as required. (Note
that if $X$ had only one element then all of the $I_n$ would coincide.)

\bigskip

\noindent 5. Draw a van Kampen diagram which shows that the group \[\langle a,b
| abab^2 = baba^2 = e\rangle\] is cyclic.

\bigskip

\emph{Solution.} In the diagram on the left, the pentagon is $abab^2=e$, the
outer boundary is $baba^2=e$ and the remaining bounded region is
$abb^{-1}b^{-1} = ab^{-1} = e$ so that $a=b$ and the group is cyclic. The
diagram on the right proceeds likewise.

    \begin{center}
        \includegraphics[scale=0.8]{resources/van-kampen-final.pdf}
    \end{center}

\bigskip

\noindent 6. Let $<$ be a reduction ordering on $X^*$ and let $\mathcal{R}$ be
a confluent rewriting system with respect to it. For a word $U\in X^*$ write
$U^\#$ for the reverse of $U$. Define $<^\#$ by $U <^\# V$ iff $U^\# < V^\#$.

(a) Show that $<^\#$ is a reduction ordering.

(b) Show that $\{(P^\#,Q^\#) : (P,Q)\in \mathcal{R}\}$ is a confluent rewriting
system with respect to $<^\#$.

\bigskip

\emph{Solution.} (a) Given $U,V$ we must show that $U <^\# V \Rightarrow AUB
<^\# AVB$ for all $A,B$. The latter holds iff $(AUB)^\# = B^\# U^\# A^\# <
(AVB)^\# = B^\# V^\# A^\#$. Now this last condition does hold since $<$ is
translation invariant and $U^\# < V^\#.$ Thus $<^\#$ is translation invariant.

To see that it is a well ordering suppose not; then there is an infinite
strictly decreasing sequence $U_1^\# > U_2^\# > \cdots$ contradicting the fact
that $<$ is a well ordering.

(b) Unwind the definitions. (Note: the students were required to write out a
detailed proof to receive full credit.)

\bigskip

\noindent 7. Let $X := \{x,y,z\}$ and consider the finite rewriting system
$$\mathcal{R} := \{(x^2, \varepsilon),\; (yz, \varepsilon),\; (zy,\varepsilon)
\}.$$ Show that $\mathcal{R}$ is confluent.

\bigskip

\emph{Solution.}

Let us first recall the idea behind the algorithm \textsc{Confluent}.

We have the following proposition from the course notes:

\begin{prop} Let $W$ be a word such that local confluence fails at $W$ but does
    not fail at any proper subword of $W$. Then one of the following holds:

    (1) $W$ appears as the left side of two distinct elements of $\mathcal{R}$.

    (2) $W$ is a left side in $\mathcal{R}$ which contains another left side as a proper subword.

    (3) $W = ABC$ where $A,B,C$ are nonempty words such that $AB$ and $BC$ are left sides in $\mathcal{R}$.
\end{prop}

\begin{defn} If $W$ is as in the proposition, then we call $W$ an \emph{overlap
    of left sides} in $\mathcal{R}$. If the third condition holds then we say
    that $W$ is a \emph{proper overlap.}
\end{defn}

Since $\mathcal{R}$ is finite, the set $\mathscr{W}$ of words which are
overlaps of left sides in $\mathcal{R}$ is also finite. For each $W\in
\mathscr{W}$, write $\mathscr{U}$ for the finite set of words $U$ such that $W
\xrightarrow{\mathcal{R}} U$ is a derivation consisting of a single step. For
each $U\in \mathscr{U}$ we put $V :=$ \textsc{Rewrite}$(X,\mathcal{R},U)$.  As
$U$ varies, if more than one $V$ is obtained, then $\mathcal{R}$ is not
confluent. The reason is that in this case we have found two words which are
irreducible with respect to $\mathcal{R}$ and define the same element of $M$.

On the other hand, if only one value of $V$ is seen as $U$ varies in
$\mathscr{U}$, then local confluence does not fail at $W$.

Performing this test for all $W\in \mathscr{W}$, we have an algorithm
\textsc{Confluent} for determining whether or not $\mathcal{R}$ is confluent.

Now, to solve the problem at hand, we must first determine $\mathscr{W}$. Cases
(1) and (2) of the proposition do not arise. For case (3): corresponding to
$(x^2, \varepsilon)$ we have $A=x, B=x, C=x$ in the notation of the
proposition, so that $W = ABC$ with $AB = BC = x^2$ a left side. If we take
$A=y, B=z, C=y$ then we have $AB=yz, BC=zy$ are left sides so that $W=ABC=yzy$
is in $\mathscr{W}$. Similarly if we take $A=z, B=y, C=z$ then $AB=zy, BC=yz$
are left sides and it follows that $W = zyz \in \mathscr{W}$. This exhausts all
possible elements of $\mathscr{W}$ since we have checked all left sides for
candidates for $AB,BC$ and $A,B,C$.

Now, $\mathscr{W} = \{x^3, yzy, zyz\}$. Fix $W\in \mathscr{W}$. We must find
the set $\mathscr{U}_W$ of words that can be obtained in one step from $W$.
Inspecting $\mathcal{R}$ we see that $$\mathscr{U}_{x^3} = \{x\},\;\;
\mathscr{U}_{yzy} = \{y\},\;\; \mathscr{U}_{zyz} = \{z\}.$$ Finally, for each
$W\in \mathscr{W}$ we see that the set $$\{
\text{\textsc{Rewrite}}(X,\mathcal{R},U) : U \in \mathscr{U}_W\}$$ is a
singleton, a fact which verifies confluence.

\bigskip

\noindent 8. Let us recall the Knuth-Bendix algorithm and the supporting subroutines, as well as the Euclidean algorithm.

\bigskip

\begin{algorithmic}[1]
    \Procedure{RewriteLeft}{$X,\mathcal{R}, U$}
    \State Input: $X$ = generators, $\mathcal{R}$ = rewriting system, $U$ = a word;
    \State Output: the rewritten form of $U$
    \State $V:= \varepsilon, W := U$;
    \While{$W \neq \varepsilon$}
    \State Let $W = xW_1$ where $x\in X$; $W:= W_1, V:= Vx;$
    \For{$i = 1,\dots,n$}
    \If{$P_i$ is a suffix of $V$}
    \State $V:= RP_i, W := Q_i W, V:= R;$
    \State break
    \EndIf
    \EndFor
    \EndWhile
    \EndProcedure
\end{algorithmic}

\bigskip

\begin{algorithmic}[1]
    \Procedure{Update}{$\mathcal{S}, U,V$}
    \State Input: $\mathcal{S} = \{(P_1,Q_1), (P_2,Q_2), \dots,(P_n,Q_n)\}$ a finite rewriting system; $U,V = $ words;
    \State Output: none; the state of $\mathcal{S}$ is modified in place;
    \State $A :=$ \textsc{RewriteLeft}$(U)$;
    \State $B :=$ \textsc{RewriteLeft}$(V)$;
    \If{$A\neq B$}
    \If{$A < B$}
    \State swap $A$ and $B$;
    \EndIf
    \State append $(A,B)$ to $\mathcal{S}$;
    \EndIf
    \EndProcedure
\end{algorithmic}

\bigskip

\begin{algorithmic}[1]
    \Procedure{Overlap}{$\mathcal{S}, i,j$}
    \State Input: $\mathcal{S} = \{(P_1,Q_1), (P_2,Q_2), \dots,(P_n,Q_n)\}$; $i,j = $ positive integers $\le |\mathcal{S}|$
    \State Output: none; the state of $\mathcal{S}$ is modified in place;
    \For{$k := 1, \dots, |P_i|$}
    \State Let $P_i = AB$ where $|B| = k$;
    \State Let $U$ be the longest word which is a prefix of both $B$ and $P_j$;
    \State Let $B = UD$ and $P_j = UE;$
    \If{$D = \varepsilon$ or $E = \varepsilon$}
    \State \textsc{Update}$(\mathcal{S}, AQ_jD, Q_iE)$;
    \EndIf
    \EndFor
    \EndProcedure
\end{algorithmic}

\bigskip

\begin{algorithmic}[1]
    \Procedure{KnuthBendix}{$X, <, \mathcal{R}$}
    \State Input:
    \State $X=$ a finite set, $<$ = reduction ordering on $X^*$, $\mathcal{R} \subset X^*\times X^*$ a finite subset;
    \State Output: $\mathcal{T} = \mathrm{RC}(X, <, \mathcal{R})$ if it is finite
    \State
    \State $\mathcal{S} := \{\};i:=1;$
    \For{$(U,V) \in \mathcal{R}$}
    \State \textsc{Update}$(\mathcal{S},U,V);$
    \EndFor
    \While{$i \le n$}
    \For{$j:=1,\dots,i$}
    \State \textsc{Overlap}$(\mathcal{S}, i,j)$;
    \If{j < i}
    \State \textsc{Overlap}$(\mathcal{S}, j,i)$;
    \EndIf
    \EndFor
    \State $i := i+1;$
    \EndWhile
    \State Let $\mathcal{P} := \{P_i : \text{every proper subword of } P_i \text{ is irreducible wrt } \mathcal{S}\}$;
    \State $\mathcal{T} := \{\}$;
    \For{$P\in \mathcal{P}$}
    \State $Q :=$ \textsc{RewriteLeft}$(X, \mathcal{R}, P)$;
    \State append $(P,Q)$ to $\mathcal{T}$;
    \EndFor
    \EndProcedure
\end{algorithmic}

\bigskip
\noindent The following is the Euclidean algorithm for positive integers $a,b$:

\bigskip

\begin{algorithmic}[1]
    \Procedure{gcd}{a,b}
    \If{$a = 0$}
    \State return $b$
    \EndIf
    \While{$b \neq 0$}
    \If{$a > b$}
    \State $a := a-b$
    \Else
    \State $b := b-a$
    \EndIf
    \EndWhile
    \State return $a$
    \EndProcedure
\end{algorithmic}

\bigskip

Let $X=\{x\}$ and let $$\mathcal{R} := \{x^m\rightarrow \varepsilon,\;\;
x^n\rightarrow \varepsilon\}$$ where $m,n \in \mathbb{Z}_{>0}$.

Show that the Knuth-Bendix algorithm returns a confluent rewriting system
consisting of the single rule \[x^{\mathrm{gcd}(m,n)} \rightarrow
\varepsilon.\] In writing your proof, refer to the line numbers given in the
above code. In the course of your proof, compare the execution of
$\mathrm{gcd}(m,n)$ using the Euclidean algorithm with the execution of the
Knuth-Bendix algorithm.

\bigskip

\emph{Solution.} Suppose without loss that $m>n$. Line 7-8 of
\textsc{KnuthBendix} starts us off with $\mathcal{S} =
\{(x^m,\varepsilon),(x^n,\varepsilon)\}$ and then line 12 of
\textsc{KnuthBendix} gives rise to an \textsc{Update} call in line 9 of
\textsc{Overlap}. This appends $(x^{m-n},\varepsilon)$ to $\mathcal{S}$,
corresponding to line 7 of the gcd algorithm. The successive calls to
\textsc{Overlap} lines 12 and 14 (and the resulting calls to \textsc{Update} in
line 9 of \textsc{Overlap}) of \textsc{KnuthBendix} correspond to lines 7 and 9
of gcd.

A much more in depth discussion of the similarities between the Knuth-Bendix
algorithm and the Gr\"obner-Buchberger algorithm (of which the gcd is the basic
example) may be found in the paper ``Algebraic Simplification'' by Buchberger
and Loos (1982).

\bigskip

\noindent 9. Given \(w \in \{0,1\}^*\) we write $w = a_n a_{n-1} \cdots a_0$
with $a_i \in \{0,1\}$ for all $i$. We define $\mathrm{eval}(w) := \sum_{i=0}^n
a_i2^i$. Thus $\mathrm{eval} : \{0,1\}^* \rightarrow \mathbb{Z}_{\ge 0}$ is a
well defined function. In other words, using the eval function, we regard $w$
as representing a nonnegative integer written in base 2 in the usual way.

Show that the language \[\mathscr{L} := \{w \in \{0,1\}^* : w \text{ starts
with a } 1 \text{ and } \mathrm{eval}(w) \text{ is a prime number}\}\] is not
regular.

\bigskip

\emph{Solution.} This was a challenge problem. None of the students could solve
it on the exam. The the solution is on page 57 of Analytic Combinatorics by
Flajolet and Sedgewick.
\end{document}


text:
<?xml version="1.0" encoding="UTF-8"?>
<billStatus>
  <bill>
    <amendments>
      <amendment>
        <number>1110</number>
        <description />
        <purpose>In the nature of a substitute.</purpose>
        <latestAction>
          <actionDate>2017-10-05</actionDate>
          <text>Amendment SA 1110 agreed to in Senate by Unanimous Consent.</text>
        </latestAction>
        <description />
        <actions>
          <count>6</count>
          <actionByCounts>
            <senate>5</senate>
          </actionByCounts>
          <actionTypeCounts>
            <amendmentAgreedTo>1</amendmentAgreedTo>
            <senateAmendmentProposedOnTheFloor>1</senateAmendmentProposedOnTheFloor>
            <senateAmendmentAgreedTo>1</senateAmendmentAgreedTo>
            <senateAmendmentSubmitted>1</senateAmendmentSubmitted>
            <amendmentProposed>1</amendmentProposed>
          </actionTypeCounts>
          <actions>
            <item>
              <actionDate>2017-10-05</actionDate>
              <committee />
              <links>
                <link>
                  <url>https://www.congress.gov/amendment/115th-congress/senate-amendment/1110</url>
                  <name>S.Amdt.1110</name>
                </link>
                <link>
                  <url>https://www.congress.gov/amendment/115th-congress/senate-amendment/1110</url>
                  <name>SA 1110</name>
                </link>
              </links>
              <sourceSystem>
                0
                <name>Senate</name>
              </sourceSystem>
              <text>Amendment SA 1110 agreed to in Senate by Unanimous Consent.</text>
              <type>Floor</type>
            </item>
            <item>
              <actionDate>2017-10-05</actionDate>
              <committee />
              <links>
                <link>
                  <url>https://www.congress.gov/amendment/115th-congress/senate-amendment/1110</url>
                  <name>S.Amdt.1110</name>
                </link>
                <link>
                  <url>https://www.congress.gov/congressional-record/volume-163/senate-section/page/S6375</url>
                  <name>S6375</name>
                </link>
                <link>
                  <url>https://www.congress.gov/amendment/115th-congress/senate-amendment/1110</url>
                  <name>SA 1110</name>
                </link>
              </links>
              <sourceSystem>
                0
                <name>Senate</name>
              </sourceSystem>
              <text>Amendment SA 1110 proposed by Senator McConnell for Senator Rubio. (consideration: CR S6375)</text>
              <type>Floor</type>
            </item>
            <item>
              <actionDate>2017-10-05</actionDate>
              <committee />
              <links />
              <text />
            </item>
            <item>
              <sourceSystem>
                9
                <name>Library of Congress</name>
              </sourceSystem>
              <committee />
              <text>Senate amendment agreed to: Amendment SA 1110 agreed to in Senate by Unanimous Consent.</text>
              <actionDate>2017-10-05</actionDate>
              <links>
                <link>
                  <url>https://www.congress.gov/amendment/115th-congress/senate-amendment/1110</url>
                  <name>S.Amdt.1110</name>
                </link>
                <link>
                  <url>https://www.congress.gov/amendment/115th-congress/senate-amendment/1110</url>
                  <name>SA 1110</name>
                </link>
              </links>
              <actionCode>94000</actionCode>
              <type>Floor</type>
            </item>
            <item>
              <sourceSystem>
                9
                <name>Library of Congress</name>
              </sourceSystem>
              <committee />
              <text>Senate amendment proposed (on the floor): Amendment SA 1110 proposed by Senator McConnell for Senator Rubio.</text>
              <actionDate>2017-10-05</actionDate>
              <links>
                <link>
                  <url>https://www.congress.gov/amendment/115th-congress/senate-amendment/1110</url>
                  <name>S.Amdt.1110</name>
                </link>
                <link>
                  <url>https://www.congress.gov/congressional-record/volume-163/senate-section/page/S6375</url>
                  <name>S6375</name>
                </link>
                <link>
                  <url>https://www.congress.gov/amendment/115th-congress/senate-amendment/1110</url>
                  <name>SA 1110</name>
                </link>
              </links>
              <actionCode>93000</actionCode>
              <type>Floor</type>
            </item>
            <item>
              <sourceSystem>
                9
                <name>Library of Congress</name>
              </sourceSystem>
              <committee />
              <text>Senate amendment submitted</text>
              <actionDate>2017-10-05</actionDate>
              <links />
              <actionCode>91000</actionCode>
              <type>Floor</type>
            </item>
          </actions>
        </actions>
        <updateDate>2017-10-11T03:11:44Z</updateDate>
        <notes />
        <proposedDate>2017-10-05T04:00:00Z</proposedDate>
        <sponsors>
          <item>
            <firstName>Marco</firstName>
            <middleName />
            <bioguideId>R000595</bioguideId>
            <lastName>Rubio</lastName>
            <state>FL</state>
            <fullName>Sen. Rubio, Marco [R-FL]</fullName>
            <identifiers>
              <lisID>2084</lisID>
              <bioguideId>R000595</bioguideId>
              <gpoId>8242</gpoId>
            </identifiers>
            <party>R</party>
          </item>
        </sponsors>
        <number>1110</number>
        <titles />
        <amendments>
          <count>0</count>
        </amendments>
        <purpose>In the nature of a substitute.</purpose>
        <createDate>2017-10-06T04:46:08Z</createDate>
        <submittedDate>2017-10-05T04:00:00Z</submittedDate>
        <version>1.0.0</version>
        <cosponsors>
          <totalCount>34</totalCount>
          <item>
            <party>D</party>
            <fullName>Sen. Shaheen, Jeanne [D-NH]</fullName>
            <bioguideId>S001181</bioguideId>
            <middleName />
            <sponsorshipWithdrawnDate />
            <identifiers>
              <lisID>1901</lisID>
              <bioguideId>S001181</bioguideId>
              <gpoId>8276</gpoId>
            </identifiers>
            <firstName>Jeanne</firstName>
            <lastName>Shaheen</lastName>
            <state>NH</state>
            <isOriginalCosponsor>True</isOriginalCosponsor>
            <sponsorshipDate>2017-10-05</sponsorshipDate>
          </item>
          <item>
            <party>R</party>
            <fullName>Sen. Crapo, Mike [R-ID]</fullName>
            <bioguideId>C000880</bioguideId>
            <middleName>D.</middleName>
            <sponsorshipWithdrawnDate />
            <identifiers>
              <lisID>250</lisID>
              <bioguideId>C000880</bioguideId>
              <gpoId>8289</gpoId>
            </identifiers>
            <firstName>MICHAEL</firstName>
            <lastName>CRAPO</lastName>
            <state>ID</state>
            <isOriginalCosponsor>True</isOriginalCosponsor>
            <sponsorshipDate>2017-10-05</sponsorshipDate>
          </item>
          <item>
            <party>D</party>
            <fullName>Sen. Kaine, Tim [D-VA]</fullName>
            <bioguideId>K000384</bioguideId>
            <middleName />
            <sponsorshipWithdrawnDate />
            <identifiers>
              <lisID>2176</lisID>
              <bioguideId>K000384</bioguideId>
              <gpoId />
            </identifiers>
            <firstName>Timothy</firstName>
            <lastName>Kaine</lastName>
            <state>VA</state>
            <isOriginalCosponsor>True</isOriginalCosponsor>
            <sponsorshipDate>2017-10-05</sponsorshipDate>
          </item>
          <item>
            <party>R</party>
            <fullName>Sen. Cornyn, John [R-TX]</fullName>
            <bioguideId>C001056</bioguideId>
            <middleName />
            <sponsorshipWithdrawnDate />
            <identifiers>
              <lisID>1692</lisID>
              <bioguideId>C001056</bioguideId>
              <gpoId>8295</gpoId>
            </identifiers>
            <firstName>John</firstName>
            <lastName>Cornyn</lastName>
            <state>TX</state>
            <isOriginalCosponsor>True</isOriginalCosponsor>
            <sponsorshipDate>2017-10-05</sponsorshipDate>
          </item>
          <item>
            <party>D</party>
            <fullName>Sen. Menendez, Robert [D-NJ]</fullName>
            <bioguideId>M000639</bioguideId>
            <middleName />
            <sponsorshipWithdrawnDate />
            <identifiers>
              <lisID>791</lisID>
              <gpoId>8239</gpoId>
              <bioguideId>M000639</bioguideId>
            </identifiers>
            <firstName>ROBERT</firstName>
            <lastName>MENENDEZ</lastName>
            <state>NJ</state>
            <isOriginalCosponsor>True</isOriginalCosponsor>
            <sponsorshipDate>2017-10-05</sponsorshipDate>
          </item>
          <item>
            <party>R</party>
            <fullName>Sen. Perdue, David [R-GA]</fullName>
            <bioguideId>P000612</bioguideId>
            <middleName>Alfred</middleName>
            <sponsorshipWithdrawnDate />
            <identifiers>
              <lisID>2286</lisID>
              <bioguideId>P000612</bioguideId>
              <gpoId />
            </identifiers>
            <firstName>David</firstName>
            <lastName>Perdue</lastName>
            <state>GA</state>
            <isOriginalCosponsor>True</isOriginalCosponsor>
            <sponsorshipDate>2017-10-05</sponsorshipDate>
          </item>
          <item>
            <party>D</party>
            <fullName>Sen. Heitkamp, Heidi [D-ND]</fullName>
            <bioguideId>H001069</bioguideId>
            <middleName />
            <sponsorshipWithdrawnDate />
            <identifiers>
              <lisID>2174</lisID>
              <bioguideId>H001069</bioguideId>
              <gpoId />
            </identifiers>
            <firstName>Heidi</firstName>
            <lastName>Heitkamp</lastName>
            <state>ND</state>
            <isOriginalCosponsor>True</isOriginalCosponsor>
            <sponsorshipDate>2017-10-05</sponsorshipDate>
          </item>
          <item>
            <party>R</party>
            <fullName>Sen. Blunt, Roy [R-MO]</fullName>
            <bioguideId>B000575</bioguideId>
            <middleName />
            <sponsorshipWithdrawnDate />
            <identifiers>
              <lisID>1464</lisID>
              <bioguideId>B000575</bioguideId>
              <gpoId>8313</gpoId>
            </identifiers>
            <firstName>Roy</firstName>
            <lastName>Blunt</lastName>
            <state>MO</state>
            <isOriginalCosponsor>True</isOriginalCosponsor>
            <sponsorshipDate>2017-10-05</sponsorshipDate>
          </item>
          <item>
            <party>D</party>
            <fullName>Sen. Tester, Jon [D-MT]</fullName>
            <bioguideId>T000464</bioguideId>
            <middleName />
            <sponsorshipWithdrawnDate />
            <identifiers>
              <bioguideId>T000464</bioguideId>
              <lisID>1829</lisID>
              <gpoId>8258</gpoId>
            </identifiers>
            <firstName>Jon</firstName>
            <lastName>Tester</lastName>
            <state>MT</state>
            <isOriginalCosponsor>True</isOriginalCosponsor>
            <sponsorshipDate>2017-10-05</sponsorshipDate>
          </item>
          <item>
            <party>R</party>
            <fullName>Sen. Capito, Shelley Moore [R-WV]</fullName>
            <bioguideId>C001047</bioguideId>
            <middleName>MOORE</middleName>
            <sponsorshipWithdrawnDate />
            <identifiers>
              <bioguideId>C001047</bioguideId>
              <gpoId>8223</gpoId>
              <lisID>1676</lisID>
            </identifiers>
            <firstName>SHELLEY</firstName>
            <lastName>CAPITO</lastName>
            <state>WV</state>
            <isOriginalCosponsor>True</isOriginalCosponsor>
            <sponsorshipDate>2017-10-05</sponsorshipDate>
          </item>
          <item>
            <party>D</party>
            <fullName>Sen. Blumenthal, Richard [D-CT]</fullName>
            <bioguideId>B001277</bioguideId>
            <middleName />
            <sponsorshipWithdrawnDate />
            <identifiers>
              <bioguideId>B001277</bioguideId>
              <gpoId>8332</gpoId>
              <lisID>2076</lisID>
            </identifiers>
            <firstName>Richard</firstName>
            <lastName>Blumenthal</lastName>
            <state>CT</state>
            <isOriginalCosponsor>True</isOriginalCosponsor>
            <sponsorshipDate>2017-10-05</sponsorshipDate>
          </item>
          <item>
            <party>R</party>
            <fullName>Sen. Moran, Jerry [R-KS]</fullName>
            <bioguideId>M000934</bioguideId>
            <middleName />
            <sponsorshipWithdrawnDate />
            <identifiers>
              <bioguideId>M000934</bioguideId>
              <gpoId>8307</gpoId>
              <lisID>1507</lisID>
            </identifiers>
            <firstName>JERRY</firstName>
            <lastName>MORAN</lastName>
            <state>KS</state>
            <isOriginalCosponsor>True</isOriginalCosponsor>
            <sponsorshipDate>2017-10-05</sponsorshipDate>
          </item>
          <item>
            <party>R</party>
            <fullName>Sen. Gardner, Cory [R-CO]</fullName>
            <bioguideId>G000562</bioguideId>
            <middleName />
            <sponsorshipWithdrawnDate />
            <identifiers>
              <lisID>1998</lisID>
              <bioguideId>G000562</bioguideId>
              <gpoId>7862</gpoId>
            </identifiers>
            <firstName>Cory</firstName>
            <lastName>Gardner</lastName>
            <state>CO</state>
            <isOriginalCosponsor>True</isOriginalCosponsor>
            <sponsorshipDate>2017-10-05</sponsorshipDate>
          </item>
          <item>
            <party>R</party>
            <fullName>Sen. Boozman, John [R-AR]</fullName>
            <bioguideId>B001236</bioguideId>
            <middleName />
            <sponsorshipWithdrawnDate />
            <identifiers>
              <lisID>1687</lisID>
              <gpoId>8247</gpoId>
              <bioguideId>B001236</bioguideId>
            </identifiers>
            <firstName>John</firstName>
            <lastName>Boozman</lastName>
            <state>AR</state>
            <isOriginalCosponsor>True</isOriginalCosponsor>
            <sponsorshipDate>2017-10-05</sponsorshipDate>
          </item>
          <item>
            <party>R</party>
            <fullName>Sen. Ernst, Joni  [R-IA]</fullName>
            <bioguideId>E000295</bioguideId>
            <middleName />
            <sponsorshipWithdrawnDate />
            <identifiers>
              <lisID>2283</lisID>
              <bioguideId>E000295</bioguideId>
              <gpoId />
            </identifiers>
            <firstName>Joni</firstName>
            <lastName>Ernst</lastName>
            <state>IA</state>
            <isOriginalCosponsor>True</isOriginalCosponsor>
            <sponsorshipDate>2017-10-05</sponsorshipDate>
          </item>
          <item>
            <party>R</party>
            <fullName>Sen. Kennedy, John [R-LA]</fullName>
            <bioguideId>K000393</bioguideId>
            <middleName>Neely</middleName>
            <sponsorshipWithdrawnDate />
            <identifiers>
              <lisID>2303</lisID>
              <bioguideId>K000393</bioguideId>
              <gpoId />
            </identifiers>
            <firstName>John</firstName>
            <lastName>Kennedy</lastName>
            <state>LA</state>
            <isOriginalCosponsor>True</isOriginalCosponsor>
            <sponsorshipDate>2017-10-05</sponsorshipDate>
          </item>
          <item>
            <party>R</party>
            <fullName>Sen. Wicker, Roger F. [R-MS]</fullName>
            <bioguideId>W000437</bioguideId>
            <middleName>F.</middleName>
            <sponsorshipWithdrawnDate />
            <identifiers>
              <lisID>1226</lisID>
              <gpoId>8263</gpoId>
              <bioguideId>W000437</bioguideId>
            </identifiers>
            <firstName>ROGER</firstName>
            <lastName>WICKER</lastName>
            <state>MS</state>
            <isOriginalCosponsor>True</isOriginalCosponsor>
            <sponsorshipDate>2017-10-05</sponsorshipDate>
          </item>
          <item>
            <party>R</party>
            <fullName>Sen. Rounds, Mike  [R-SD]</fullName>
            <bioguideId>R000605</bioguideId>
            <middleName />
            <sponsorshipWithdrawnDate />
            <identifiers>
              <lisID>2288</lisID>
              <gpoId />
              <bioguideId>R000605</bioguideId>
            </identifiers>
            <firstName>Mike</firstName>
            <lastName>Rounds</lastName>
            <state>SD</state>
            <isOriginalCosponsor>True</isOriginalCosponsor>
            <sponsorshipDate>2017-10-05</sponsorshipDate>
          </item>
          <item>
            <party>R</party>
            <fullName>Sen. Heller, Dean [R-NV]</fullName>
            <bioguideId>H001041</bioguideId>
            <middleName />
            <sponsorshipWithdrawnDate />
            <identifiers>
              <lisID>1863</lisID>
              <bioguideId>H001041</bioguideId>
              <gpoId>8060</gpoId>
            </identifiers>
            <firstName>Dean</firstName>
            <lastName>Heller</lastName>
            <state>NV</state>
            <isOriginalCosponsor>True</isOriginalCosponsor>
            <sponsorshipDate>2017-10-05</sponsorshipDate>
          </item>
          <item>
            <party>D</party>
            <fullName>Sen. Wyden, Ron [D-OR]</fullName>
            <bioguideId>W000779</bioguideId>
            <middleName />
            <sponsorshipWithdrawnDate />
            <identifiers>
              <lisID>1247</lisID>
              <bioguideId>W000779</bioguideId>
              <gpoId>8265</gpoId>
            </identifiers>
            <firstName>RON</firstName>
            <lastName>WYDEN</lastName>
            <state>OR</state>
            <isOriginalCosponsor>True</isOriginalCosponsor>
            <sponsorshipDate>2017-10-05</sponsorshipDate>
          </item>
          <item>
            <party>R</party>
            <fullName>Sen. Cruz, Ted [R-TX]</fullName>
            <bioguideId>C001098</bioguideId>
            <middleName />
            <sponsorshipWithdrawnDate />
            <identifiers>
              <lisID>2175</lisID>
              <bioguideId>C001098</bioguideId>
              <gpoId />
            </identifiers>
            <firstName>Ted</firstName>
            <lastName>Cruz</lastName>
            <state>TX</state>
            <isOriginalCosponsor>True</isOriginalCosponsor>
            <sponsorshipDate>2017-10-05</sponsorshipDate>
          </item>
          <item>
            <party>R</party>
            <fullName>Sen. Sasse, Ben  [R-NE]</fullName>
            <bioguideId>S001197</bioguideId>
            <middleName />
            <sponsorshipWithdrawnDate />
            <identifiers>
              <lisID>2289</lisID>
              <bioguideId>S001197</bioguideId>
              <gpoId />
            </identifiers>
            <firstName>Ben</firstName>
            <lastName>Sasse</lastName>
            <state>NE</state>
            <isOriginalCosponsor>True</isOriginalCosponsor>
            <sponsorshipDate>2017-10-05</sponsorshipDate>
          </item>
          <item>
            <party>R</party>
            <fullName>Sen. Roberts, Pat [R-KS]</fullName>
            <bioguideId>R000307</bioguideId>
            <middleName />
            <sponsorshipWithdrawnDate />
            <identifiers>
              <lisID>968</lisID>
              <bioguideId>R000307</bioguideId>
              <gpoId>8275</gpoId>
            </identifiers>
            <firstName>PAT</firstName>
            <lastName>ROBERTS</lastName>
            <state>KS</state>
            <isOriginalCosponsor>True</isOriginalCosponsor>
            <sponsorshipDate>2017-10-05</sponsorshipDate>
          </item>
          <item>
            <party>R</party>
            <fullName>Sen. Collins, Susan M. [R-ME]</fullName>
            <bioguideId>C001035</bioguideId>
            <middleName>MARGARET</middleName>
            <sponsorshipWithdrawnDate />
            <identifiers>
              <lisID>1541</lisID>
              <bioguideId>C001035</bioguideId>
              <gpoId>8291</gpoId>
            </identifiers>
            <firstName>SUSAN</firstName>
            <lastName>COLLINS</lastName>
            <state>ME</state>
            <isOriginalCosponsor>True</isOriginalCosponsor>
            <sponsorshipDate>2017-10-05</sponsorshipDate>
          </item>
          <item>
            <party>R</party>
            <fullName>Sen. Cotton, Tom [R-AR]</fullName>
            <bioguideId>C001095</bioguideId>
            <middleName />
            <sponsorshipWithdrawnDate />
            <identifiers>
              <lisID>2098</lisID>
              <gpoId />
              <bioguideId>C001095</bioguideId>
            </identifiers>
            <firstName>Tom</firstName>
            <lastName>Cotton</lastName>
            <state>AR</state>
            <isOriginalCosponsor>True</isOriginalCosponsor>
            <sponsorshipDate>2017-10-05</sponsorshipDate>
          </item>
          <item>
            <party>R</party>
            <fullName>Sen. Young, Todd C. [R-IN]</fullName>
            <bioguideId>Y000064</bioguideId>
            <middleName>C.</middleName>
            <sponsorshipWithdrawnDate />
            <identifiers>
              <lisID>2019</lisID>
              <bioguideId>Y000064</bioguideId>
              <gpoId>7948</gpoId>
            </identifiers>
            <firstName>Todd</firstName>
            <lastName>Young</lastName>
            <state>IN</state>
            <isOriginalCosponsor>True</isOriginalCosponsor>
            <sponsorshipDate>2017-10-05</sponsorshipDate>
          </item>
          <item>
            <party>D</party>
            <fullName>Sen. Cortez Masto, Catherine  [D-NV]</fullName>
            <bioguideId>C001113</bioguideId>
            <middleName />
            <sponsorshipWithdrawnDate />
            <identifiers>
              <bioguideId>C001113</bioguideId>
              <lisID>2299</lisID>
              <gpoId />
            </identifiers>
            <firstName>Catherine</firstName>
            <lastName>Cortez Masto</lastName>
            <state>NV</state>
            <isOriginalCosponsor>True</isOriginalCosponsor>
            <sponsorshipDate>2017-10-05</sponsorshipDate>
          </item>
          <item>
            <party>D</party>
            <fullName>Sen. Baldwin, Tammy [D-WI]</fullName>
            <bioguideId>B001230</bioguideId>
            <middleName />
            <sponsorshipWithdrawnDate />
            <identifiers>
              <lisID>1558</lisID>
              <bioguideId>B001230</bioguideId>
              <gpoId>8215</gpoId>
            </identifiers>
            <firstName>TAMMY</firstName>
            <lastName>BALDWIN</lastName>
            <state>WI</state>
            <isOriginalCosponsor>True</isOriginalCosponsor>
            <sponsorshipDate>2017-10-05</sponsorshipDate>
          </item>
          <item>
            <party>D</party>
            <fullName>Sen. Durbin, Richard J. [D-IL]</fullName>
            <bioguideId>D000563</bioguideId>
            <middleName>J.</middleName>
            <sponsorshipWithdrawnDate />
            <identifiers>
              <lisID>326</lisID>
              <bioguideId>D000563</bioguideId>
              <gpoId>8326</gpoId>
            </identifiers>
            <firstName>RICHARD</firstName>
            <lastName>DURBIN</lastName>
            <state>IL</state>
            <isOriginalCosponsor>True</isOriginalCosponsor>
            <sponsorshipDate>2017-10-05</sponsorshipDate>
          </item>
          <item>
            <party>D</party>
            <fullName>Sen. Klobuchar, Amy [D-MN]</fullName>
            <bioguideId>K000367</bioguideId>
            <middleName />
            <sponsorshipWithdrawnDate />
            <identifiers>
              <bioguideId>K000367</bioguideId>
              <lisID>1826</lisID>
              <gpoId>8249</gpoId>
            </identifiers>
            <firstName>Amy</firstName>
            <lastName>Klobuchar</lastName>
            <state>MN</state>
            <isOriginalCosponsor>True</isOriginalCosponsor>
            <sponsorshipDate>2017-10-05</sponsorshipDate>
          </item>
          <item>
            <party>D</party>
            <fullName>Sen. Coons, Christopher A. [D-DE]</fullName>
            <bioguideId>C001088</bioguideId>
            <middleName>A.</middleName>
            <sponsorshipWithdrawnDate />
            <identifiers>
              <bioguideId>C001088</bioguideId>
              <lisID>1984</lisID>
              <gpoId>8297</gpoId>
            </identifiers>
            <firstName>Christopher</firstName>
            <lastName>Coons</lastName>
            <state>DE</state>
            <isOriginalCosponsor>True</isOriginalCosponsor>
            <sponsorshipDate>2017-10-05</sponsorshipDate>
          </item>
          <item>
            <party>D</party>
            <fullName>Sen. Casey, Robert P., Jr. [D-PA]</fullName>
            <bioguideId>C001070</bioguideId>
            <middleName />
            <sponsorshipWithdrawnDate />
            <identifiers>
              <lisID>1828</lisID>
              <gpoId>8282</gpoId>
              <bioguideId>C001070</bioguideId>
            </identifiers>
            <firstName>Bob</firstName>
            <lastName>Casey</lastName>
            <state>PA</state>
            <isOriginalCosponsor>True</isOriginalCosponsor>
            <sponsorshipDate>2017-10-05</sponsorshipDate>
          </item>
          <item>
            <party>D</party>
            <fullName>Sen. Nelson, Bill [D-FL]</fullName>
            <bioguideId>N000032</bioguideId>
            <middleName>WILLIAM</middleName>
            <sponsorshipWithdrawnDate />
            <identifiers>
              <bioguideId>N000032</bioguideId>
              <gpoId>8236</gpoId>
              <lisID>859</lisID>
            </identifiers>
            <firstName>CLARENCE</firstName>
            <lastName>NELSON</lastName>
            <state>FL</state>
            <isOriginalCosponsor>True</isOriginalCosponsor>
            <sponsorshipDate>2017-10-05</sponsorshipDate>
          </item>
          <item>
            <party>D</party>
            <fullName>Sen. Manchin, Joe, III [D-WV]</fullName>
            <bioguideId>M001183</bioguideId>
            <middleName />
            <sponsorshipWithdrawnDate />
            <identifiers>
              <lisID>1983</lisID>
              <bioguideId>M001183</bioguideId>
              <gpoId>8256</gpoId>
            </identifiers>
            <firstName>Joe</firstName>
            <lastName>Manchin</lastName>
            <state>WV</state>
            <isOriginalCosponsor>True</isOriginalCosponsor>
            <sponsorshipDate>2017-10-05</sponsorshipDate>
          </item>
          <currentCount>34</currentCount>
        </cosponsors>
        <chamber>Senate</chamber>
        <amendedAmendment />
        <links />
        <type>SAMDT</type>
        <congress>115</congress>
        <amendedBill>
          <originChamber>Senate</originChamber>
          <title>Hizballah International Financing Prevention Amendments Act of 2017</title>
          <number>1595</number>
          <type>S</type>
          <congress>115</congress>
          <originChamberCode>S</originChamberCode>
        </amendedBill>
        <congress>115</congress>
        <type>SAMDT</type>
      </amendment>
    </amendments>
    <updateDate>2017-10-11T07:12:36Z</updateDate>
    <notes />
    <relatedBills />
    <latestAction>
      <actionDate>2017-10-10</actionDate>
      <text>Held at the desk.</text>
      <links />
      <actionTime>19:42:19</actionTime>
    </latestAction>
    <committees>
      <billCommittees>
        <item>
          <chamber>Senate</chamber>
          <systemCode>ssbk00</systemCode>
          <name>Banking, Housing, and Urban Affairs Committee</name>
          <subcommittees />
          <activities>
            <item>
              <date>2017-10-05T21:50:04Z</date>
              <name>Discharged from</name>
            </item>
            <item>
              <date>2017-07-20T17:45:21Z</date>
              <name>Referred to</name>
            </item>
          </activities>
          <type>Standing</type>
        </item>
      </billCommittees>
    </committees>
    <introducedDate>2017-07-20</introducedDate>
    <committeeReports />
    <congress>115</congress>
    <title>Hizballah International Financing Prevention Amendments Act of 2017</title>
    <recordedVotes />
    <cboCostEstimates />
    <cosponsors>
      <item>
        <firstName>Jeanne</firstName>
        <middleName />
        <bioguideId>S001181</bioguideId>
        <isOriginalCosponsor>True</isOriginalCosponsor>
        <lastName>Shaheen</lastName>
        <state>NH</state>
        <sponsorshipWithdrawnDate />
        <fullName>Sen. Shaheen, Jeanne [D-NH]</fullName>
        <identifiers>
          <lisID>1901</lisID>
          <bioguideId>S001181</bioguideId>
          <gpoId>8276</gpoId>
        </identifiers>
        <party>D</party>
        <sponsorshipDate>2017-07-20</sponsorshipDate>
      </item>
      <item>
        <firstName>MICHAEL</firstName>
        <middleName>D.</middleName>
        <bioguideId>C000880</bioguideId>
        <isOriginalCosponsor>False</isOriginalCosponsor>
        <lastName>CRAPO</lastName>
        <state>ID</state>
        <sponsorshipWithdrawnDate />
        <fullName>Sen. Crapo, Mike [R-ID]</fullName>
        <identifiers>
          <lisID>250</lisID>
          <bioguideId>C000880</bioguideId>
          <gpoId>8289</gpoId>
        </identifiers>
        <party>R</party>
        <sponsorshipDate>2017-07-24</sponsorshipDate>
      </item>
      <item>
        <firstName>John</firstName>
        <middleName />
        <bioguideId>B001236</bioguideId>
        <isOriginalCosponsor>False</isOriginalCosponsor>
        <lastName>Boozman</lastName>
        <state>AR</state>
        <sponsorshipWithdrawnDate />
        <fullName>Sen. Boozman, John [R-AR]</fullName>
        <identifiers>
          <lisID>1687</lisID>
          <gpoId>8247</gpoId>
          <bioguideId>B001236</bioguideId>
        </identifiers>
        <party>R</party>
        <sponsorshipDate>2017-07-24</sponsorshipDate>
      </item>
      <item>
        <firstName>John</firstName>
        <middleName />
        <bioguideId>C001056</bioguideId>
        <isOriginalCosponsor>False</isOriginalCosponsor>
        <lastName>Cornyn</lastName>
        <state>TX</state>
        <sponsorshipWithdrawnDate />
        <fullName>Sen. Cornyn, John [R-TX]</fullName>
        <identifiers>
          <lisID>1692</lisID>
          <bioguideId>C001056</bioguideId>
          <gpoId>8295</gpoId>
        </identifiers>
        <party>R</party>
        <sponsorshipDate>2017-07-26</sponsorshipDate>
      </item>
      <item>
        <firstName>ROGER</firstName>
        <middleName>F.</middleName>
        <bioguideId>W000437</bioguideId>
        <isOriginalCosponsor>False</isOriginalCosponsor>
        <lastName>WICKER</lastName>
        <state>MS</state>
        <sponsorshipWithdrawnDate />
        <fullName>Sen. Wicker, Roger F. [R-MS]</fullName>
        <identifiers>
          <lisID>1226</lisID>
          <gpoId>8263</gpoId>
          <bioguideId>W000437</bioguideId>
        </identifiers>
        <party>R</party>
        <sponsorshipDate>2017-07-26</sponsorshipDate>
      </item>
      <item>
        <firstName>David</firstName>
        <middleName>Alfred</middleName>
        <bioguideId>P000612</bioguideId>
        <isOriginalCosponsor>False</isOriginalCosponsor>
        <lastName>Perdue</lastName>
        <state>GA</state>
        <sponsorshipWithdrawnDate />
        <fullName>Sen. Perdue, David [R-GA]</fullName>
        <identifiers>
          <lisID>2286</lisID>
          <bioguideId>P000612</bioguideId>
          <gpoId />
        </identifiers>
        <party>R</party>
        <sponsorshipDate>2017-07-31</sponsorshipDate>
      </item>
      <item>
        <firstName>SHELLEY</firstName>
        <middleName>MOORE</middleName>
        <bioguideId>C001047</bioguideId>
        <isOriginalCosponsor>False</isOriginalCosponsor>
        <lastName>CAPITO</lastName>
        <state>WV</state>
        <sponsorshipWithdrawnDate />
        <fullName>Sen. Capito, Shelley Moore [R-WV]</fullName>
        <identifiers>
          <bioguideId>C001047</bioguideId>
          <gpoId>8223</gpoId>
          <lisID>1676</lisID>
        </identifiers>
        <party>R</party>
        <sponsorshipDate>2017-08-01</sponsorshipDate>
      </item>
      <item>
        <firstName>Dean</firstName>
        <middleName />
        <bioguideId>H001041</bioguideId>
        <isOriginalCosponsor>False</isOriginalCosponsor>
        <lastName>Heller</lastName>
        <state>NV</state>
        <sponsorshipWithdrawnDate />
        <fullName>Sen. Heller, Dean [R-NV]</fullName>
        <identifiers>
          <lisID>1863</lisID>
          <bioguideId>H001041</bioguideId>
          <gpoId>8060</gpoId>
        </identifiers>
        <party>R</party>
        <sponsorshipDate>2017-08-03</sponsorshipDate>
      </item>
      <item>
        <firstName>Timothy</firstName>
        <middleName />
        <bioguideId>K000384</bioguideId>
        <isOriginalCosponsor>False</isOriginalCosponsor>
        <lastName>Kaine</lastName>
        <state>VA</state>
        <sponsorshipWithdrawnDate />
        <fullName>Sen. Kaine, Tim [D-VA]</fullName>
        <identifiers>
          <lisID>2176</lisID>
          <bioguideId>K000384</bioguideId>
          <gpoId />
        </identifiers>
        <party>D</party>
        <sponsorshipDate>2017-09-13</sponsorshipDate>
      </item>
      <item>
        <firstName>Mike</firstName>
        <middleName />
        <bioguideId>R000605</bioguideId>
        <isOriginalCosponsor>False</isOriginalCosponsor>
        <lastName>Rounds</lastName>
        <state>SD</state>
        <sponsorshipWithdrawnDate />
        <fullName>Sen. Rounds, Mike  [R-SD]</fullName>
        <identifiers>
          <lisID>2288</lisID>
          <gpoId />
          <bioguideId>R000605</bioguideId>
        </identifiers>
        <party>R</party>
        <sponsorshipDate>2017-09-19</sponsorshipDate>
      </item>
      <item>
        <firstName>JERRY</firstName>
        <middleName />
        <bioguideId>M000934</bioguideId>
        <isOriginalCosponsor>False</isOriginalCosponsor>
        <lastName>MORAN</lastName>
        <state>KS</state>
        <sponsorshipWithdrawnDate />
        <fullName>Sen. Moran, Jerry [R-KS]</fullName>
        <identifiers>
          <bioguideId>M000934</bioguideId>
          <gpoId>8307</gpoId>
          <lisID>1507</lisID>
        </identifiers>
        <party>R</party>
        <sponsorshipDate>2017-09-19</sponsorshipDate>
      </item>
      <item>
        <firstName>John</firstName>
        <middleName>Neely</middleName>
        <bioguideId>K000393</bioguideId>
        <isOriginalCosponsor>False</isOriginalCosponsor>
        <lastName>Kennedy</lastName>
        <state>LA</state>
        <sponsorshipWithdrawnDate />
        <fullName>Sen. Kennedy, John [R-LA]</fullName>
        <identifiers>
          <lisID>2303</lisID>
          <bioguideId>K000393</bioguideId>
          <gpoId />
        </identifiers>
        <party>R</party>
        <sponsorshipDate>2017-09-19</sponsorshipDate>
      </item>
      <item>
        <firstName>Cory</firstName>
        <middleName />
        <bioguideId>G000562</bioguideId>
        <isOriginalCosponsor>False</isOriginalCosponsor>
        <lastName>Gardner</lastName>
        <state>CO</state>
        <sponsorshipWithdrawnDate />
        <fullName>Sen. Gardner, Cory [R-CO]</fullName>
        <identifiers>
          <lisID>1998</lisID>
          <bioguideId>G000562</bioguideId>
          <gpoId>7862</gpoId>
        </identifiers>
        <party>R</party>
        <sponsorshipDate>2017-09-19</sponsorshipDate>
      </item>
      <item>
        <firstName>Joni</firstName>
        <middleName />
        <bioguideId>E000295</bioguideId>
        <isOriginalCosponsor>False</isOriginalCosponsor>
        <lastName>Ernst</lastName>
        <state>IA</state>
        <sponsorshipWithdrawnDate />
        <fullName>Sen. Ernst, Joni  [R-IA]</fullName>
        <identifiers>
          <lisID>2283</lisID>
          <bioguideId>E000295</bioguideId>
          <gpoId />
        </identifiers>
        <party>R</party>
        <sponsorshipDate>2017-09-26</sponsorshipDate>
      </item>
      <item>
        <firstName>ROBERT</firstName>
        <middleName />
        <bioguideId>M000639</bioguideId>
        <isOriginalCosponsor>False</isOriginalCosponsor>
        <lastName>MENENDEZ</lastName>
        <state>NJ</state>
        <sponsorshipWithdrawnDate />
        <fullName>Sen. Menendez, Robert [D-NJ]</fullName>
        <identifiers>
          <lisID>791</lisID>
          <gpoId>8239</gpoId>
          <bioguideId>M000639</bioguideId>
        </identifiers>
        <party>D</party>
        <sponsorshipDate>2017-09-26</sponsorshipDate>
      </item>
      <item>
        <firstName>Heidi</firstName>
        <middleName />
        <bioguideId>H001069</bioguideId>
        <isOriginalCosponsor>False</isOriginalCosponsor>
        <lastName>Heitkamp</lastName>
        <state>ND</state>
        <sponsorshipWithdrawnDate />
        <fullName>Sen. Heitkamp, Heidi [D-ND]</fullName>
        <identifiers>
          <lisID>2174</lisID>
          <bioguideId>H001069</bioguideId>
          <gpoId />
        </identifiers>
        <party>D</party>
        <sponsorshipDate>2017-09-26</sponsorshipDate>
      </item>
      <item>
        <firstName>Jon</firstName>
        <middleName />
        <bioguideId>T000464</bioguideId>
        <isOriginalCosponsor>False</isOriginalCosponsor>
        <lastName>Tester</lastName>
        <state>MT</state>
        <sponsorshipWithdrawnDate />
        <fullName>Sen. Tester, Jon [D-MT]</fullName>
        <identifiers>
          <bioguideId>T000464</bioguideId>
          <lisID>1829</lisID>
          <gpoId>8258</gpoId>
        </identifiers>
        <party>D</party>
        <sponsorshipDate>2017-09-27</sponsorshipDate>
      </item>
      <item>
        <firstName>RON</firstName>
        <middleName />
        <bioguideId>W000779</bioguideId>
        <isOriginalCosponsor>False</isOriginalCosponsor>
        <lastName>WYDEN</lastName>
        <state>OR</state>
        <sponsorshipWithdrawnDate />
        <fullName>Sen. Wyden, Ron [D-OR]</fullName>
        <identifiers>
          <lisID>1247</lisID>
          <bioguideId>W000779</bioguideId>
          <gpoId>8265</gpoId>
        </identifiers>
        <party>D</party>
        <sponsorshipDate>2017-09-27</sponsorshipDate>
      </item>
      <item>
        <firstName>Richard</firstName>
        <middleName />
        <bioguideId>B001277</bioguideId>
        <isOriginalCosponsor>False</isOriginalCosponsor>
        <lastName>Blumenthal</lastName>
        <state>CT</state>
        <sponsorshipWithdrawnDate />
        <fullName>Sen. Blumenthal, Richard [D-CT]</fullName>
        <identifiers>
          <bioguideId>B001277</bioguideId>
          <gpoId>8332</gpoId>
          <lisID>2076</lisID>
        </identifiers>
        <party>D</party>
        <sponsorshipDate>2017-09-28</sponsorshipDate>
      </item>
      <item>
        <firstName>Roy</firstName>
        <middleName />
        <bioguideId>B000575</bioguideId>
        <isOriginalCosponsor>False</isOriginalCosponsor>
        <lastName>Blunt</lastName>
        <state>MO</state>
        <sponsorshipWithdrawnDate />
        <fullName>Sen. Blunt, Roy [R-MO]</fullName>
        <identifiers>
          <lisID>1464</lisID>
          <bioguideId>B000575</bioguideId>
          <gpoId>8313</gpoId>
        </identifiers>
        <party>R</party>
        <sponsorshipDate>2017-09-28</sponsorshipDate>
      </item>
      <item>
        <firstName>PAT</firstName>
        <middleName />
        <bioguideId>R000307</bioguideId>
        <isOriginalCosponsor>False</isOriginalCosponsor>
        <lastName>ROBERTS</lastName>
        <state>KS</state>
        <sponsorshipWithdrawnDate />
        <fullName>Sen. Roberts, Pat [R-KS]</fullName>
        <identifiers>
          <lisID>968</lisID>
          <bioguideId>R000307</bioguideId>
          <gpoId>8275</gpoId>
        </identifiers>
        <party>R</party>
        <sponsorshipDate>2017-09-28</sponsorshipDate>
      </item>
      <item>
        <firstName>Ted</firstName>
        <middleName />
        <bioguideId>C001098</bioguideId>
        <isOriginalCosponsor>False</isOriginalCosponsor>
        <lastName>Cruz</lastName>
        <state>TX</state>
        <sponsorshipWithdrawnDate />
        <fullName>Sen. Cruz, Ted [R-TX]</fullName>
        <identifiers>
          <lisID>2175</lisID>
          <bioguideId>C001098</bioguideId>
          <gpoId />
        </identifiers>
        <party>R</party>
        <sponsorshipDate>2017-09-28</sponsorshipDate>
      </item>
      <item>
        <firstName>John</firstName>
        <middleName />
        <bioguideId>H001061</bioguideId>
        <isOriginalCosponsor>False</isOriginalCosponsor>
        <lastName>Hoeven</lastName>
        <state>ND</state>
        <sponsorshipWithdrawnDate />
        <fullName>Sen. Hoeven, John [R-ND]</fullName>
        <identifiers>
          <lisID>2079</lisID>
          <gpoId>8331</gpoId>
          <bioguideId>H001061</bioguideId>
        </identifiers>
        <party>R</party>
        <sponsorshipDate>2017-09-28</sponsorshipDate>
      </item>
      <item>
        <firstName>Ben</firstName>
        <middleName />
        <bioguideId>S001197</bioguideId>
        <isOriginalCosponsor>False</isOriginalCosponsor>
        <lastName>Sasse</lastName>
        <state>NE</state>
        <sponsorshipWithdrawnDate />
        <fullName>Sen. Sasse, Ben  [R-NE]</fullName>
        <identifiers>
          <lisID>2289</lisID>
          <bioguideId>S001197</bioguideId>
          <gpoId />
        </identifiers>
        <party>R</party>
        <sponsorshipDate>2017-09-28</sponsorshipDate>
      </item>
      <item>
        <firstName>John</firstName>
        <middleName />
        <bioguideId>B001261</bioguideId>
        <isOriginalCosponsor>False</isOriginalCosponsor>
        <lastName>Barrasso</lastName>
        <state>WY</state>
        <sponsorshipWithdrawnDate />
        <fullName>Sen. Barrasso, John [R-WY]</fullName>
        <identifiers>
          <bioguideId>B001261</bioguideId>
          <lisID>1881</lisID>
          <gpoId>8300</gpoId>
        </identifiers>
        <party>R</party>
        <sponsorshipDate>2017-10-03</sponsorshipDate>
      </item>
      <item>
        <firstName>SUSAN</firstName>
        <middleName>MARGARET</middleName>
        <bioguideId>C001035</bioguideId>
        <isOriginalCosponsor>False</isOriginalCosponsor>
        <lastName>COLLINS</lastName>
        <state>ME</state>
        <sponsorshipWithdrawnDate />
        <fullName>Sen. Collins, Susan M. [R-ME]</fullName>
        <identifiers>
          <lisID>1541</lisID>
          <bioguideId>C001035</bioguideId>
          <gpoId>8291</gpoId>
        </identifiers>
        <party>R</party>
        <sponsorshipDate>2017-10-03</sponsorshipDate>
      </item>
      <item>
        <firstName>Tom</firstName>
        <middleName />
        <bioguideId>C001095</bioguideId>
        <isOriginalCosponsor>False</isOriginalCosponsor>
        <lastName>Cotton</lastName>
        <state>AR</state>
        <sponsorshipWithdrawnDate />
        <fullName>Sen. Cotton, Tom [R-AR]</fullName>
        <identifiers>
          <lisID>2098</lisID>
          <gpoId />
          <bioguideId>C001095</bioguideId>
        </identifiers>
        <party>R</party>
        <sponsorshipDate>2017-10-03</sponsorshipDate>
      </item>
      <item>
        <firstName>RICHARD</firstName>
        <middleName>J.</middleName>
        <bioguideId>D000563</bioguideId>
        <isOriginalCosponsor>False</isOriginalCosponsor>
        <lastName>DURBIN</lastName>
        <state>IL</state>
        <sponsorshipWithdrawnDate />
        <fullName>Sen. Durbin, Richard J. [D-IL]</fullName>
        <identifiers>
          <lisID>326</lisID>
          <bioguideId>D000563</bioguideId>
          <gpoId>8326</gpoId>
        </identifiers>
        <party>D</party>
        <sponsorshipDate>2017-10-05</sponsorshipDate>
      </item>
      <item>
        <firstName>Amy</firstName>
        <middleName />
        <bioguideId>K000367</bioguideId>
        <isOriginalCosponsor>False</isOriginalCosponsor>
        <lastName>Klobuchar</lastName>
        <state>MN</state>
        <sponsorshipWithdrawnDate />
        <fullName>Sen. Klobuchar, Amy [D-MN]</fullName>
        <identifiers>
          <bioguideId>K000367</bioguideId>
          <lisID>1826</lisID>
          <gpoId>8249</gpoId>
        </identifiers>
        <party>D</party>
        <sponsorshipDate>2017-10-05</sponsorshipDate>
      </item>
      <item>
        <firstName>Bob</firstName>
        <middleName />
        <bioguideId>C001070</bioguideId>
        <isOriginalCosponsor>False</isOriginalCosponsor>
        <lastName>Casey</lastName>
        <state>PA</state>
        <sponsorshipWithdrawnDate />
        <fullName>Sen. Casey, Robert P., Jr. [D-PA]</fullName>
        <identifiers>
          <lisID>1828</lisID>
          <gpoId>8282</gpoId>
          <bioguideId>C001070</bioguideId>
        </identifiers>
        <party>D</party>
        <sponsorshipDate>2017-10-05</sponsorshipDate>
      </item>
      <item>
        <firstName>Christopher</firstName>
        <middleName>A.</middleName>
        <bioguideId>C001088</bioguideId>
        <isOriginalCosponsor>False</isOriginalCosponsor>
        <lastName>Coons</lastName>
        <state>DE</state>
        <sponsorshipWithdrawnDate />
        <fullName>Sen. Coons, Christopher A. [D-DE]</fullName>
        <identifiers>
          <bioguideId>C001088</bioguideId>
          <lisID>1984</lisID>
          <gpoId>8297</gpoId>
        </identifiers>
        <party>D</party>
        <sponsorshipDate>2017-10-05</sponsorshipDate>
      </item>
      <item>
        <firstName>CLARENCE</firstName>
        <middleName>WILLIAM</middleName>
        <bioguideId>N000032</bioguideId>
        <isOriginalCosponsor>False</isOriginalCosponsor>
        <lastName>NELSON</lastName>
        <state>FL</state>
        <sponsorshipWithdrawnDate />
        <fullName>Sen. Nelson, Bill [D-FL]</fullName>
        <identifiers>
          <bioguideId>N000032</bioguideId>
          <gpoId>8236</gpoId>
          <lisID>859</lisID>
        </identifiers>
        <party>D</party>
        <sponsorshipDate>2017-10-05</sponsorshipDate>
      </item>
      <item>
        <firstName>Joe</firstName>
        <middleName />
        <bioguideId>M001183</bioguideId>
        <isOriginalCosponsor>False</isOriginalCosponsor>
        <lastName>Manchin</lastName>
        <state>WV</state>
        <sponsorshipWithdrawnDate />
        <fullName>Sen. Manchin, Joe, III [D-WV]</fullName>
        <identifiers>
          <lisID>1983</lisID>
          <bioguideId>M001183</bioguideId>
          <gpoId>8256</gpoId>
        </identifiers>
        <party>D</party>
        <sponsorshipDate>2017-10-05</sponsorshipDate>
      </item>
      <item>
        <firstName>Joe</firstName>
        <middleName />
        <bioguideId>D000607</bioguideId>
        <isOriginalCosponsor>False</isOriginalCosponsor>
        <lastName>Donnelly</lastName>
        <state>IN</state>
        <sponsorshipWithdrawnDate />
        <fullName>Sen. Donnelly, Joe [D-IN]</fullName>
        <identifiers>
          <bioguideId>D000607</bioguideId>
          <gpoId>7941</gpoId>
          <lisID>1850</lisID>
        </identifiers>
        <party>D</party>
        <sponsorshipDate>2017-10-05</sponsorshipDate>
      </item>
      <item>
        <firstName>Kirsten</firstName>
        <middleName>E.</middleName>
        <bioguideId>G000555</bioguideId>
        <isOriginalCosponsor>False</isOriginalCosponsor>
        <lastName>Gillibrand</lastName>
        <state>NY</state>
        <sponsorshipWithdrawnDate />
        <fullName>Sen. Gillibrand, Kirsten E. [D-NY]</fullName>
        <identifiers>
          <lisID>1866</lisID>
          <gpoId>8336</gpoId>
          <bioguideId>G000555</bioguideId>
        </identifiers>
        <party>D</party>
        <sponsorshipDate>2017-10-05</sponsorshipDate>
      </item>
      <item>
        <firstName>Todd</firstName>
        <middleName>C.</middleName>
        <bioguideId>Y000064</bioguideId>
        <isOriginalCosponsor>False</isOriginalCosponsor>
        <lastName>Young</lastName>
        <state>IN</state>
        <sponsorshipWithdrawnDate />
        <fullName>Sen. Young, Todd C. [R-IN]</fullName>
        <identifiers>
          <lisID>2019</lisID>
          <bioguideId>Y000064</bioguideId>
          <gpoId>7948</gpoId>
        </identifiers>
        <party>R</party>
        <sponsorshipDate>2017-10-05</sponsorshipDate>
      </item>
    </cosponsors>
    <billNumber>1595</billNumber>
    <billType>S</billType>
    <summaries>
      <billSummaries />
    </summaries>
    <laws />
    <policyArea>
      <name>International Affairs</name>
    </policyArea>
    <titles>
      <item>
        <titleType>(Extracted from GPO) Short Titles as Passed Senate</titleType>
        <chamberName>Senate</chamberName>
        <parentTitleType />
        <chamberCode>S</chamberCode>
        <title>Hizballah International Financing Prevention Amendments Act of 2017</title>
      </item>
      <item>
        <titleType>Short Titles as Introduced</titleType>
        <chamberName />
        <parentTitleType />
        <chamberCode />
        <title>Hizballah International Financing Prevention Amendments Act of 2017</title>
      </item>
      <item>
        <titleType>Official Title as Introduced</titleType>
        <chamberName />
        <parentTitleType />
        <chamberCode />
        <title>A bill to amend the Hizballah International Financing Prevention Act of 2015 to impose additional sanctions with respect to Hizballah, and for other purposes.</title>
      </item>
      <item>
        <titleType>Display Title</titleType>
        <chamberName />
        <parentTitleType />
        <chamberCode />
        <title>Hizballah International Financing Prevention Amendments Act of 2017</title>
      </item>
      <item>
        <titleType>(Extracted from GPO) Short Titles as Introduced</titleType>
        <chamberName />
        <parentTitleType />
        <chamberCode />
        <title>Hizballah International Financing Prevention Amendments Act of 2017</title>
      </item>
    </titles>
    <version>1.0.0</version>
    <originChamber>Senate</originChamber>
    <subjects>
      <billSubjects>
        <legislativeSubjects>
          <item>
            <name>Bank accounts, deposits, capital</name>
          </item>
          <item>
            <name>Congressional oversight</name>
          </item>
          <item>
            <name>Drug, alcohol, tobacco use</name>
          </item>
          <item>
            <name>Foreign and international banking</name>
          </item>
          <item>
            <name>Foreign property</name>
          </item>
          <item>
            <name>Fraud offenses and financial crimes</name>
          </item>
          <item>
            <name>Government information and archives</name>
          </item>
          <item>
            <name>Intelligence activities, surveillance, classified information</name>
          </item>
          <item>
            <name>Judicial review and appeals</name>
          </item>
          <item>
            <name>Middle East</name>
          </item>
          <item>
            <name>Military assistance, sales, and agreements</name>
          </item>
          <item>
            <name>Organized crime</name>
          </item>
          <item>
            <name>Political parties and affiliation</name>
          </item>
          <item>
            <name>Presidents and presidential powers, Vice Presidents</name>
          </item>
          <item>
            <name>Sanctions</name>
          </item>
          <item>
            <name>Smuggling and trafficking</name>
          </item>
          <item>
            <name>Terrorism</name>
          </item>
          <item>
            <name>War and emergency powers</name>
          </item>
        </legislativeSubjects>
        <policyArea>
          <name>International Affairs</name>
        </policyArea>
      </billSubjects>
    </subjects>
    <createDate>2017-07-21T00:56:46Z</createDate>
    <actions>
      <actionByCounts>
        <houseOfRepresentatives>2</houseOfRepresentatives>
        <senate>8</senate>
      </actionByCounts>
      <item>
        <committee />
        <actionTime>19:42:19</actionTime>
        <sourceSystem>
          2
          <name>House floor actions</name>
        </sourceSystem>
        <type>Floor</type>
        <actionCode>H15000</actionCode>
        <actionDate>2017-10-10</actionDate>
        <text>Held at the desk.</text>
        <links />
      </item>
      <item>
        <committee />
        <actionTime>14:09:00</actionTime>
        <sourceSystem>
          2
          <name>House floor actions</name>
        </sourceSystem>
        <type>Floor</type>
        <actionCode>H14000</actionCode>
        <actionDate>2017-10-10</actionDate>
        <text>Received in the House.</text>
        <links />
      </item>
      <item>
        <actionDate>2017-10-10</actionDate>
        <committee />
        <links />
        <sourceSystem>
          0
          <name>Senate</name>
        </sourceSystem>
        <text>Message on Senate action sent to the House.</text>
        <type>Floor</type>
      </item>
      <item>
        <actionDate>2017-10-05</actionDate>
        <committee />
        <links>
          <link>
            <url>https://www.congress.gov/congressional-record/volume-163/senate-section/page/S6375</url>
            <name>S6375</name>
          </link>
        </links>
        <sourceSystem>
          0
          <name>Senate</name>
        </sourceSystem>
        <text>Passed Senate with an amendment by Unanimous Consent. (consideration: CR S6375)</text>
        <type>Floor</type>
      </item>
      <item>
        <committee />
        <sourceSystem>
          9
          <name>Library of Congress</name>
        </sourceSystem>
        <type>Floor</type>
        <actionCode>17000</actionCode>
        <actionDate>2017-10-05</actionDate>
        <text>Passed/agreed to in Senate: Passed Senate with an amendment by Unanimous Consent.</text>
        <links />
      </item>
      <item>
        <actionDate>2017-10-05</actionDate>
        <committee />
        <links />
        <sourceSystem>
          0
          <name>Senate</name>
        </sourceSystem>
        <text>Measure laid before Senate by unanimous consent.</text>
        <type>Floor</type>
      </item>
      <item>
        <actionDate>2017-10-05</actionDate>
        <committee>
          <systemCode>ssbk00</systemCode>
          <name>Banking, Housing, and Urban Affairs Committee</name>
        </committee>
        <links />
        <sourceSystem>
          0
          <name>Senate</name>
        </sourceSystem>
        <text>Senate Committee on Banking, Housing, and Urban Affairs discharged by Unanimous Consent.</text>
        <type>Discharge</type>
      </item>
      <item>
        <committee>
          <systemCode>ssbk00</systemCode>
          <name>Banking, Housing, and Urban Affairs Committee</name>
        </committee>
        <sourceSystem>
          9
          <name>Library of Congress</name>
        </sourceSystem>
        <type>Committee</type>
        <actionCode>14500</actionCode>
        <actionDate>2017-10-05</actionDate>
        <text>Senate Committee on Banking, Housing, and Urban Affairs discharged by Unanimous Consent.</text>
        <links />
      </item>
      <item>
        <actionDate>2017-07-20</actionDate>
        <committee>
          <systemCode>ssbk00</systemCode>
          <name>Banking, Housing, and Urban Affairs Committee</name>
        </committee>
        <links />
        <sourceSystem>
          0
          <name>Senate</name>
        </sourceSystem>
        <text>Read twice and referred to the Committee on Banking, Housing, and Urban Affairs.</text>
        <type>IntroReferral</type>
      </item>
      <item>
        <committee />
        <sourceSystem>
          9
          <name>Library of Congress</name>
        </sourceSystem>
        <type>IntroReferral</type>
        <actionCode>10000</actionCode>
        <actionDate>2017-07-20</actionDate>
        <text>Introduced in Senate</text>
        <links />
      </item>
      <actionTypeCounts>
        <referredToCommittee>1</referredToCommittee>
        <receivedInTheHouse>1</receivedInTheHouse>
        <measureLaidBeforeSenate>1</measureLaidBeforeSenate>
        <passedSenate>1</passedSenate>
        <sentToHouse>1</sentToHouse>
        <committeeDischarged>1</committeeDischarged>
        <introducedInSenate>1</introducedInSenate>
        <passedAgreedToInSenate>1</passedAgreedToInSenate>
        <senateCommitteeDischarged>1</senateCommitteeDischarged>
        <heldAtTheDesk>1</heldAtTheDesk>
      </actionTypeCounts>
    </actions>
    <calendarNumbers />
    <sponsors>
      <item>
        <firstName>Marco</firstName>
        <middleName />
        <fullName>Sen. Rubio, Marco [R-FL]</fullName>
        <byRequestType />
        <bioguideId>R000595</bioguideId>
        <lastName>Rubio</lastName>
        <state>FL</state>
        <identifiers>
          <lisID>2084</lisID>
          <bioguideId>R000595</bioguideId>
          <gpoId>8242</gpoId>
        </identifiers>
        <party>R</party>
      </item>
    </sponsors>
  </bill>
  <dublinCore xmlns:dc="http://purl.org/dc/elements/1.1/">
    <dc:format>text/xml</dc:format>
    <dc:language>EN</dc:language>
    <dc:rights>Pursuant to Title 17 Section 105 of the United States Code, this file is not subject to copyright protection and is in the public domain.</dc:rights>
    <dc:contributor>Congressional Research Service, Library of Congress</dc:contributor>
    <dc:description>This file contains bill summaries and statuses for federal legislation. A bill summary describes the most significant provisions of a piece of legislation and details the effects the legislative text may have on current law and federal programs. Bill summaries are authored by the Congressional Research Service (CRS) of the Library of Congress. As stated in Public Law 91-510 (2 USC 166 (d)(6)), one of the duties of CRS is "to prepare summaries and digests of bills and resolutions of a public general nature introduced in the Senate or House of Representatives". For more information, refer to the User Guide that accompanies this file.</dc:description>
  </dublinCore>
</billStatus>


text:
package policy

import (
	"fmt"

	corev1 "k8s.io/api/core/v1"
	metav1 "k8s.io/apimachinery/pkg/apis/meta/v1"
	"k8s.io/pod-security-admission/api"
)

/*
Privileged Pods disable most security mechanisms and must be disallowed.

Restricted Fields:
spec.containers[*].securityContext.privileged
spec.initContainers[*].securityContext.privileged

Allowed Values: false, undefined/null
*/

func init() {
	addCheck(CheckPrivileged)
}

// CheckPrivileged returns a baseline level check
// that forbids privileged=true in 1.0+
func CheckPrivileged() Check {
	return Check{
		ID:    "privileged",
		Level: api.LevelBaseline,
		Versions: []VersionedCheck{
			{
				MinimumVersion: api.MajorMinorVersion(1, 0),
				CheckPod:       privileged_1_0,
			},
		},
	}
}

func privileged_1_0(podMetadata *metav1.ObjectMeta, podSpec *corev1.PodSpec) CheckResult {
	var badContainers []string
	visitContainers(podSpec, func(container *corev1.Container) {
		if container.SecurityContext != nil && container.SecurityContext.Privileged != nil && *container.SecurityContext.Privileged {
			badContainers = append(badContainers, container.Name)
		}
	})
	if len(badContainers) > 0 {
		return CheckResult{
			Allowed:         false,
			ForbiddenReason: "privileged",
			ForbiddenDetail: fmt.Sprintf(
				`%s %s must not set securityContext.privileged=true`,
				pluralize("container", "containers", len(badContainers)),
				joinQuote(badContainers),
			),
		}
	}
	return CheckResult{Allowed: true}
}