% misc \newcommand{\Pate}{P\^at\'e} \newcommand{\myldots}{{\everymath{}\ldots\!\!}} % for use out of math mode \newcommand{\nats}{\mathbb{N}} \newcommand{\ints}{\mathbb{Z}} \newcommand{\reals}{\mathbb{R}} \newcommand{\sizedot}{|\cdot|} % for use in \index with hyperref \newcommand{\hash}[1]{{{\sharp}#1}} % relations and binary operators \newcommand{\myiff}{\mathrel{\;\eqtxt{iff}\;}} \newcommand{\myconcat}{\mathbin{@}} \newcommand{\lparr}[1]{\stackrel{\strut#1}{\Rightarrow}} \newcommand{\tranarr}[1]{\stackrel{\strut#1}{\rightarrow}} \newcommand{\tranlongarr}[1]{\stackrel{\strut#1}{\longrightarrow}} \newcommand{\lex}{\mathrel{\triangleright}} \newcommand{\myand}{\mathbin{\mathbf{and}}} \newcommand{\myor}{\mathbin{\mathbf{or}}} \newcommand{\myimplies}{\mathbin{\mathbf{implies}}} \newcommand{\myiffbf}{\mathbin{\mathbf{iff}}} \newcommand{\iso}{\mathbin{\mathbf{iso}}} \newcommand{\pred}{\mathrel{\mathbf{pred}}} \newcommand{\size}{\mathrel{\mathbf{size}}} \newcommand{\height}{\mathrel{\mathbf{height}}} \newcommand{\length}{\mathrel{\mathbf{length}}} \newcommand{\myleft}{\mathrel{\mathbf{left}}} \newcommand{\myright}{\mathrel{\mathbf{right}}} \newcommand{\strong}{\mathrel{\mathbf{strong}}} \newcommand{\leqcc}{\mathrel{\leq_{cc}}} \newcommand{\ltcc}{\mathrel{<_{cc}}} \newcommand{\ltsimp}{\mathrel{<_{\mathbf{simp}}}} \newcommand{\leqsimp}{\mathrel{\leq_{\mathbf{simp}}}} \newcommand{\equivsimp}{\mathrel{\equiv_{\mathbf{simp}}}} \newcommand{\simp}{\mathrel{\mathbf{simp}}} \newcommand{\ltcsm}{\mathrel{<_{\mathbf{csm}}}} \newcommand{\lecsm}{\mathrel{\leq_{\mathbf{csm}}}} \newcommand{\equivcsm}{\mathrel{\equiv_{\mathbf{csm}}}} % mathematical variables \newcommand{\ns}{{\it ns}} \newcommand{\ms}{{\it ms}} \newcommand{\ls}{{\it ls}} \newcommand{\xs}{{\it xs}} \newcommand{\ys}{{\it ys}} \newcommand{\zs}{{\it zs}} \newcommand{\xss}{{\it xss}} \newcommand{\yss}{{\it yss}} \newcommand{\myexp}{{\it exp}} \newcommand{\tr}{{\it tr}} \newcommand{\trs}{{\it trs}} \newcommand{\pat}{{\it pat}} \newcommand{\lp}{{\it lp}} \newcommand{\pd}{{\it pd}} \newcommand{\code}{{\it code}} \newcommand{\pt}{{\it pt}} \newcommand{\pts}{{\it pts}} \newcommand{\Simp}{{\it simp}} \newcommand{\Sub}{{\it sub}} \newcommand{\acc}{\mathit{acc}} \newcommand{\mach}{\mathit{mach}} \newcommand{\aft}{\mathit{aft}} \newcommand{\rel}{\mathit{rel}} \newcommand{\bs}{\mathit{bs}} \newcommand{\cs}{\mathit{cs}} \newcommand{\pr}{\mathit{pr}} \newcommand{\progoper}{\mathit{oper}} \newcommand{\progcon}{\mathit{con}} % symbols \newcommand{\zerosf}{\mathsf{0}} \newcommand{\onesf}{\mathsf{1}} \newcommand{\twosf}{\mathsf{2}} \newcommand{\threesf}{\mathsf{3}} \newcommand{\foursf}{\mathsf{4}} \newcommand{\fivesf}{\mathsf{5}} \newcommand{\sixsf}{\mathsf{6}} \newcommand{\asf}{\mathsf{a}} \newcommand{\bsf}{\mathsf{b}} \newcommand{\csf}{\mathsf{c}} \newcommand{\dsf}{\mathsf{d}} \newcommand{\Asf}{\mathsf{A}} \newcommand{\Bsf}{\mathsf{B}} \newcommand{\Csf}{\mathsf{C}} \newcommand{\Dsf}{\mathsf{D}} \newcommand{\Esf}{\mathsf{E}} \newcommand{\Fsf}{\mathsf{F}} \newcommand{\Gsf}{\mathsf{G}} \newcommand{\Hsf}{\mathsf{H}} \newcommand{\Isf}{\mathsf{I}} \newcommand{\Jsf}{\mathsf{J}} \newcommand{\Ksf}{\mathsf{K}} \newcommand{\Lsf}{\mathsf{L}} \newcommand{\Msf}{\mathsf{M}} \newcommand{\Nsf}{\mathsf{N}} \newcommand{\Osf}{\mathsf{O}} \newcommand{\Psf}{\mathsf{P}} \newcommand{\Qsf}{\mathsf{Q}} \newcommand{\Rsf}{\mathsf{R}} \newcommand{\Ssf}{\mathsf{S}} \newcommand{\Tsf}{\mathsf{T}} \newcommand{\Usf}{\mathsf{U}} \newcommand{\Vsf}{\mathsf{V}} \newcommand{\Wsf}{\mathsf{W}} \newcommand{\Xsf}{\mathsf{X}} \newcommand{\Ysf}{\mathsf{Y}} \newcommand{\Zsf}{\mathsf{Z}} \newcommand{\Zero}{\langle\zerosf\rangle} \newcommand{\One}{\langle\onesf\rangle} \newcommand{\Two}{\langle\twosf\rangle} \newcommand{\dead}{\langle\mathsf{dead}\rangle} \newcommand{\newlinesym}{\mathsf{\langle newline\rangle}} \newcommand{\spacesym}{\mathsf{\langle space\rangle}} \newcommand{\plussym}{{\langle\mathsf{plus}\rangle}} \newcommand{\timessym}{{\langle\mathsf{times}\rangle}} \newcommand{\openparsym}{{\langle\mathsf{openPar}\rangle}} \newcommand{\closparsym}{{\langle\mathsf{closPar}\rangle}} \newcommand{\idsym}{{\langle\mathsf{id}\rangle}} \newcommand{\commasym}{{\langle\mathsf{comma}\rangle}} \newcommand{\percsym}{{\langle\mathsf{perc}\rangle}} \newcommand{\mytildesym}{{\langle\mathsf{tilde}\rangle}} \newcommand{\lesssym}{{\langle\mathsf{less}\rangle}} \newcommand{\greatsym}{{\langle\mathsf{great}\rangle}} % program constructors \newcommand{\progapp}{\mathbf{app}} \newcommand{\progcalc}{\mathbf{calc}} \newcommand{\progcond}{\mathbf{cond}} \newcommand{\progconst}{\mathbf{const}} \newcommand{\progint}{\mathbf{int}} \newcommand{\proglam}{\mathbf{lam}} \newcommand{\progletRec}{\mathbf{letRec}} \newcommand{\progletSimp}{\mathbf{letSimp}} \newcommand{\progpair}{\mathbf{pair}} \newcommand{\progstr}{\mathbf{str}} \newcommand{\progsym}{\mathbf{sym}} \newcommand{\progvar}{\mathbf{var}} % program constants \newcommand{\prognil}{\mathsf{nil}} \newcommand{\progtrue}{\mathsf{true}} \newcommand{\progfalse}{\mathsf{false}} % program operators \newcommand{\progcompare}{\mathsf{compare}} \newcommand{\progconsSym}{\mathsf{consSym}} \newcommand{\progdeconsSym}{\mathsf{deconsSym}} \newcommand{\progfst}{\mathsf{fst}} \newcommand{\progisInt}{\mathsf{isInt}} \newcommand{\progisLam}{\mathsf{isLam}} \newcommand{\progisNeg}{\mathsf{isNeg}} \newcommand{\progisNil}{\mathsf{isNil}} \newcommand{\progisPair}{\mathsf{isPair}} \newcommand{\progisPos}{\mathsf{isPos}} \newcommand{\progisStr}{\mathsf{isStr}} \newcommand{\progisSym}{\mathsf{isSym}} \newcommand{\progisZero}{\mathsf{isZero}} \newcommand{\progminus}{\mathsf{minus}} \newcommand{\progplus}{\mathsf{plus}} \newcommand{\progsnd}{\mathsf{snd}} \newcommand{\progstrToSymList}{\mathsf{strToSymList}} \newcommand{\progsymListToStr}{\mathsf{symListToStr}} % defined names \newcommand{\AWS}{\mathbf{AWS}} \newcommand{\AllLongStutter}{\mathbf{AllLongStutter}} \newcommand{\AllPrefixGood}{\mathbf{AllPrefixGood}} \newcommand{\AllSubstringGood}{\mathbf{AllSubstringGood}} \newcommand{\Alp}{\mathbf{Alp}} \newcommand{\Bool}{\mathbf{Bool}} \newcommand{\CC}{\mathbf{CC}} \newcommand{\CFLan}{\mathbf{CFLan}} \newcommand{\CP}{\mathbf{CP}} \newcommand{\Char}{\mathbf{Char}} \newcommand{\DFA}{\mathbf{DFA}} \newcommand{\EFA}{\mathbf{EFA}} \newcommand{\Eval}{\mathbf{Eval}} \newcommand{\FA}{\mathbf{FA}} \newcommand{\Gram}{\mathbf{Gram}} \newcommand{\JOIN}{\mathbf{Join}} \newcommand{\LP}{\mathbf{LP}} \newcommand{\Lan}{\mathbf{Lan}} \newcommand{\List}{\mathbf{List}} \newcommand{\LongAndNotStutter}{\mathbf{LongAndNotStutter}} \newcommand{\Long}{\mathbf{Long}} \newcommand{\NFA}{\mathbf{NFA}} \newcommand{\NotStutter}{\mathbf{NotStutter}} \newcommand{\Option}{\mathbf{Option}} \newcommand{\PT}{\mathbf{PT}} \newcommand{\Path}{\mathbf{Path}} \newcommand{\ProgConst}{\mathbf{Const}} \newcommand{\ProgLab}{\mathbf{ProgLab}} \newcommand{\ProgOper}{\mathbf{Oper}} \newcommand{\ProgVar}{\mathbf{Var}} \newcommand{\Prog}{\mathbf{Prog}} \newcommand{\RELan}{\mathbf{RELan}} \newcommand{\RFA}{\mathbf{RFA}} \newcommand{\RecLan}{\mathbf{RecLan}} \newcommand{\Rec}{\mathbf{Rec}} \newcommand{\RegLab}{\mathbf{RegLab}} \newcommand{\RegLan}{\mathbf{RegLan}} \newcommand{\Reg}{\mathbf{Reg}} \newcommand{\Rep}{\mathbf{Rep}} \newcommand{\Run}{\mathbf{Run}} \newcommand{\SSop}{\mathit{SS}} \newcommand{\SomeLongNotStutter}{\mathbf{SomeLongNotStutter }} \newcommand{\Step}{\mathbf{Step}} \newcommand{\Str}{\mathbf{Str}} \newcommand{\Stutter}{\mathbf{Stutter}} \newcommand{\Sym}{\mathbf{Sym}} \newcommand{\Tree}{\mathbf{Tree}} \newcommand{\Valid}{\mathbf{Valid}} \newcommand{\Val}{\mathbf{Val}} \newcommand{\WS}{\mathbf{WS}} \newcommand{\allLongStutterDFA}{\mathbf{allLongStutterDFA}} \newcommand{\allPrefixGoodDFA}{\mathbf{allPrefixGoodDFA}} \newcommand{\allStrDFA}{\mathbf{allStrDFA}} \newcommand{\allStrEFA}{\mathbf{allStrEFA}} \newcommand{\allStrReg}{\mathbf{allStrReg}} \newcommand{\allStr}{\mathbf{allStr}} \newcommand{\allSubstringGoodDFA}{\mathbf{allSubstringGoodDFA}} \newcommand{\allSym}{\mathbf{allSym}} \newcommand{\alphabet}{\mathbf{alphabet}} \newcommand{\ans}{\mathbf{ans}} \newcommand{\any}{[\mathbf{any}]} \newcommand{\csm}{\mathbf{csm}} \newcommand{\calculate}{\mathbf{calculate}} \newcommand{\cc}{\mathbf{cc}} \newcommand{\closure}{\mathbf{closure}} \newcommand{\combineTrans}{\mathbf{combineTrans}} \newcommand{\concatsToList}{\mathbf{concatsToList}} \newcommand{\concat}{\mathbf{concat}} \newcommand{\deepClosure}{\mathbf{deepClosure}} \newcommand{\deepConcat}{\mathbf{deepConcat}} \newcommand{\deepUnion}{\mathbf{deepUnion}} \newcommand{\determSimplify}{\mathbf{determSimplify}} \newcommand{\diff}{\mathbf{diff}} \newcommand{\digit}{[\mathbf{digit}]} \newcommand{\domain}{\mathbf{domain}} \newcommand{\efaToDFA}{\mathbf{efaToDFA}} \newcommand{\efaToNFA}{\mathbf{efaToNFA}} \newcommand{\eliminateState}{\mathbf{eliminateState}} \newcommand{\emptyCloseBackwards}{\mathbf{emptyCloseBackwards}} \newcommand{\emptyClose}{\mathbf{emptyClose}} \newcommand{\emptySet}{\mathbf{emptySet}} \newcommand{\emptyStr}{\mathbf{emptyStr}} \newcommand{\error}{\mathbf{error}} \newcommand{\eval}{\mathbf{eval}} \newcommand{\faToGram}{\mathbf{faToGram}} \newcommand{\faToEFA}{\mathbf{faToEFA}} \newcommand{\faToRFA}{\mathbf{faToRFA}} \newcommand{\faToReg}{\mathbf{faToReg}} \newcommand{\fail}{\mathbf{fail}} \newcommand{\false}{\mathbf{false}} \newcommand{\findIso}{\mathbf{findIso}} \newcommand{\free}{\mathbf{free}} \newcommand{\genConcat}{\mathbf{genConcat}} \newcommand{\genUnion}{\mathbf{genUnion}} \newcommand{\globallySimplified}{\mathbf{globallySimplified}} \newcommand{\globallySimplify}{\mathbf{globallySimplify}} \newcommand{\haltsOn}{\mathit{haltsOn}} \newcommand{\halts}{\mathit{halts}} \newcommand{\hasEmp}{\mathbf{hasEmp}} \newcommand{\hasSym}{\mathbf{hasSym}} \newcommand{\id}{\mathbf{id}} \newcommand{\intermed}{\mathbf{intermed}} \newcommand{\inter}{\mathbf{inter}} \newcommand{\join}{\mathbf{join}} \newcommand{\letter}{[\mathbf{letter}]} \newcommand{\locallySimplified}{\mathbf{locallySimplified}} \newcommand{\locallySimplify}{\mathbf{locallySimplify}} \newcommand{\longAndNotStutterDFA}{\mathbf{longAndNotStutterDFA}} \newcommand{\longAndNotStutterEFA}{\mathbf{longAndNotStutterEFA}} \newcommand{\longDFA}{\mathbf{longDFA}} \newcommand{\longReg}{\mathbf{longReg}} \newcommand{\minAndRen}{\mathbf{minAndRen}} \newcommand{\minimize}{\mathbf{minimize}} \newcommand{\minus}{\mathbf{minus}} \newcommand{\mycomplement}{\mathbf{complement}} \newcommand{\myendState}{\mathbf{endState}} \newcommand{\myheight}{\mathbf{height}} \newcommand{\mylabel}{\mathbf{label}} \newcommand{\mynot}{\mathbf{not}} \newcommand{\mysize}{\mathbf{size}} \newcommand{\myvalue}{\mathbf{value}} \newcommand{\nextEmp}{\mathbf{nextEmp}} \newcommand{\nextSym}{\mathbf{nextSym}} \newcommand{\next}{\mathbf{next}} \newcommand{\nfaToDFA}{\mathbf{nfaToDFA}} \newcommand{\none}{\mathbf{none}} \newcommand{\nonterm}{\mathbf{nonterm}} \newcommand{\norm}{\mathbf{norm}} \newcommand{\notStutterDFA}{\mathbf{notStutterDFA}} \newcommand{\numConcats}{\mathbf{numConcats}} \newcommand{\numLeaves}{\mathbf{numLeaves}} \newcommand{\numSyms}{\mathbf{numSyms}} \newcommand{\obviSub}{\mathbf{obviSub}} \newcommand{\obviousSubset}{\mathbf{obviousSubset}} \newcommand{\ord}{\mathbf{ord}} \newcommand{\parELoop}{\mathbf{parELoop}} \newcommand{\parE}{\mathbf{parE}} \newcommand{\parF}{\mathbf{parF}} \newcommand{\parTLoop}{\mathbf{parTLoop}} \newcommand{\parT}{\mathbf{parT}} \newcommand{\pow}{\mathbf{pow}} \newcommand{\prefix}{\mathbf{prefix}} \newcommand{\pre}{\mathbf{pre}} \newcommand{\range}{\mathbf{range}} \newcommand{\reachify}{\mathbf{reachify}} \newcommand{\regToDFA}{\mathbf{regToDFA}} \newcommand{\regToEFA}{\mathbf{regToEFA}} \newcommand{\regToFA}{\mathbf{regToFA}} \newcommand{\regToGram}{\mathbf{regToGram}} \newcommand{\regToNFA}{\mathbf{regToNFA}} \newcommand{\remRedun}{\mathbf{remRedun}} \newcommand{\renameAlphabet}{\mathbf{renameAlphabet}} \newcommand{\renameStatesCanonically}{\mathbf{renameStatesCanonically}} \newcommand{\renameStates}{\mathbf{renameStates}} \newcommand{\renameVariablesCanonically}{\mathbf{renameVariablesCanonically}} \newcommand{\renameVariables}{\mathbf{renameVariables}} \newcommand{\rev}{\mathbf{rev}} \newcommand{\rfaToReg}{\mathbf{rfaToReg}} \newcommand{\rightConcat}{\mathbf{rightConcat}} \newcommand{\rightUnion}{\mathbf{rightUnion}} \newcommand{\rootLabel}{\mathbf{rootLabel}} \newcommand{\run}{\mathbf{run}} \newcommand{\select}{\mathbf{select}} \newcommand{\shiftClosuresRight}{\mathbf{shiftClosuresRight}} \newcommand{\simplified}{\mathbf{simplified}} \newcommand{\simplify}{\mathbf{simplify}} \newcommand{\someLongNotStutterDFA}{\mathbf{someLongNotStutterDFA}} \newcommand{\someLongNotStutterEFA}{\mathbf{someLongNotStutterEFA}} \newcommand{\some}{\mathbf{some}} \newcommand{\sortUnions}{\mathbf{sortUnions}} \newcommand{\standardize}{\mathbf{standardize}} \newcommand{\startState}{\mathbf{startState}} \newcommand{\state}{\mathbf{state}} \newcommand{\stdRFAToReg}{\mathbf{stdRFAToReg}} \newcommand{\step}{\mathbf{step}} \newcommand{\strToFA}{\mathbf{strToFA}} \newcommand{\strToGram}{\mathbf{strToGram}} \newcommand{\strToReg}{\mathbf{strToReg}} \newcommand{\stutterDFA}{\mathbf{stutterDFA}} \newcommand{\stutterReg}{\mathbf{stutterReg}} \newcommand{\substring}{\mathbf{substring}} \newcommand{\subst}{\mathbf{subst}} \newcommand{\suffix}{\mathbf{suffix}} \newcommand{\symToNFA}{\mathbf{symToNFA}} \newcommand{\symToGram}{\mathbf{symToGram}} \newcommand{\symToReg}{\mathbf{symToReg}} \newcommand{\true}{\mathbf{true}} \newcommand{\unionsToList}{\mathbf{unionsToList}} \newcommand{\union}{\mathbf{union}} \newcommand{\update}{\mathbf{update}} \newcommand{\validPaths}{\mathbf{validPaths}} \newcommand{\valid}{\mathbf{valid}} \newcommand{\weaklySimplified}{\mathbf{weaklySimplified}} \newcommand{\weaklySimplify}{\mathbf{weaklySimplify}} \newcommand{\yield}{\mathbf{yield}} \newcommand{\zeros}{\mathbf{zeros}}