#! /bin/sh
# This is a shell archive, meaning:
# 1. Remove everything above the #! /bin/sh line.
# 2. Save the resulting text in a file.
# 3. Execute the file with /bin/sh (not csh) to create the files:
# KWRmacs.tex
# KWRstyle.sty
# LNall.tex
# LNall.aux
# LNall.bbl
# LNall.blg
# This archive created: Wed Jan 5 16:14:58 1994
export PATH; PATH=/bin:$PATH
if test -f 'KWRmacs.tex'
then
echo shar: will not over-write existing file "'KWRmacs.tex'"
else
cat << \SHAR_EOF > 'KWRmacs.tex'
\newcommand{\newfontobj}[2]{
\newcommand{#1}[1]{
\expandafter\def\csname##1\endcsname{{#2 ##1}}}}
\newfontobj{\class}{\rm}
\class{P}
\class{UP}
\class{NP}
\class{PH}
\class{EXP}
\class{NEXP}
\class{PSPACE}
\class{PSpace}
\class{NPSPACE}
\class{RE}
\class{Ptime}
\class{Pspace}
\class{BPP}
\class{BPPtime}
\class{RP}
\class{ZPP}
\class{AM}
\class{MA}
\class{PP}
\class{coNP}
\class{coAM}
\class{coRP}
\class{MP}
% \class{CP}
\class{FewP}
\class{Few}
\class{PF}
\class{FP}
\class{REG}
\class{CFL}
\class{DCFL}
\class{REC}
\class{RE}
\class{CSL}
\class{DCSL}
\class{NCSL}
\class{TLIN}
\class{NTLIN}
\class{2DPDA}
\class{AC}
\class{NC}
\class{BC}
\class{SC}
\class{DLOG}
\class{NLOG}
\class{DLOGTIME}
\class{NLOGTIME}
\class{ALOGTIME}
\class{ATISP}
\class{DLIN}
\class{NLIN}
\class{NLT}
\class{DNLT}
\class{NNLT}
\class{NQL}
\class{QL}
\class{DQL}
\class{BQL}
\class{RQL}
\class{PQL}
\class{UQL}
\class{QLH}
\class{QLSPACE}
\class{CFA}
\class{CFR}
\class{Con}
\class{LOGSPACE}
\class{L}
\class{FL}
\class{ACC}
\class{NL}
\class{SSM}
\class{DGSM}
\class{BM}
\class{VM}
\class{CREW}
\class{EREW}
\class{CRCW}
\class{NPMV}
\class{NPSV}
\class{BPSV}
\class{BPMV}
\class{ZPMV}
\class{ZPSV}
\class{NNSV}
\class{NNMV}
\class{RPSV}
\class{RPMV}
% \class{PRSV}
% \class{PRMV}
% \class{PPMV}
% \class{PPSV}
\class{GapP}
\class{PrMV}
\class{PrSV}
\class{FO}
\class{SF}
\class{FOL}
\class{LOGH}
\class{LINH}
\class{RUD}
\class{LBR}
\newcommand{\PrtwoV}{\mbox{\rm PR2V}}
\newcommand{\NPtwoV}{\mbox{\rm NP2V}}
\newcommand{\BPtwoV}{\mbox{\rm BP2V}}
% The following is a terrible hack, but it works---usually.
\newcommand{\parityP}{{\mathchoice{\raisebox{1pt}{$\displaystyle\oplus$}{\rm
P}}{\raisebox{1pt}{$\textstyle\oplus$}{\rm
P}}{\raisebox{1pt}{$\scriptstyle\oplus$}{\rm
P}}{\raisebox{1pt}{$\scriptscriptstyle\oplus$}{\rm P}}}}
\newcommand{\parityQL}{{\mathchoice{\raisebox{1pt}{$\displaystyle\oplus$}{\rm
QL}}{\raisebox{1pt}{$\textstyle\oplus$}{\rm
QL}}{\raisebox{1pt}{$\scriptstyle\oplus$}{\rm
QL}}{\raisebox{1pt}{$\scriptscriptstyle\oplus$}{\rm QL}}}}
% Ditto for Number-P --KWR
\newcommand{\numberP}{{\mathchoice{\raisebox{1pt}
{$\displaystyle\#$}{\rm P}}{\raisebox{1pt}
{$\textstyle\#$}{\rm P}}{\raisebox{1pt}
{$\scriptstyle\#$}{\rm P}}{\raisebox{1pt}
{$\scriptscriptstyle\#$}{\rm P}}}}
% And C-parity-P:
\newcommand{\CparityP}{{\rm C}\parityP}
% And C=P:
\newcommand{\cep}{\mbox{{\rm C}$_=${\rm P}}}
%
%\newcommand{\cep} {C\!\!\!\!=\!\!\!P}
\newfontobj{\lang}{\it}
\lang{SAT}
\lang{QBF}
\lang{HAM}
\lang{CLIQUE}
\newfontobj{\func}{\it}
\func{sat}
\func{op}
\func{Ran}
\func{Dom}
\func{Supp}
\func{Graph}
\func{Subgraph}
\func{Prefs}
\func{Code}
\func{ran}
\func{dom}
\func{graph}
\func{maj}
\func{subgraph}
\func{prefs}
\func{wt}
\func{Perm}
\func{Det}
\func{NAND}
\func{NOR}
\func{nand}
\func{nor}
\func{UE}
\func{ue}
\func{normal}
\func{prim}
\func{PLUS}
\func{BIT}
\func{Mask}
\func{EQ}
\func{BSUM}
\func{Pos}
\func{Min}
\func{Max}
\newfontobj{\type}{\tt}
\type{String}
\type{Strings}
\type{Char}
\type{Chars}
\type{Bool}
\type{Event}
\type{Events}
\type{Language}
\type{Languages}
\type{Class}
\type{Classes}
\type{Hierarchy}
\type{Hierarchies}
\newfontobj{\machine}{\rm}
\machine{TM}
\machine{NTM}
\machine{DTM}
\machine{PDA}
\machine{DPDA}
\machine{NPDA}
\machine{NFA}
\machine{DFA}
\machine{FA}
\machine{HDFA}
\machine{kHDFA}
\machine{LBA}
\machine{DLBA}
\machine{NLBA}
\machine{CFG}
\machine{CSG}
\newcommand{\cfatime}{\mbox{CFA-TIME}}
% Polynomial hierarchy stuff
\newcommand{\Skp}{\Sigma_k^p}
\newcommand{\Pkp}{\Pi_k^p}
\newcommand{\Dkp}{\Delta_k^p}
\newcommand{\Skql}{\Sigma_k^{ql}}
\newcommand{\Pkql}{\Pi_k^{ql}}
\newcommand{\Dkql}{\Delta_k^{ql}}
\newcommand{\Sql}{\Sigma^{ql}}
\newcommand{\Pql}{\Pi^{ql}}
\newcommand{\Dql}{\Delta^{ql}}
% This is the old definition.
% \newcommand{\parityP}{\raisebox{1pt}{$\oplus$}{\rm P}}
\newcommand{\CA}{{\cal A}}
\newcommand{\CB}{{\cal B}}
\newcommand{\CC}{{\cal C}}
\newcommand{\CD}{{\cal D}}
\newcommand{\CE}{{\cal E}}
\newcommand{\CF}{{\cal F}}
\newcommand{\CG}{{\cal G}}
\newcommand{\CH}{{\cal H}}
\newcommand{\CI}{{\cal I}}
\newcommand{\CJ}{{\cal J}}
\newcommand{\CK}{{\cal K}}
\newcommand{\CL}{{\cal L}}
\newcommand{\CM}{{\cal M}}
\newcommand{\CN}{{\cal N}}
\newcommand{\CO}{{\cal O}}
\newcommand{\CP}{{\cal P}}
\newcommand{\CQ}{{\cal Q}}
\newcommand{\CR}{{\cal R}}
\newcommand{\CS}{{\cal S}}
\newcommand{\CT}{{\cal T}}
\newcommand{\CU}{{\cal U}}
\newcommand{\CV}{{\cal V}}
\newcommand{\CW}{{\cal W}}
\newcommand{\CX}{{\cal X}}
\newcommand{\CY}{{\cal Y}}
\newcommand{\CZ}{{\cal Z}}
\newcommand{\rma}{\mbox{a}}
\newcommand{\rmb}{\mbox{b}}
\newcommand{\rmD}{\mbox{D}}
\newcommand{\rmR}{\mbox{R}}
\newcommand{\rmS}{\mbox{S}}
\newcommand{\rmL}{\mbox{L}}
\newcommand{\co}{{\hbox{co-}}}
% ENVIRONMENTS FOR RESULTS, DEFINITIONS, EXAMPLES, and OPEN PROBLEMS
% Results, definitions, and examples are numbered /by section/.
% Open problems are numbered for the entire paper.
% Conventions are counted as definitions;
% conjectures are counted as open problems.
% "\newdefinition" is an add-on by Stuart Kurtz which behaves like
% \newtheorem but doesn't italicize the text body.
\newtheorem{theorem}{Theorem}[section]
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{mainrobustnesstheorem}[theorem]{Main Robustness Theorem}
\newtheorem{robustnesstheorem}[theorem]{Robustness Theorem}
\newtheorem{claim}[theorem]{Claim}
\newdefinition{definition}{Definition}[section]
% \newdefinition{definition}{Definition}[lecnum]
\newdefinition{convention}[definition]{Convention}
\newdefinition{example}{Example}[section]
\newdefinition{openproblem}{Open Problem}
\newdefinition{conjecture}[openproblem]{Conjecture}
\newenvironment{theorem*}{\sl \begin{trivlist}
\item[]{\bf Theorem.\enspace}}{\end{trivlist}}
\newenvironment{proposition*}{\sl \begin{trivlist}
\item[]{\bf Proposition.\enspace}}{\end{trivlist}}
\newenvironment{counterexample*}{\sl \begin{trivlist}
\item[]{\bf Counterexample.\enspace}}{\end{trivlist}}
\newenvironment{convention*}{\sl \begin{trivlist}
\item[]{\bf Convention.\enspace}}{\end{trivlist}}
\newenvironment{claim*}{\sl begin{trivlist}
\item[]{\bf Claim.\enspace}}{\end{trivlist}}
\newenvironment{problem}{\sl \begin{trivlist}
\item[]{\bf Problem.\enspace}}{\end{trivlist}}
\newenvironment{notation}{\it \begin{trivlist}
\item[]{Notation.\enspace}}{\end{trivlist}}
\newenvironment{note}{\unskip\footnote\bgroup\ignorespaces}{\egroup}
\newenvironment{construction}{\bigbreak\begin{block}}{\end{block}
\bigbreak}
\newenvironment{block}{\begin{list}{\hbox{}}{\leftmargin 1em
\itemindent -1em \topsep 0pt \itemsep 0pt \partopsep 0pt}}{\end{list}}
\newenvironment{Adjust}[1]{\begin{list}{\hbox{}}{\leftmargin #1
\topsep 0pt \itemsep 0pt \partopsep 0pt}}{\end{list}}
\newcommand{\thinbar}{\rule{\textwidth}{0.015in}}
\newenvironment{Comment}{\vspace{-2.5ex}\begin{trivlist}
\item[]\thinbar\vspace{-2ex}
\item[]\sl}{\nopagebreak[4]\vspace{-2.5ex}\item[]
\thinbar\end{trivlist}}
\newcommand{\topic}[1]{\medskip\noindent{\bf #1}}
\newcommand{\stub}[1]{\typeout{*** Stub! ***}
$\langle${\bf Stub:} {\em #1}$\rangle$}
\newcommand{\Strut}[1]{\rule{0pt}{#1}}
\newcommand{\restrict}{\mathclose{\mid}}
\newcommand{\restricted}[1]{\restrict_{#1}}
\newcommand{\symdiff}{\bigtriangleup}
% \newcommand{\diff}{\backslash}
\newcommand{\eqq}{\stackrel{?}{=}}
\newcommand{\neqq}{\stackrel{?}{{\neq}}}
\newcommand{\range}[1]{{\rm range}(#1)}
\newcommand{\domain}[1]{{\rm domain}(#1)}
\newcommand{\supp}{\mbox{\it L\/}}
\newcommand{\fnAND}{\mbox{\it AND\/}}
\newcommand{\fnOR}{\mbox{\it OR\/}}
\newcommand{\fnor}{\mbox{\it or\/}}
\newcommand{\fnand}{\mbox{\it and\/}}
\newcommand{\noteq}{\neq}
\newcommand{\compl}[1]{\overline{#1}}
\newcommand{\set}[1]{\{\,#1\,\}}
\newcommand{\setf}{\mbox{\it set-$f$}}
\newcommand{\setg}{\mbox{\it set-$g$}}
\newcommand{\pair}[1]{\mathopen{\langle}#1\mathclose{\rangle}}
\newcommand{\tuple}[1]{\mathopen{\langle}#1\mathclose{\rangle}}
\newcommand{\PAIR}[1]{{\langle}#1{\rangle}}
\newcommand{\floor}[1]{\lfloor#1\rfloor}
\newcommand{\ceiling}[1]{\lceil #1\rceil}
\newcommand{\Ahat}{\widehat{A}}
\newcommand{\Bhat}{\widehat{B}}
\newcommand{\Rhat}{\widehat{R}}
\newcommand{\prob}{{\rm Pr}}
\newcommand{\Prob}{{\rm Prob}}
\renewcommand{\Pr}{{\rm Pr}}
\newcommand{\Cmpl}{\mathbin{\hbox{\rule[0.5ex]{0.6em}{0.25ex}}}}
\newcommand{\predicate}[1]{\mathopen{\lbrack\!\lbrack} #1
\mathclose{\rbrack\!\rbrack}}
\newcommand{\BPQ}[1]{\BP{\kern -2pt}_{#1}\,}
\newcommand{\parity}{\oplus}
\newcommand{\odd}{\oplus^+}
\newcommand{\even}{\oplus^-}
\newcommand{\oddeven}{\oplus^{\pm}}
\newcommand{\evenodd}{\oplus^{\mp}}
\newcommand{\BP}{{\rm BP}}
\newcommand{\Count}{{\rm C}}
\newcommand{\ZP}{{\rm ZP}}
\newcommand{\Rplus}{{\rm R}^+}
\newcommand{\Rminus}{{\rm R}^-}
\newcommand{\Rpm}{{\rm R}^{\pm}}
\newcommand{\Rmp}{{\rm R}^{\mp}}
\newcommand{\sizedepth}{\hbox{SIZE-DEPTH}}
\newcommand{\twodpda}{\hbox{2DPDA}}
\newcommand{\RAMLIN}{\mbox{{\rm RAM-LIN}}}
\newcommand{\ramlin}{\RAMLIN}
\newcommand{\DRAMLIN}{\mbox{{\rm DRAM-LIN}}}
\newcommand{\dramlin}{\DRAMLIN}
\newcommand{\NRAMLIN}{\mbox{{\rm NRAM-LIN}}}
\newcommand{\nramlin}{\NRAMLIN}
\newcommand{\RAMTIME}{\mbox{{\rm RAM-TIME}}}
\newcommand{\BRAMTIME}{\mbox{{\rm BRAM-TIME}}}
\newcommand{\SRAMTIME}{\mbox{{\rm SRAM-TIME}}}
\newcommand{\ramtime}{\RAMTIME}
\newcommand{\ramtmtime}{\mbox{{\rm RAM-TM-TIME}}}
\newcommand{\ramlogtime}{\RAMTIME^{\log}}
\newcommand{\TC}{\mbox{\rm TC}}
\newcommand{\TCTIME}{\mbox{\rm TC-TIME}}
\newcommand{\DSPACE}{\hbox{\rm DSPACE}}
\newcommand{\NSPACE}{\hbox{\rm NSPACE}}
\newcommand{\TIME}{\hbox{\rm TIME}}
\newcommand{\DTIME}{\hbox{\rm DTIME}}
\newcommand{\NTIME}{\hbox{\rm NTIME}}
\newcommand{\ATIME}{\hbox{\rm ATIME}}
\newcommand{\dmutime}{\mbox{{\rm D}$\mu${\rm TIME}}}
\newcommand{\nmutime}{\mbox{{\rm N}$\mu${\rm TIME}}}
\newcommand{\dmudtime}{\mbox{{\rm D}$\mu_d${\rm TIME}}}
\newcommand{\nmudtime}{\mbox{{\rm N}$\mu_d${\rm TIME}}}
\newcommand{\dmulogtime}{\mbox{{\rm D}$\mu_{\log}${\rm TIME}}}
\newcommand{\nmulogtime}{\mbox{{\rm N}$\mu_{\log}${\rm TIME}}}
\newcommand{\dmuzerotime}{\mbox{{\rm D}$\mu_0${\rm TIME}}}
\newcommand{\nmuzerotime}{\mbox{{\rm N}$\mu_0${\rm TIME}}}
\newcommand{\dmuonetime}{\mbox{{\rm D}$\mu_1${\rm TIME}}}
\newcommand{\nmuonetime}{\mbox{{\rm N}$\mu_1${\rm TIME}}}
\newcommand{\dmutwotime}{\mbox{{\rm D}$\mu_2${\rm TIME}}}
\newcommand{\dmuthreetime}{\mbox{{\rm D}$\mu_3${\rm TIME}}}
\newcommand{\mulog}{\mbox{$\mu_{\log}$}}
\newcommand{\mutime}{\mbox{$\mu$-{\it time\/}}}
\newcommand{\mudtime}{\mbox{$\mu_d$-{\it time\/}}}
\newcommand{\mulogtime}{\mbox{$\mu_{\log}$-{\it time\/}}}
\newcommand{\muacc}{\mbox{$\mu$-{\it acc\/}}}
\newcommand{\mudacc}{\mbox{$\mu_d$-{\it acc\/}}}
\newcommand{\mulogacc}{\mbox{$\mu_{\log}$-{\it acc\/}}}
\newcommand{\muoneacc}{\mbox{$\mu_1$-{\it acc\/}}}
\newcommand{\code}{\mbox{\it code\/}}
\newcommand{\qlin}{\mbox{\it qlin\/}}
\newcommand{\lin}{\mbox{\it lin\/}}
\newcommand{\difce}{\mbox{\it diff\/}}
\newcommand{\loglog}{\log\!\log}
% \newcommand{\ACCEPT}{\mbox{A{\footnotesize CCEPT}}}
% \newcommand{\REJECT}{\mbox{R{\footnotesize EJECT}}}
% \newcommand{\HALT}{\mbox{H{\footnotesize ALT}}}
% \newcommand{\goUP}{\mbox{U{\footnotesize P}}}
% \newcommand{\DOWNRIGHT}{\mbox{D{\footnotesize OWN} R{\footnotesize IGHT}}}
% \newcommand{\DOWNLEFT}{\mbox{D{\footnotesize OWN} L{\footnotesize EFT}}}
% \newcommand{\PULL}{\mbox{P{\footnotesize ULL}}}
% \newcommand{\PUT}{\mbox{P{\footnotesize UT}}}
% \newcommand{\DOWN}{\mbox{D{\footnotesize OWN}}}
% \newcommand{\RIGHT}{\mbox{R{\footnotesize IGHT}}}
% \newcommand{\LEFT}{\mbox{L{\footnotesize EFT}}}
\newcommand{\ACCEPT}{{\mbox{\sc Accept}}}
\newcommand{\REJECT}{{\mbox{\sc Reject}}}
\newcommand{\HALT}{{\mbox{\sc Halt}}}
\newcommand{\goUP}{{\mbox{\sc Up}}}
\newcommand{\DOWNRIGHT}{{\mbox{\sc Down Right}}}
\newcommand{\DOWNLEFT}{{\mbox{\sc Down Left}}}
\newcommand{\PULL}{{\mbox{\sc Pull}}}
\newcommand{\PUT}{{\mbox{\sc Put}}}
\newcommand{\DOWN}{{\mbox{\sc Down}}}
\newcommand{\RIGHT}{{\mbox{\sc Right}}}
\newcommand{\LEFT}{{\mbox{\sc Left}}}
\newcommand{\LOAD}{{\mbox{\sc Load}}}
\newcommand{\WRITE}{{\mbox{\sc Write}}}
\newcommand{\READ}{{\mbox{\sc Read}}}
\newcommand{\ONLY}{{\mbox{\sc Only}}}
\newcommand{\POP}{{\mbox{\sc Pop}}}
\newcommand{\PUSH}{{\mbox{\sc Push}}}
% The following are only logical --KWR
\newcommand{\eqdef}{\mbox{$=_{\rm def}$}}
\newcommand{\AND}{\; \wedge \;}
\newcommand{\OR}{\; \vee \;}
\newcommand{\bigAND}{\bigwedge}
\newcommand{\bigOR}{\bigvee}
\newcommand{\And}{\;\&\;}
\newcommand{\Or}{\;\hbox{\rm or}\;}
\newcommand{\implies}{\Longrightarrow}
% \newcommand{\iff}{\Longleftrightarrow}
\newcommand{\eqv}{\longleftrightarrow}
\newcommand{\imp}{\rightarrow}
\newcommand{\TRUE}{\hbox{\rm TRUE}}
\newcommand{\FALSE}{\hbox{\rm FALSE}}
\newcommand{\into}{\rightarrow}
\newcommand{\union}{\cup}
\newcommand{\bigunion}{\bigcup}
\newcommand{\intersect}{\cap}
\newcommand{\bigintersect}{\bigcap}
\newcommand{\contains}{\supseteq}
\newcommand{\bo}{{\bf 0}}
\newcommand{\bl}{{\bf 1}}
% when there is time, fix the following mess with a nice macro
\newcommand{\dash}{\hbox{-}}
\newcommand{\redur}{\mathrel{\hbox{$\leq_{\rm r}$}}}
\newcommand{\rredu}{\redur}
\newcommand{\pmredu}{\mathrel{\hbox{$\leq_{\rm m}^{\rm p}$}}}
\newcommand{\rpmredu}{\mathrel{\hbox{$\leq_{\rm m}^{\rm rp}$}}}
\newcommand{\corpmredu}{\mathrel{\hbox{$\leq_{\rm m}^{\rm co-rp}$}}}
\newcommand{\bppmredu}{\mathrel{\hbox{$\leq_{\rm m}^{\rm bpp}$}}}
\newcommand{\vvmredu}{\mathrel{\hbox{$\leq_{\rm m}^{\rm vv}$}}}
\newcommand{\Rredu}{\mathrel{\hbox{$\leq_{\rm R}$}}}
\newcommand{\URredu}{\mathrel{\hbox{$\leq_{\rm UR}$}}}
\newcommand{\ptredu}{\mathrel{\hbox{$\leq_{\rm T}^{\rm p}$}}}
\newcommand{\pttredu}{\mathrel{\hbox{$\leq_{\rm tt}^{\rm p}$}}}
\newcommand{\pcttredu}{\mathrel{\hbox{$\leq_{\rm ctt}^{\rm p}$}}}
\newcommand{\pdttredu}{\mathrel{\hbox{$\leq_{\rm dtt}^{\rm p}$}}}
\newcommand{\pIttredu}{\mathrel{\hbox{$\leq_{\rm 1tt}^{\rm p}$}}}
\newcommand{\pIIttredu}{\mathrel{\hbox{$\leq_{\rm 2tt}^{\rm p}$}}}
\newcommand{\pmsredu}{\mathrel{<_{\rm m}^{\rm p}}}
\newcommand{\pmequiv}{\mathop{\equiv_{\rm m}^{\rm p}}}
\newcommand{\notpmredu}{\mathop{\not\leq_{\rm m}^{\rm p}}}
\newcommand{\plredu}{\mathop{\leq_1^{\rm p}}}
\newcommand{\notplredu}{\mathop{\not\leq_1^{\rm p}}}
\newcommand{\liredu}{\mathop{\leq_{1\dash{\rm li}}^{\rm p}}}
\newcommand{\pmttredu}{\mathrel{\hbox{$\leq_{\rm mtt}^{\rm p}$}}}
\newcommand{\pposredu}{\mathrel{\hbox{$\leq_{\rm pos}^{\rm p}$}}}
\newcommand{\npposredu}{\mathrel{\hbox{$\leq_{\rm pos}^{\rm np}$}}}
\newcommand{\snpmredu}{\mathrel{\hbox{$\leq_{\rm m}^{\rm snp}$}}}
\newcommand{\logmredu}{\mathrel{\hbox{$\leq_{\rm m}^{\rm log}$}}}
\newcommand{\cfrmredu}{\mathrel{\hbox{$\leq_{\rm m}^{\rm cfr}$}}}
\newcommand{\qlmredu}{\mathrel{\hbox{$\leq_{\rm m}^{\rm ql}$}}}
\newcommand{\qltredu}{\mathrel{\hbox{$\leq_{\rm T}^{\rm ql}$}}}
\newcommand{\qlmequiv}{\mathop{\equiv_{\rm m}^{\rm ql}}}
\newcommand{\Dpt}{\CD^{\rm p}_{\rm T}}
\newcommand{\Dppos}{\CD^{\rm p}_{\rm pos}}
\newcommand{\Dnppos}{\CD^{\rm np}_{\rm pos}}
\newcommand{\Rpequiv}{\equiv_{\Rplus}}
\newcommand{\Rmequiv}{\equiv_{\Rminus}}
\newcommand{\BPequiv}{\equiv_{\BP}}
\newcommand{\sqdot}{\rule{0.5mm}{0.5mm}}
\newcommand{\lam}[1]{\lambda #1\,\sqdot\,}
\newcommand{\lamp}[1]{\lam{\pair{#1}}}
\newcommand{\SO}{{\cal O}}
\newcommand{\Card}[1]{\Vert #1 \Vert}
\newcommand{\card}[1]{| #1 |}
\newcommand{\Quad}[1]{\hspace*{#1em}}
\newcommand{\qqquad}{\qquad\quad}
\newcommand{\proofsketch}{\noindent{\bf Proof Sketch.}\enspace}
\newcommand{\Proofsketch}[1]{\noindent{\bf Proof Sketch #1.}\enspace}
% \newcommand{\proof}{\noindent{\bf Proof.}\enspace}
\newcommand{\Proof}[1]{\bigbreak\noindent{\bf Proof #1.}\enspace}
\newenvironment{proof}{{\bf Proof. }}{\hfill\rule{2mm}{2mm}}
% the following makes a nice fat QED box
\newcommand{\sqr}[2]{{\vcenter{\hrule height.#2pt
\hbox{\vrule width.#2pt height#1pt \kern#1pt
\vrule width.#2pt}
\hrule height.#2pt}}}
\newcommand{\qed}{{\unskip\nobreak\hfil\penalty50
\hskip1em\hbox{}\nobreak\hfil$\sqr{8}{8}$
\parfillskip=0pt \finalhyphendemerits=0 \par}
\bigskip}
\newcommand{\Qed}[1]{{\unskip\nobreak\hfil\penalty50
\hskip1em\hbox{}\nobreak\hfil$\sqr{8}{8}$\enspace\bf #1
\parfillskip=0pt \finalhyphendemerits=0 \par}
\bigskip}
\newcommand{\refeq}[1]{(\ref{#1})}
\newcommand{\re}{r.e.\ }
\newcommand{\Nat}{{\rm \bf N}}
\newcommand{\Zed}{{\rm \bf Z}}
\newcommand{\Int}{\Zed}
\newcommand{\Reals}{{\rm \bf R}}
\newcommand{\sep}{{\,;\,}}
\newcommand{\hep}{{\,\#\,}}
%% Improve the following hack!!!
\newenvironment{header}{
\newcommand{\From}{\item[{\bf From:}]}
\newcommand{\To}{\item[{\bf To:}]}
\newcommand{\Subject}{\item[{\bf Subject:}]}
\newcommand{\Date}{\item[{\bf Date:}]}
\newcommand{\Revised}{\item[{\bf Revised:}]}
\newcommand{\Bar}{\item[\rule{0.986\textwidth}{.03in}]}
\begin{list}{\hbox{}}{
\leftmargin 1.5em
\itemindent -1em
\topsep 0pt
\labelwidth 0pt
\itemsep -5pt
}\Bar}{\Bar\end{list}
\medskip}
\newcommand {\Choose} [2] {(\,^{#1}_{#2}\,)}
\newcommand {\worddef}[1] {\boldmath{\bf #1}\unboldmath}
\newcommand{\GF}{\mbox{GF}}
\newcommand{\gh}{\mbox{gh}}
\newcommand{\ap}{\mbox{ap}}
% this is the macro-file for ampmp.tex. I called it tickmacro.tex
% \newenvironment{beweis} {\proof}{\qed}
\class{AmpMP}
\class{MaskP}
\newcommand {\ul} [1] {\underline{#1}}
\newcommand {\ol} [1] {\overline{#1}}
\newcommand {\subs} {\subseteq}
\newcommand {\parp} {\parityP}
\newcommand {\cparp} {\CparityP}
\newcommand {\bpparp} {\BP[\parityP]}
\newcommand {\mb} {\MP}
\newcommand {\nump} {\numberP}
\newcommand {\ampmp} {\AmpMP}
\newcommand {\con} {\cdot}
\newcommand {\acc} {\mbox{\it acc\/}}
\newcommand{\qacc}{q_{acc}}
\newcommand{\numacc}{\#\acc}
\newcommand{\polylog}{\mathop{\rm polylog}\nolimits}
\newcommand {\nule} {\{0,1\}}
\newcommand{\aat}{\mbox{@}}
\newcommand{\ats}{\mbox{\small @}}
\newcommand{\pct}{{\%}}
\newcommand{\dol}{{\$}}
% Miscellaneous macros defined for the Class Notes
\def\emptystring{\epsilon}
\def\diverge{\joinrel\uparrow}
% \def\Min{\hbox{Min}}
\newcommand{\N}{{\sf N\hspace*{-1.0ex}\rule{0.15ex}%
{1.3ex}\hspace*{1.0ex}}}
\newcommand{\rderive}{\Longrightarrow_r}
\newcommand{\rderives}{\Longrightarrow_r^*}
\newcommand{\derives}{\Longrightarrow^*}
\newcommand{\on}[1]{~(\mbox{on }#1)}
\newcommand{\ratrel}{\mbox {\it RatRel\/}}
\newcommand{\inverserel}[1]{{#1}^\leftarrow}
\newcommand{\rhoredu}{\mathrel{\hbox{$\leq_\rho$}}}
%\def\doublebits{\mathop{\sc Doublebits}\nolimits}
\newcommand{\doublebits}{\mbox{\sc Doublebits}}
%\def\doublebits{\mathop{\sc Doublebits}\nolimits}
\newcommand{\alt}{\mbox {\sc Alt}}
\def\vrange#1 #2 #3 {(#1_{#2}, \ldots #1_{#3})}
\def\emsg{\emptystring}
\newcommand{\Sklin}{\Sigma_k^{\lin}}
\newcommand{\Pklin}{\Pi_k^{\lin}}
SHAR_EOF
fi # end of overwriting check
if test -f 'KWRstyle.sty'
then
echo shar: will not over-write existing file "'KWRstyle.sty'"
else
cat << \SHAR_EOF > 'KWRstyle.sty'
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% Style changes to book.sty and bk12.sty %%%
%%% Plus some additional macros %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\ifcase\@ptsize
\def\big{\@setsize\large{12pt}\xiipt\@xiipt}
\def\small{\@setsize\large{8pt}\xiipt\@xiipt}
\or
\def\big{\@setsize\large{12pt}\xiipt\@xiipt}
\def\small{\@setsize\large{8pt}\xiipt\@xiipt}
\else
\def\big{\@setsize\large{14pt}\xiipt\@xiipt}
\def\small{\@setsize\large{10pt}\xiipt\@xiipt}
\fi
\def\@normalsize{\@setsize\normalsize{14.5pt}\xiipt\@xiipt
\abovedisplayskip 12pt plus3pt minus7pt%
\belowdisplayskip \abovedisplayskip
\abovedisplayshortskip \abovedisplayskip % \z@ plus3pt%
\belowdisplayshortskip \abovedisplayskip % 6.5pt plus3.5pt minus3pt
}
\def\small{\@setsize\small{13.6pt}\xipt\@xipt
\abovedisplayskip 11pt plus3pt minus6pt%
\belowdisplayskip \abovedisplayskip
\abovedisplayshortskip \abovedisplayskip % \z@ plus3pt%
\belowdisplayshortskip \abovedisplayskip % 6.5pt plus3.5pt minus3pt
\def\@listi{\parsep 4.5pt plus 2pt minus 1pt
\itemsep \parsep
\topsep 9pt plus 3pt minus 5pt}}
\def\footnotesize{\@setsize\footnotesize{12pt}\xpt\@xpt
\abovedisplayskip 10pt plus2pt minus5pt%
\belowdisplayskip \abovedisplayskip
\abovedisplayshortskip \abovedisplayskip % \z@ plus3pt%
\belowdisplayshortskip \abovedisplayskip % 6pt plus3pt minus3pt
\def\@listi{\topsep 6pt plus 2pt minus 2pt\parsep 3pt plus 2pt minus 1pt
\itemsep \parsep}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcounter{innersec}
\setcounter{innersec}{0}
\def\theinnersec{}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% PAGE SIZE HACKS
\marginparwidth 35pt
\oddsidemargin 15pt
\evensidemargin 15pt
\marginparsep 0pt
\topmargin 0pt
\textwidth 16cm
\textheight 22cm
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% NUMBERING HACKERY
\newcommand{\addtoreset}[2]{\@addtoreset{#1}{#2}}
\def\refcounter#1{{\let\@elt\@stpelt \csname cl@#1\endcsname}
\edef\@currentlabel{\csname p@#1\endcsname\csname the#1\endcsname}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \@makechapterhead {TEXT} : Makes the heading for the \chapter command.
%
\def\@makechapterhead#1{ % Heading for \chapter command
\vspace*{5pt} % Space at top of text page. CHANGED -JSR
{ \parindent 0pt \begin{center}
\ifnum \c@secnumdepth >\m@ne % IF secnumdepth > -1 THEN
\Large\bf\@chapapp\ \arabic{chapter} % Print 'Chapter' and number.
\par
\vskip 30pt \fi % Space between number and title.
% CHANGED -JSR
\LARGE \bf % Title. CHANGED -JSR
#1\par
\end{center}
\nobreak % TeX penalty to prevent page break.
\vskip 30pt % Space between title and text.
% CHANGED -JSR
} }
% \@makeschapterhead {TEXT} : Makes the heading for the \chapter* command.
%
\def\@makeschapterhead#1{ % Heading for \chapter* command
\vspace*{40pt} % Space at top of page. CHANGED -JSR
{ \parindent 0pt \begin{center}
\LARGE \bf % Title. CHANGED -JSR
#1\par
\end{center}
\nobreak % TeX penalty to prevent page break.
\vskip 30pt % Space between title and text.
% CHANGED -JSR
} }
\def\@chapter[#1]#2{\ifnum \c@secnumdepth >\m@ne
\refstepcounter{chapter}
\def\theinnersec{\thechapter} % ADDED -JSR
\refcounter{innersec} % ADDED -JSR
\typeout{\@chapapp\space\thechapter.}
\addcontentsline{toc}{chapter}{\protect
\numberline{\thechapter}#1}\else
\addcontentsline{toc}{chapter}{#1}\fi
\chaptermark{#1}
\addtocontents{lof}{\protect\addvspace{10pt}} % Adds between-chapter space
\addtocontents{lot}{\protect\addvspace{10pt}} % to lists of figs & tables.
\if@twocolumn % Tests for two-column mode.
\@topnewpage[\@makechapterhead{#2}]
\else \@makechapterhead{#2}
\@afterheading % Routine called after chapter and
\fi} % section heading.
\def\@sect#1#2#3#4#5#6[#7]#8{\ifnum #2>\c@secnumdepth
\def\@svsec{}\else
\refstepcounter{#1}\edef\@svsec{\csname the#1\endcsname.\hskip 1em }\fi
\@tempskipa #5\relax
\ifdim \@tempskipa>\z@
\begingroup #6\relax
\@hangfrom{\hskip #3\relax\@svsec}{\interlinepenalty \@M #8\par}
\endgroup
\csname #1mark\endcsname{#7}\addcontentsline
{toc}{#1}{\ifnum #2>\c@secnumdepth \else
\protect\numberline{\csname the#1\endcsname}\fi
#7}\else
\def\@svsechd{#6\hskip #3\@svsec #8\csname #1mark\endcsname
{#7}\addcontentsline
{toc}{#1}{\ifnum #2>\c@secnumdepth \else
\protect\numberline{\csname the#1\endcsname}\fi
#7}}\fi
\@xsect{#5}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% NOTE: Change the numeric params latter to reflect the fact that we're using
% smaller type sizes than Lamport prefers.
\def\section{\def\theinnersec{\thesection}\refcounter{innersec}
\@startsection{section}{1}{\z@}{-3.5ex plus -1ex minus -.2ex}{2.3ex plus
.2ex}{\large\bf}}
\def\subsection{\def\theinnersec{\thesubsection}\refcounter{innersec}
\@startsection{subsection}{2}{\z@}{-3.25ex plus -1ex minus -.2ex}
{1.5ex plus .2ex}{\normalsize\bf}}
\def\subsubsection{\def\theinnersec{\thesubsection}\refcounter{innersec}
\@startsection{subsubsection}{3}{\z@}{-3.25ex plus -1ex minus
-.2ex}{1.5ex plus .2ex}{\normalsize\bf}}
\def\paragraph{\def\theinnersec{\theparagraph}\refcounter{innersec}
\@startsection{paragraph}{4}{\z@}{3.25ex plus 1ex minus
.2ex}{-1em}{\normalsize\bf}}
\def\subparagraph{\def\theinnersec{\thesubparagraph}\refcounter{innersec}
\@startsection{subparagraph}{4}{\parindent}{3.25ex plus 1ex minus
.2ex}{-1em}{\normalsize\bf}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\@begintheorem#1#2{\sl \trivlist %
\item[]{\bf #1\ #2.\hskip \labelsep}}
\def\@opargbegintheorem#1#2#3{\sl \trivlist
\item[]{\bf #1\ #2\ (#3).\hskip \labelsep}}
\def\@thmcountersep{.}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Stuart's defs.sty. [This is the most important part --KWR]
%
% Construct a "newdefinition" command analogous to the newtheorem
% command. The primary difference is that the newdefinition widget
% does not cause its body to be italicized.
%
% This is all cribbed from latex.tex.
% Contact Stuart A. Kurtz if there are any difficulties.
\def\newdefinition#1{\@ifnextchar[{\@odefn{#1}}{\@ndefn{#1}}}
\def\@ndefn#1#2{%
\@ifnextchar[{\@xndefn{#1}{#2}}{\@yndefn{#1}{#2}}}
\def\@xndefn#1#2[#3]{\expandafter\@ifdefinable\csname #1\endcsname
{\@definecounter{#1}\@addtoreset{#1}{#3}%
\expandafter\xdef\csname the#1\endcsname{\expandafter\noexpand
\csname the#3\endcsname \@thmcountersep \@thmcounter{#1}}%
\global\@namedef{#1}{\@defn{#1}{#2}}\global\@namedef{end#1}{\@enddefinition}}}
\def\@yndefn#1#2{\expandafter\@ifdefinable\csname #1\endcsname
{\@definecounter{#1}%
\expandafter\xdef\csname the#1\endcsname{\@thmcounter{#1}}%
\global\@namedef{#1}{\@defn{#1}{#2}}\global\@namedef{end#1}{\@enddefinition}}}
\def\@odefn#1[#2]#3{\expandafter\@ifdefinable\csname #1\endcsname
{\global\@namedef{the#1}{\@nameuse{the#2}}%
\global\@namedef{#1}{\@defn{#2}{#3}}%
\global\@namedef{end#1}{\@enddefinition}}}
\def\@defn#1#2{\refstepcounter
{#1}\@ifnextchar[{\@ydefn{#1}{#2}}{\@xdefn{#1}{#2}}}
\def\@xdefn#1#2{\@begindefinition{#2}{\csname the#1\endcsname}\ignorespaces}
\def\@ydefn#1#2[#3]{\@opargbegindefinition{#2}{\csname
the#1\endcsname}{#3}\ignorespaces}
\def\@begindefinition#1#2{ \trivlist \item[\hskip \labelsep{\bf #1\ #2.}]}
\def\@opargbegindefinition#1#2#3{\trivlist
\item[\hskip \labelsep{\bf #1\ #2\ (#3).}]}
\def\@enddefinition{\endtrivlist}
% Construct a "newscholium" command analogous to the newtheorem
% command. The primary difference is that the newscholium widget
% does not cause its body to be italicized.
%
% This is all cribbed from latex.tex.
% Contact Stuart A. Kurtz if there are any difficulties.
\def\newscholium#1{\@ifnextchar[{\@oschm{#1}}{\@nschm{#1}}}
\def\@nschm#1#2{%
\@ifnextchar[{\@xnschm{#1}{#2}}{\@ynschm{#1}{#2}}}
\def\@xnschm#1#2[#3]{\expandafter\@ifdefinable\csname #1\endcsname
{\@definecounter{#1}\@addtoreset{#1}{#3}%
\expandafter\xdef\csname the#1\endcsname{\expandafter\noexpand
\csname the#3\endcsname \@thmcountersep \@thmcounter{#1}}%
\global\@namedef{#1}{\@schm{#1}{#2}}\global\@namedef{end#1}{\@endscholium}}}
\def\@ynschm#1#2{\expandafter\@ifdefinable\csname #1\endcsname
{\@definecounter{#1}%
\expandafter\xdef\csname the#1\endcsname{\@thmcounter{#1}}%
\global\@namedef{#1}{\@schm{#1}{#2}}\global\@namedef{end#1}{\@endscholium}}}
\def\@oschm#1[#2]#3{\expandafter\@ifdefinable\csname #1\endcsname
{\global\@namedef{the#1}{\@nameuse{the#2}}%
\global\@namedef{#1}{\@schm{#2}{#3}}%
\global\@namedef{end#1}{\@endscholium}}}
\def\@schm#1#2{\refstepcounter
{#1}\@ifnextchar[{\@yschm{#1}{#2}}{\@xschm{#1}{#2}}}
\def\@xschm#1#2{\@beginscholium{#2}{\csname the#1\endcsname}\ignorespaces}
\def\@yschm#1#2[#3]{\@opargbeginscholium{#2}{\csname
the#1\endcsname}{#3}\ignorespaces}
\def\@beginscholium#1#2{\footnotesize \trivlist %
\item[]{\bf #1\ #2.\hskip \labelsep}}
\def\@opargbeginscholium#1#2#3{\footnote \trivlist %
\item[]{\bf #1\ #2\ (#3).\hskip \labelsep}}
\def\@endscholium{\endtrivlist}
%%% The \text command stolen from AMSLaTeX
\def\RIfM@{\relax\ifmmode}
\def\RIfMIfI@{\relax\ifmmode\ifinner}
\def\Invalid@#1{\def#1{\Err@{\Invalid@@\string#1}}}
\def\Invalid@@{Invalid use of }
\def\DN@{\def\next@}
\def\eat@#1{}
\def\text{\RIfM@\expandafter\text@\else\expandafter\text@@\fi}
\def\text@@#1{\leavevmode\hbox{#1}}
\newif\iffirstchoice@
\firstchoice@true
\def\text@#1{\mathchoice
{\hbox{\everymath{\displaystyle}\def\textfonti{\the\textfont\@ne}%
\def\textfontii{\the\textfont\tw@}\textdef@@ T#1}}
{\hbox{\firstchoice@false
\everymath{\textstyle}\def\textfonti{\the\textfont\@ne}%
\def\textfontii{\the\textfont\tw@}\textdef@@ T#1}}
{\hbox{\firstchoice@false
\everymath{\scriptstyle}\def\textfonti{\the\scriptfont\@ne}%
\def\textfontii{\the\scriptfont\tw@}\textdef@@ S\rm#1}}
{\hbox{\firstchoice@false
\everymath{\scriptscriptstyle}\def\textfonti
{\the\scriptscriptfont\@ne}%
\def\textfontii{\the\scriptscriptfont\tw@}\textdef@@ s\rm#1}}}
\def\textdef@@#1{\textdef@#1\rm\textdef@#1\bf\textdef@#1\sl\textdef@#1\it}
\def\rmfam{0}
\def\textdef@#1#2{%
\DN@{\csname\expandafter\eat@\string#2fam\endcsname}%
\if S#1\edef#2{\the\scriptfont\next@\relax}%
\else\if s#1\edef#2{\the\scriptscriptfont\next@\relax}%
\else\edef#2{\the\textfont\next@\relax}\fi\fi}
SHAR_EOF
fi # end of overwriting check
if test -f 'LNall.tex'
then
echo shar: will not over-write existing file "'LNall.tex'"
else
cat << \SHAR_EOF > 'LNall.tex'
% Document Type: LaTeX
\documentstyle[KWRstyle,11pt,psfig]{article}
% \documentstyle[KWRLNstyle,11pt,psfig]{article}
% \documentstyle[KWRstyle,11pt,titlepage]{article}
% \special{header=lprep70.procs}
% \renewcommand{\baselinestretch}{1.2}
\setlength{\textwidth}{6.4in} %6.25in or 6.5in
\setlength{\textheight}{9in}
\setlength{\topmargin}{0in}
\setlength{\headheight}{0in}
\setlength{\headsep}{0in}
\setlength{\footheight}{.5in}
\setlength{\footskip}{.5in}
\setlength{\oddsidemargin}{.2in} %.2in or 0in
\setlength{\parindent}{0.3in} %.5in
\setlength{\parskip}{0in} %.1 in or .2 in or 0in
\setlength{\partopsep}{2ex}
\setlength{\topsep}{1ex}
\setlength{\itemsep}{.5ex}
\input{KWRmacs}
%\input{KWRLNmacs}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\hfuzz=3pt
\vfuzz=3pt
\begin{document}
\bibliographystyle{alpha}
\begin{titlepage}
\hbox{}
\vspace{.75in}
\centerline{\bf \LARGE
Formal Language Theory: Origins and New Directions}
\vspace{.50in}
\centerline{\Large Class Notes for CS682: ``Formal Language Theory II''}
\vspace{1in}
\centerline{\large Instructor: Dr. Kenneth W.~Regan}
\vspace{.5in}
\centerline{\large Students and Scribes, Fall 1993:}
\vspace{.17in}
\centerline{\large Daniel F. Boyd}
\centerline{\large Deborah T. Burhans}
\centerline{\large Kannan Govindarajan}
\centerline{\large D. Sivakumar}
\centerline{\large Michael J. Smolowitz}
\vspace{1.75in}
\centerline{December 1993}
\vspace{.75in}
\centerline{Department of Computer Science}
\centerline{State University of New York at Buffalo}
\centerline{226 Bell Hall, Buffalo, NY 14260 USA}
\vspace{.5in}
\centerline{Authors' e-mail addresses:
\{regan,boyd,burhans,govin-k,sivak-d,ms\}@cs.buffalo.edu}
\end{titlepage}
% \begin{document}
% \bibliographystyle{alpha}
% \maketitle
\sloppy
\section{Preface}
These notes were compiled by the instructor and students during
the teaching of the course ``CS682: Formal Language Theory II''
in the Computer Science Department of the State University of
New York at Buffalo during the Fall Semester, 1993.
The system of taking and preparing class notes was modeled on
the treatment of 6xx courses at MIT.
The students were assigned responsibility for compiling the
notes in LaTeX. This began in the second week of term
after a special session describing the LaTeX macros used
for the notes and giving students some practice.
In this compilation, I have removed the MIT macros for
numbering by lecture, and have grouped the material by
topics rather than by weeks.
After each section heading I indicate which students scribed that
section and the time period covered.
As of this writing (12/14/93), I have not yet made intended
revisions and additions to the notes as they were covered in class.
The main motivation for compiling these notes is to provide
a single, {\em good\/} source for the special topics that
formed the second half of the course, namely the connections
among Smullyan's {\em rudimentary relations\/},
other systems of first-order logic, and (to use a term of
Harvey Rose \cite{Rose84})
``small classes'' of languages.
Since 1981, the year of both the article by S. Greibach
titled ``Formal Languages: Origins and Directions''
\cite{Gre81}
and the first publication of the Furst-Saxe-Sipser theorem
\cite{FSS81,FSS84}, there have been many notable
advances in the part of complexity theory
having to do with small classes.
(Hence my modification to Greibach's title.)
Parts of the foundation for this work were laid in
papers from the 1960s and 1970s, and other parts,
cast by Barrington, Immerman, and Straubing
\cite{Imm87,Bar89,BIS90} from molds cut by earlier
researchers in logic and circuit complexity, are newer.
However, the sources-of-record
for these developments are journal papers,
from which I selected the above-cited and
\cite{Jon69,Jon75,Wra78} (plus the book \cite{MP71}
and some nice expository papers such as \cite{Lin92b}).
Taken collectively, these papers do not (and being separate
in time and space, would not be expected to) provide a
cohesive picture of the subject.
Also, IMHO, they are on the whole not particularly well written.
They provided an all-too-typical challenge for the students
of learning how to read real journal papers, warts and all.
The purpose of the course was to draw connections among these
papers, and to stimulate deeper insights as a basis for
further research.
One paper which was very valuable in this last service
was a well-written note by Allender and Gore \cite{AlGo91b}
connecting Jones' work and
\cite{BIS90}.
I used this in the final part of the course, but for variety,
carried out the cycle of proofs of equivalence in the opposite direction.
A second service of these notes is that several of the above-cited
papers refer to earlier work for key points in their proofs,
and this ``citation trail'' goes all the way back to
several Ph.D. theses in the 1960s which are not so readily
obtainable. One such example is the trick for writing
a language in $\NLIN$ as an intersection of CFLs, which
goes from \cite{Wra78} through \cite{BoGr70} and \cite{GrHo69}
to a citation of a thesis.
Another hard-to-track lemma is the one for converting an alternating TM
to an ATM which queries its input at most once along any path,
{\em while increasing the number of alternations by at most 1\/}
(most references omit the last clause).
We also found an anticipation of the binary-counting lemma
of \cite{BIS90} in a lemma of Jones \cite{Jon69};
this is even earlier than a similar lemma of Lipton
\cite{Lip78}, who shares credit with Pippenger.
Also in these notes (as of 12/14/93, a problem on the
take-home final) is an ``elementary'' proof that every
first-order definable language is star-free regular;
the proof is different from those in
\cite{Mey69,MP71,Lad77,Tho82,PePi86,Bar89}, and the
idea of writing numbers in unary notation appears to be
entirely new.
It is natural for established researchers who are familiar
with these matters to brush them off, but they can be
hard obstacles for students if not done {\em right\/}.
Put another way, we more-advanced people should give
our students every opportunity to spot something in these
``old'' lemmas that we ourselves have always missed!
The plan of this course
was to stay with the established text by Hopcroft and Ullman \cite{HU79}
in the first half, concentrating on chapters 10-12, before
making the leap to less-structured sources.
To my own chagrin, I found that the material on LR$(k)$ parsing
in \cite{HU79} is not in as good a shape as I expected it to be,
and several other well-known texts were not much help in my
initial flailing, until I figured out which concepts were
primary and which could be deferred.
Hopcroft and Ullman do the LR$(0)$ case and sketch the
LR$(1)$ case. From what I found, it is {\em better\/} to begin
with the general LR$(k)$ case---when one has good notation, this
is really not any more overhead than for LR$(1)$. Indeed,
starting with LR$(k)$ makes the requirements clearer.
The case $k=0$ should in retrospect be regarded as degenerate.
The most instructive way to appreciate the difference between
LR$(1)$ and LR$(0)$ is to do the construction from a DPDA to an
LR$(1)$ grammar $G$, and then challenge the students to find
the one point where $G$ fails to be LR$(0)$.
Then the result about $L\cdot\$$ having an LR$(0)$ grammar,
which is done first in \cite{HU79} and other texts, can be
understood as a patch on the previous proof.
Also in my opinion, the concept of a {\em handle\/} in a derivation
is unnecessary before presenting the principle and gets in the way;
it is best introduced later when one discusses ways of
{\em improving\/} the efficiency of implementations of the
principle.
Thus these notes also unintendedly provide a streamlined
new treatment of the theory behind
LR$(k)$ parsing.
These notes are preliminary, and will be refined and augmented later on.
They are also incomplete. The unit on LR$(k)$ parsing was
intended to serve a one-week treatment of DPDAs with
two-way input tape (presenting Cook's linear-time simulation on a RAM
by the method of ``building a table''), with the speculative
purpose of basing a generalization of LR$(k)$ parsing on them.
I had to cut this and advance to the Chomsky-Sch{\"u}tzenberger
Representation Theorem as a preface to Wrathall's paper,
but part of this is the topic of D. Boyd's short essay, which will be
integrated with these notes at a later date.
I have not yet established just what sort of generalization
will work; K.~Govindarajan's essay may provide some useful guidelines.
The three other ``2-3 page research essays'' and the problem sets
in the course will be integrated later as well.
There were also two weeks of intended material on classes within
$\NC^1$ that were not presented by the end of term; there is only
a one-page sketch in the last section as of now.
Comments on these notes are welcome and invited.
I am grateful for advice and help in certain particulars from
Professors David Mix Barrington, John Case, Ronald Book, Oscar Ibarra,
Michael Loui, and Eric Allender.
Barrington provided me his current skeletal outline of the
book on this subject that he has just begun; these notes are mostly
independent of it.
\newpage
\section{Review of Formal Language Theory and Preview of Course}
[First week of class, lectures 01--03, scribed by K.W. Regan; some
notes were added later.]
\bigskip
The first week of lectures is a review of the basic
{\em types\/} of objects seen in formal language theory,
followed by an important example of ``generalized'' homomorphisms
and how they can simulate Turing machines.
The basic types are organized around what is sometimes called the
``ladder of abstraction.''
Going one rung up the latter means talking about
{\em sets of\/} objects at the previous level.
\bigskip
{\bf Level 0.} {\Char}acters over some alphabet
$\Sigma$. Usually $\Sigma$ is finite.
Most often $\Sigma = \set{0,1}$ or $\Sigma = \set{\mbox{a,b}}$.
\bigskip
{\bf Level 1.} {\String} = ARRAY $[0\dots n \!-\! 1]$ OF {\Char}.
Consider the following correspondence:
\begin{tabbing}
Numbers\quad\= {$\Sigma^*$ }\= {$=$ } \= {$\lambda$,}
\= 0, \= 2, \= 00, \= 01, \= 10, \= {\dots} \kill
Strings \> $\Sigma^*$ \>$=$ \>$\lambda$ \>0,\>1,\>00,\>01,\>10,\>{\dots}\\
Numbers \> $\Nat$ \>$=$ \>0,\>1,\>2,\>3,\>4,\>5,\>{\dots}\\
\end{tabbing}
In {\em dyadic notation\/}, the number $\mbox{\it Val\/}(x)$
corresponding to a binary string $x$ of length $n$ equals
$\sum_{i=0}^{n-1} (x_i + 1)\!\cdot\! 2^i$.
This is often superior to standard binary notation---it eliminates
the problem that ``leading zeroes'' give multiple names for the
same number.
There is another way to look at strings: rather than ordered arrays of
characters, they can be unordered sets of ``events.'' Define
{\Event} to be the type ({\Char},{\it position\/}), where
{\it position\/} is a natural number. Then for instance,
the string 10110 is given by $\set{(1,3),(1,2),(1,0),(0,1),(0,4)}$,
with the order immaterial. This notation also allows for
``partial strings''; i.e., where the set does not fill all positions
up to the highest one in the set. I'm mostly saying this because the
type definition {\String} = SET OF {\Event} has the same
form as what follows. (A second reason: the notion of a
``non-consecutive substring'' such as 010 in positions 1,2,4 in 10110
may become useful later.)
As an ``aside,'' let me mention several extensions of the notion
of a string:
\begin{itemize}
\item
``Compound strings'' of the form $(x,y)$ where $x$ and $y$ are strings.
These have been studied. For example, one representation of the
important Pattern Matching language is
$L_{\rm pat} = \set{(p,t) : p,t \in \Sigma^* \AND (\exists u,v \in \Sigma^*)
t = upv}$. Then
$((\epsilon,0) + (\epsilon,1))^* ((0,0)+(1,1))^*
((\epsilon,0) + (\epsilon,1))^*$
is a ``compound regular expression'' which defines $L_{pat}$.
$L_{pat}$ is accepted by a two-input-tape NFA, but not by any
two-tape DFA (even stronger, not by any DFA with two heads on a
single tape containing $p\#t$). Thus the ``NFA=DFA'' part of
Kleene's Theorem fails in the case of compound strings.
\item
The second typing for strings above can also be thought of as
the type ${\it position} \into {\it Char\/}$. That is, a string
is a function $c(t)$ which gives the character at each position $t$.
If we think of $t$ as ``time,'' we can generalize this to a notion
of ``continuously-varying strings.'' This is not as far-fetched as
it sounds, and without having any specific knowledge, I suspect
that this notion is implicit if not explicit in much work on
real-time process control.
\item
One can think of {\em two-dimensional strings\/} as 2D arrays of characters.
Two-dimensional pattern-matching is a field with huge practical
importance. Dr.\ Alan Huang of Bell Labs, who is one of the foremost
researchers in optical computing today, has developed a theory of
computing via optical 2D pattern matching which he calls
{\it Symbolic Substitution\/}. I know of no general work on extending
the theory of 1D strings and formal languages to 2D strings.
It might be
interesting in particular to investigate which properties
are ``really 2D,'' in the sense that they are not simply lifted from
properties of 1D {\em rasterizations\/} of 2D strings.
\end{itemize}
OK, I digressed, but let me ask: In how many fields can one be at
the frontier of current research 15 minutes into the first lecture of term?
\bigskip
{\bf Level 2.}
{\Language} = SET OF {\Strings}.
Recall that there are $2^{\aleph_0}$-many languages over a given finite
alphabet, only $\aleph_0$ of which are r.e.
\bigskip
{\bf Level 3.}
{\Class} = SET OF {\Languages}.
Formal language theorists like to talk in terms of classes, rather
than any of the more-concrete objects lower down on the
ladder of abstraction. (:-))
\bigskip
{\bf Level 4.}
{\Hierarchy} = SET OF {\Classes}.
Two examples are:
\begin{enumerate}
\item
{\it The Chomsky Hierarchy\/} =
$\REG,\CFL,CSL,RE$.
\item
{\it The Arithmetical Hierarchy\/} = $\REC,\RE,\RE^{\RE},\RE^{\RE^{\RE}},\dots$,
equivalently written as $\Sigma_0^0,\Sigma_1^0,\Sigma_2^0,\Sigma_3^0,\dots$.
\end{enumerate}
From CS596, recall that the ``stacks of $\RE$'' notation referred to
definitions of classes via {\em oracle Turing machines\/}, while
the $\Sigma_k^0$ notation referred to classes of languages defined
by logical formulas of arithmetic---for $\Sigma_k^0$, the formulas
are required to be in {\em prenex form\/} with at most $k$ blocks
of like quantifiers, the first (outermost) block being existential.
The statement that the two ways of defining the hierarchy are
equivalent is sometimes called the
``Weak Hierarchy Theorem'' of Kleene,
while Kleene's ``Strong Hierarchy Theorem'' is that all these
classes are distinct.
In complexity theory we've talked about the
{\em Polynomial Hierarchy\/}, with notation
$\P = \Sigma_0^p$, $\NP = \Sigma_1^p$, $\NP^{\NP} = \Sigma_2^p$, etc.
Here again, the $\Sigma_k^p$ notation requires to
definitions by quantifiers, this time by
{\em polynomial-length bounded\/}) quantifiers,
and there is a ``weak hierarchy theorem'' stating equivalence to
``oracle'' definitions, this time involving polynomial-time bounded
(non-)deterministic oracle TMs.
But there is no known analogue of the strong-hierarchy theorem;
whether the polynomial hierarchy ``collapses'' or is infinite
includes the $\P$ vs.\ $\NP$ question.
In this course we will study two other hierarchies.
The {\em Linear-Time Hierarchy\/}, for which I'll use the notation
$\Sigma_k^{\lin}$, was apparently first defined and studied
as such by Celia Wrathall, in her Ph.D.\ thesis \cite{Wra75}
and journal paper \cite{Wra78}.
Let $\LINH = \cup_{k=1}^{\infty}$. In addition to proving
the equivalence of several ways of defining $\Sigma_k^{\lin\/}$,
including one involving {\em alternating\/} linear-time Turing machines,
Wrathall proved that
$\LINH$ equals the class $\RUD$ of languages definable in
Raymond Smullyan's
system of {\em rudimentary\/} relations.
Neil Jones \cite{Jon69} had earlier observed that
$\RUD$ contains all CFLs and many non-CFLs besides, but it was
Wrathall who really pinpointed the complexity-theoretic power of
these relations.
Again no ``strong hierarchy theorem'' is known here, except that
the class $\Sigma_1^{\lin} = \NLIN$ (viz., nondeterministic linear
time on Turing machines) is known to properly contain
$\DLIN$ (deterministic linear time), by the theorem of
Paul, Pippenger, Szemer{\'e}di, and Trotter \cite{PPST83}.
However, the $\NLIN \neq \DLIN$ proof turns on some very
gritty limitations of the 1-dimensional tapes of TMs, and is
not known to carry over when TMs can have 2-D tapes.
That is, whereas $\NLIN$ remains the same under this and several
other variations of the TM model
(so to speak, it is a quite {\em robust\/} complexity concept),
$\DLIN$ seems sensitive to picky details,
and I'm not sure the TM version
deserves the name ``$\Sigma_0^{\lin}$.''
The other hierarchy is at a {\em much lower\/} level of complexity,
namely that of {\em alternating\/} Turing machines which do
(and thanks to a special ``random-access'' input mechanism, can)
run in {\em logarithmic\/} time.
Here the notation will be $\Sigma_k^{\log}$ and $\LOGH$,
and the final phase of the course will concern many equivalent
characterizations of $\LOGH$: by systems of first-order logic,
by ``log-bounded rudimentary relations'' \cite{Jon75,AlGo91b},
and by constant-depth unbounded fan-in circuits.
(At this point I am not aware of sharp characterizations of
the individual $\Sigma_k^{\log}$ levels; in fact, there seem
to be nagging differences in the alternating log-time TM model itself,
especially in the definition of $\DLOGTIME$.)
\bigskip
{\bf Level 5.}
Well, this would be: sets of hierarchies. I've never seen anyone
really draw attention to this as a {\em concept\/}.
Despite how things may seem from the above, I
don't want you to do so either.
\bigskip
Instead, I will emphasize other kinds of formal objects
``closer to Earth'' and on a par with strings and languages.
First consider
\bigskip
{\bf Predicates:}
type $\String \into \Bool$.
Given a predicate $R$ with one free variable $\hat{x}$,
define $L_R := \set{x \in \Sigma^* : R(x) \mbox{ holds}}$.
Sometimes we'll just call this language $R$.
[Note: I won't always annotate the distinction between
the formal name of a variable $\hat{x}$ and substituting
a particular value $x$ for $\hat{x}$; you'll be expected to
get used to my writing just $x$ in either sense.
However, I {\em will\/} try to preserve the sense of
$x$ standing for an object of type \String, and in particular,
for ``the main input string.''
In many references, ``$x$'' is used for variables in other contexts,
most annoyingly, for {\em positions\/} in the input string.]
\bigskip
{\bf Characteristic functions.} Given a language $L$, define
$\chi_L(x) = 1$ if $x \in L$, $= 0$ otherwise.
If we identify $\set{0,1}$ with the type $\Bool$, then this
has the same type as a predicate with one free variable.
However, usually we'll think of predicates as finite
{\em syntactic\/} objects that we can encode as strings.
I'll try to use the letters $P,Q,R,S\dots$ for predicates and
$L,A,B,C,D\dots$ for languages.
We'll be free to write e.g.\
$A(x) = B(x)$ interchangeably with $\chi_A(x) = \chi_B(x)$ or
$x \in A \iff x \in B$,
and $P(x)$ can be identified with $L_P(x)$ or
$\chi{L_P}(x)$.
Here's a subtler convention which seems to be taking root
in the field. If I write
$P(x) \eqv Q(x)$, this carries the connotation that I am
most interested in the {\em formal object\/} $P \eqv Q$, while
double arrows $\implies$, $\iff$ are used when
only the {\em truth\/} of a particular statement is concerned.
(A more-dubious habit is writing ``$P(x)$'' to mean
``$P$ is a predicate with one free variable $x$''; this is like
writing ``$f(x)$'' to refer to a function.)
\bigskip
{\bf String relations of arity} $k \geq 2$:
Suppose $P$ is a predicate with two free variables;
i.e. $P: \Sigma^* \times \Sigma^* \into \Bool$.
Then we let $\rho_P$ stand for the {\em relation\/}
\[
\rho_P = \set{(x,y) : P(x,y)}.
\]
Using some sort of injective {\em tupling function\/}
$\tuple{\cdot,\cdot}: \Sigma^* \times \Sigma^* \into \Sigma^*$,
we could represent $P$ by the language
$\theta_P = \set{\tuple{x,y} : P(x,y)}$ (the ``$\theta$'' is
Wrathall's notation).
However, one of the distinctive features of my approach
will be the desire to treat relations as entities in their own
right. When we get to the topic of the so-called
{\em rational relations\/}, we'll see several important
differences from regular languages, whose appreciation
would be diminished if we always ``flattened'' relations to languages.
Here's a principal motivation:
A predicate $P(x)$, with the one free variable $x$,
often has other variables $y,z,\dots$ which were
quantified ``at earlier stages in the building of $P$.''
Logic has a natural inductive structure on which to
prove results, or to locate the precise point at which
some property is lost, but the most natural
paths through that structure to a desired predicate $P(x)$
generally all go through predicates of higher arity.
What I'm hoping for is that working directly with the
{\em relations\/} defined by these intermediate predicates
will reveal secrets and structures that flattening everything
to languages might hide.
In combinatorics, the simple trick of interchanging the order
of variables in a summation is often what turns the intuitive corner
toward a new result.
My analogy here is the idea of transposing a $k$-ary relation
of strings of length (say) $n$ into an $n$-ary relation of
strings of length $k$, or alternatively into a language
of single strings over a huge alphabet of $k$-tuples.
Two simple tupling functions deserve mention here.
Let $\Sigma = \set{0,1}$, $\Gamma = \set{0,1,\#}$.
Let $h: \Gamma \into \Sigma^2$ be given by
$h(0) = 00$, $h(1) = 11$, $h(\#) = 01$.
Then $h$ determines a unique {\em homomorphism\/}
$h_*: \Gamma^* \into \Sigma^*$ via the inductive
definition:
\begin{itemize}
\item
{\em Basis.\/} $h_*(\epsilon) = \epsilon$.
\item
{\em Induction.\/} For all $c \in \Gamma$ and $w \in \Gamma^*$,
$h_*(cw) = h(c)\cdot h_*(w)$.
\end{itemize}
It is a little bit more precise to justify the
induction step here by noting that: given $x \in Gamma^*$ such that
$x \neq \epsilon$, there is a unique way to write
$x = cw$ such that $c \in \Gamma$ and $w \in \Gamma^*$;
then we may define $h_*(x) = h(c)\cdot h_*(w)$.
As in CS596, I will eventually drop the notational distinction
between the finite function $h$ and its extension $h_*$.
Now define for all sequences $(x_1,x_2,\dots x_k)$ of strings over $\Sigma$,
\[
\tuple{(x_1,x_2,\dots x_k} = h(x_1 \# x_2 \# \dots \# x_k).
\]
This function is 1-1, and is ``easily'' computed. We associate to it
the {\em projection functions\/} $\pi_j$, for $1 \leq j \leq k$,
defined for all $z \in \Sigma^*$ by
$\pi_j(z) = x_j$ if there exist
$x_1,\dots,x_{j-1},x_{j+1},\dots x_k \in \Sigma^*$ such that
$\tuple{x_1,x_2,\dots,x_k} = z$, {\em undefined\/} otherwise.
Note that since $\tuple{\dots}$ is not onto, $\pi_j(z)$ may
be undefined. If one cares about this, say for $k = 2$,
one needs the notion
of a {\em pairing function\/}, namely a {\em bijection\/}
from $\Sigma^* \times \Sigma^*$ onto $\Sigma^*$
(or from $\Nat \times \Nat$ onto $\Nat$).
In this course, I have not found a result where this matters;
though for the record, I seem to have been the first
person to construct a pairing function which is computable
by a finite automaton (which implies that
its graph is a 3-ary rational relation).
Heading in the other direction, a useful feature of this
tupling function is that it works unambiguously for any $k$;
in other words, it is a full-fledged
{\em sequence encoding function\/}.
Logicians working in terms of the arithmetical operations
$+$ and $\times$ found themselves needing to resort to
exponentiation to define sequence-encoding functions,
the most famous of which is called
{\em G\"odel's $\beta$-function\/}, namely
$\beta(x_1,\dots,x_k) = 2^{x_1}3^{x_2}5^{x_3}\dots$,
using the first $k$ primes.
\footnote{I still need to check my memory of this.}
Smullyan's thesis \cite{Smu61} was hailed for the
simplifications that result from considering
{\em concatenation\/} of strings as a basic operation, and
in retrospect, for giving logic a more
``computer-sciencey'' look.
The other tupling function, attributed to UB's John Myhill by
Wrathall, pads all of $x_1,\dots,x_k$ out to the same
length by trailing ``dummy characters'' @, and then
{\em shuffles\/} their bits.
I'll use the notation $[x_1,\dots x_k]$ when the distinction
between this ``parallel'' tupling function and the above
``serial'' function matters.
\subsection{Generalized Homomorphisms}
Fix numbers $d,e > 0$. Given a finite function
$h: \Sigma^d \into \Gamma^e$, consider the function
$h_*: \Sigma^* \into \Gamma^*$ defined inductively by:
\begin{itemize}
\item
{\em Basis.\/} For all $x \in \Sigma^*$ such that $|x| < d$,
$h_*(x) := \epsilon$.
\item
{\em Induction.\/} For all $x \in \Sigma^*$ such that
$|x| \geq d$, there is a unique way to write $x = vw$ such
that $|v| = d$, and then $h_*(x) := h(v)h_*(w)$.
\end{itemize}
Then call $h_*$ a {\em generalized homomorphism with fixed pitch\/}
$d$:$e$, or for short, a {\em $d$:$e$ \gh\/}.
Note that $e/d$ need not be a fraction in lowest terms.
A $d$:$e$ gh can be identified with an ordinary homomorphism
from the ``compound alphabet'' $(\Sigma^d)$ to $(\Sigma^e)$,
except for the way the basis truncates strings whose
lengths are not an integral multiple of $d$.
For example, the function $a(00) = 0$, $a(01) = 0$, $a(10) = 0$,
$a(11) = 1$ defines a 2:1 gh which takes the logical AND of
successive pairs of bits, and ``vectorized OR'' is likewise
a 2:1 \gh.
Negation, i.e.\ flipping bits, is a 1:1 gh.
The concept of a \gh includes any
ordinary homomorphism $h : \Sigma^* \into \Gamma^*$ such that
the values $h(c)$ over $c \in \Sigma$ all have the same length
(I've seen this called a ``balanced homomorphism'').
However, it does not include homomorphisms with varying
lengths, in particular {\em erasing homomorphisms\/} such as
$e(1) = 1$, $e(0) = \epsilon$.
Moreover, because of the way truncation is handled,
a $d$:$e$ $\gh$ $h$ may lack the characteristic property that
for all $x,y \in \Sigma^*$,
$h(xy) = h(y)h(y)$.
The {\em intent\/} of the definition is that each output
symbol depends only on finitely-many input symbols in
pre-set locations. More important, if one draws lines
from each output symbol to the input symbols it depends on,
the resulting diagram is a string of {\em disjoint\/}
``blocks.''
[At this point I drew diagrams of the above examples and
some others.]
The other principal motivation of the definition is the
following simulation of a Turing machine.
\begin{theorem}\label{TM-to-gh}
For every single-tape Turing machine $M$, there is a
composition $g_2 \circ g_1 \circ g_0$ of three gh's
such that for every ID $I$ of $M$,
$g_2 \circ g_1 \circ g_0(I) = J$ such that
$I \vdash_M J$. That is, the gh's compute the
next-ID function of $M$.
\end{theorem}
\proofsketch
Recall the coding of IDs using the {\em ID alphabet\/}
$\Gamma_I = \Gamma \cup (Q \times \Gamma)$ of $M$.
The {\em idea\/} is that $g_0$ updates cells
$0,3,6,9,\dots$ of the tape,
$g_1$ updates cells $1,4,7,10,\dots$, and
$g_2$ updates cells $2,5,8,11,\dots$ and finishes the job.
Each gh is 3:3 (not 1:1).
This works because the status of the cell in position $p$ at a given time
$t$ depends only on the status of cells $p-1$, $p$, and
$p+1$ at time $t-1$.
[Here I drew a diagram showing the dependencies. The class
said later it looked like three tiers of ``Marching Ms.''
When the idea was set, I admitted
there was a ``tiny fib'' in the statement of the theorem, and
invited discussion. The ``fib'' is that since $g_1$ begins
its work in cell~1, it is not really {\em composed\/} with
the output of $g_0$. Put another way, what I drew might
be called a ``cascaded composition,'' but it is not a
composition in the formal (sequential) sense.
The class was challenged on the first problem set
to devise a definition of ``generalized homomorphism''
which makes the theorem valid, and to decide certain
properties of it, such as whether the class of functions
so defined is closed under composition.
The exercise was also intended as one in ``research taste.''
Now t term's end, {\em I'm\/} still not sure what should
be the best formal definition, though I lean toward
the following:
$g$ should have the form $\phi_1\cdot h \cdot \phi_2$ where
for some numbers $c,d,e$ with $c < d$, $\phi_1$ maps
$\Sigma^c$ to $\Gamma^*$, $h$ is a $d$:$e$ gh, and
$\phi_2$ is a function of the last up-to-$d-1$ symbols
left over after $h$ is done.
Probably one should also stipulate that the length of the
output of $\phi_1$ and $\phi_2$ depends only on the length
of the input. Note that this definition does not
include erasing homomorphisms, so it's not really a
{\em generalization\/} of homomorphisms.
Good names for it are still welcome!]
% \lecture{04}{September 13}{K.W. Regan}{Debra Burhans and Kannan Govindarajan}
% **** YOUR NOTES GO HERE:
\section{The Chomsky Hierarchy}
[Lectures 4--5, scribed by Debra Burhans and Kannan Govindarajan.]
\begin{definition}
A {\em Grammar} is a 4-tuple (V, T, P, S) where
\begin{enumerate}
\item V is a non-empty set of {\em variable} symbols.
\item T is a non-empty set of {\em terminal} symbols.
\item P is a set of {\em productions} of the form $( {\rm V} \cup {\rm T} )^+ \rightarrow ( {\rm V} \cup {\rm T} )^*$.
\item S $\in$ V is the {\em start symbol}.
\item ${\rm V} \cap {\rm T} = \phi$.
\end{enumerate}
\end{definition}
Table \ref{tbl:ch} summarises the 4-level Chomsky hierarchy.
The linear grammars are strictly more powerful than type 3 grammars, though they are not as
powerful as type 2 grammars. Examples of simple linear grammars which are not regular are:
\begin{itemize}
\item ${\rm A} \rightarrow 0{\rm B}~|~ \epsilon.~ ~ {\rm B} \rightarrow {\rm A}1$.\\
This grammar accepts the language \{$0^n1^n | n \geq 0$\}, which is not regular.
\item ${\rm A} \rightarrow 0{\rm A}0~ | ~ 1{\rm A}1 ~ | ~ 0 ~ | ~ 1 ~ | ~ \epsilon$.\\
This grammar generates palindromic strings over the alphabet \set{0,1}, which is a known
non-deterministic \CFL, and {\em not} a \DCFL.
\end{itemize}
\begin{table}[p]
\begin{center}
\begin{tabular}{||c|c|c||} \hline
& & \\
A Grammar is & If every production has the form & Equivalent machine class \\ \hline \hline
Type 0 (\RE) & $( {\rm V} \cup {\rm T} )^+ \rightarrow ( {\rm V} \cup {\rm T} )^*$ & \TM\\ \hline
The Normal Form is & V $\rightarrow$ T & \\
& VV $\rightarrow$ VV & \\
& V $\rightarrow$ VV & \\
& V $\rightarrow \epsilon$ & \\ \hline \hline
Type 1 (\CSL) & V $\rightarrow$ T or $\alpha \rightarrow \beta$ &\NLBA \\
& where $\alpha , \beta \in {\rm V}^+$ \footnotemark[1] and $\mid \alpha \mid ~ \leq ~ \mid \beta \mid$ & \\ \hline
The Normal Form is & V $\rightarrow$ T & \\
& V $\rightarrow$ VV & \\
& VV $\rightarrow$ VV & \\ \hline \hline
Type 2 (\CFL) & V $\rightarrow ~ ({\rm T} \cup {\rm V} )^*$ & \NPDA \\ \hline
Chomsky Normal Form & V $\rightarrow$ VV & \\
& V $\rightarrow$ T & \\ \hline
Greibach Normal Form & V $\rightarrow$ T${\rm V}^*$ & Real-time NPDA \\ \hline \hline
Type 3 (\REG) & & \FA \\ \hline
Left Linear & V $\rightarrow$ V${\rm T}^*$ & \\
& V $\rightarrow$ ${\rm T}^*$ & \\ \hline
Right Linear & V $\rightarrow$ ${\rm T}^*$V & \\
& V $\rightarrow$ ${\rm T}^*$ & \\ \hline
Strongly Regular & V $\rightarrow$ VT & \\
& V $\rightarrow$ T & \\ \hline
Strongly Regular & V $\rightarrow$ TV & \\
& V $\rightarrow$ T & \\ \hline \hline
Linear & V $\rightarrow$ ${\rm T}^*$V${\rm T}^*$ & \\
& V $\rightarrow$ $T*$ & \\ \hline
Simple Linear & V $\rightarrow$ TV & \\
& V $\rightarrow$ VT & \\
& V $\rightarrow$ T & \\ \hline \hline
\end{tabular}
\end{center}
\caption{The Chomsky Hierarchy}
\label{tbl:ch}
\end{table}
\footnotetext[1]{ By special dispensation, the length decreasing production $S_{00} \rightarrow \epsilon ~ | ~ S$ is permitted in case type 1 languages contain the empty string.}
\newpage
\section{Known Results and Open Problems}
\subsection{Determinism and Non-determinism}
\begin{enumerate}
\item Every language which is accepted by an \NTM ~ is accepted by a \DTM, so for any type 0
language we need not specify whether the \TM ~ that accepts the language is deterministic or
non-deterministic.
\item Every language which is accepted by an \NFA ~ is accepted by a \DFA, so for any type 3
language we need not specify whether the \FA ~ that accepts the language is deterministic or
non-deterministic.
\item It is known that there exist languages which are accepted by an \NPDA ~ which are not accepted
by any \DPDA, so the correct machine equivalent for type 2 languages is the \NPDA.
\item It is not yet known whether \NLBA ~ is equivalent to \DLBA. The best known result is Savitch's
theorem which shows that \NLBA ~ $\subseteq$ \DSPACE($n^2$).
\end{enumerate}
% \lecture{05}{September 15}{K.W. Regan}{Debra Burhans and Kannan Govindarajan}
% **** YOUR NOTES GO HERE:
\begin{enumerate}
\item Every $2\HDFA$ ~ language is in $\NC^1 \Longleftrightarrow$ \LOGSPACE = $\NC^1$.
\item \{w\#w $|$ w $\in \set{0,1}^*$ \} and \{p\#t $|$ p is a substring of t\} are
not \kHDFA ~ languages for any k.
\end{enumerate}
\subsection{Machine Definitions}
\subsection*{Turing Machine}
The elements of the generalised Turing Machine are:
\begin{enumerate}
\item The input tape alphabet $\Sigma$.
\item The work tape alphabet $\Gamma$ = $\Sigma \cup \{ B \}$.
\item A read-only input tape. Input tapes can be real-time (only right moves allowed) or
one-way (no left moves allowed).
\item A read-write work tape. A {\em WORM} work tape is a
Write Once Read Many tape, and a {\em monotone} work tape can write a 1 over a 0, but not vice versa.
Work tapes always have one two-way head. A {\em stack-restricted} work tape is one in which
in any left move by the head the $B$ character must be written (POP).
\end{enumerate}
One can now define the usual kinds of automata in terms of this $\TM$ model.
\begin{enumerate}
\item A $\DFA$ is a $\DTM$ which consists of one real-time input tape and no
work tape.
\item A $\DPDA$ is a $\DTM$ which has a one-way input tape, and has a stack-restricted
work-tape.
\end{enumerate}
There are other generalisations (or restrictions) of the {\em stack-restricted} $\DTM$ depending
on the kinds of operations that the $\DTM$ is allowed (or not allowed) to perform on the stack. Some
of these are
\begin{enumerate}
\item A stack automaton can operate in two modes, a {\em pushdown} mode on top
of the stack or a {\em reading} mode in the interior of the stack, where it
can read the symbols on the stack but cannot write.
\item A {\em non-erasing} stack automaton, can push symbols but not pop
symbols from the top of the stack.
\item A {\em checking} automaton is a {\em non-erasing} automaton which can
push symbols on top of its stack as long as it is in the {\em pushdown} mode, but
once it enters the {\em reading} mode, it cannot return to the {\em pushdown}
mode.
\end{enumerate}
\section{Deterministic Pushdown Automata}
[Lectures 5--6, scribed by Burhans and Govindarajan.]
\begin{definition}
A $\DPDA$ M is defined\footnotemark as the 6-tuple (Q, $\Sigma$, $\Gamma$, $\delta$, B, s, F)
where:
\begin{enumerate}
\item Q is a finite set of states of the $\DPDA$.
\item $\Sigma$ is the finite ``terminal'' alphabet.
\item $\Gamma$ is the finite ``stack'' alphabet.
\item $\delta$ is the transition function of the $\DPDA$.
\mbox{ $\delta : (Q \times \Sigma \times \Gamma) \longrightarrow (\Gamma^* \times \set{R,S} \times Q)$}
\item s $\in$ Q, is the start state of the $\DPDA$.
\item F $\subseteq$ Q, is the set of final states of M.
\end{enumerate}
\end{definition}
\footnotetext{This definition is cosmetically different from the definition in the text
\cite{HU79}. We have left out the bottom of stack marker.}
This definition allows $\delta$ to contain tuples of the form (p,a,A;X,D,q)
where p,q $\in$ Q, a $\in \Sigma$, A $\in \Gamma$, X = $X_1 X_2 \ldots X_n \in \Gamma^*$ and D $\in$ \set{R,S}. $X_1$ is the new top of stack character.
The kinds of transitions that a {\em stack-restricted} $\DTM$ might perform
to simulate the above move of the $\DPDA$ would be
\begin{enumerate}
\item [(n+1).]pop A. If X = $\epsilon$, go to step 0.
\item [n.]push $X_n$.
\item [(n-1).]push $X_{n-1}$.\\
\vdots
\item [1.]push $X_1$.
\item [0.]move input head in direction D.
\item [-1.] go to state q.
\end{enumerate}
An $\epsilon$-move in our $\DPDA$ definition is a tuple of the form (p,a,A;X,S,q)
that is an $\epsilon$-move is characterised just by the input head not moving.
This is more general than the text definition of an $\epsilon$-move because
the text puts in an $\epsilon$ instead of the 'a' in (p,a,A;X,S,q) and enforces
another restriction that there should be no other ``reading'' tuple for p and A in the
transition function. Our definition does allow tuples of the form (p,b,A;Y,R,r)
for some other character b in the input alphabet, in the transition function.
\paragraph{Normal Forms and Acceptance conditions of $\DPDA$s}
We can assume that the DPDA M, in its first transition, writes a {\tt \#} as a
bottom of stack marker. M, then never writes another {\tt \#}, nor does it pop
the {\tt \#} except possibly at the end.
There are two commonly accepted acceptance conditions for $\DPDA$s. These are:
\begin{enumerate}
\item The ``Freeze'' condition. The $\DPDA$ after undergoing a transition (p,b,A;Y,R,r)
where b is the last character of the input and r is a final state, just ``freezes'' and halts.
\item The ``Musical Chairs'' condition. After exhausting its input, the $\DPDA$
is allowed one transition (q,B,A;$\epsilon$,S,r) and it accepts if and only if
r is an accepting state. This accepting condition similar to the first if
there were an explicit end-of-input marker \$ at the end of the input string.
\end{enumerate}
% \begin{thebibliography}{999999}
% \bibitem [HU79] {HU79}
% John E. Hopcroft and Jeffrey D. Ullman, ``Introduction to Automata
% Theory, Languages and Computation'', Addison Wesley, 1979.
% \end{thebibliography}
% \lecture{06}{September 20}{K.W. Regan}{Debra Burhans and Kannan Govindarajan}
\subsection{Normal Forms of $\DPDA$s}
\begin{theorem}
For every $\DPDA$ M (under either acceptance condition), there exists a $\DPDA$
M', which is total and such that L(M) = L(M').
\end{theorem}
Totality means that M' reads all of its input and halts on every input.
Kripa's question: Why should the $\DPDA$ be made to read all of its input for
it to be total? Why isnt halting on all inputs enough irrespective of whether
all the input has been read or not?
\begin{proof}
Suppose we are given the $\DPDA$ M = (Q, $\Sigma , \Gamma , \delta, \wedge$\footnotemark, s, F)
\footnotetext{When we use the $\wedge$ as an explicit bottom marker, we assume
that the $\DPDA$s dont have to explicitly push down a bottom of stack etc. In
the Turing Machine formalism, the blank symbol B, is treated as the bottom of stack marker.}
We first arrange for the transition function $\delta : {\rm Q} \times \Sigma \times \Gamma \rightarrow \Gamma^* \times \set{R,S} \times {\rm Q}$
to be total by adding a dead state d in which M first pops the stack down to the
$\wedge$, finishes reading the input before halting. So if the machine M halts
on its input, it is clear that the $\DPDA$ M' constructed by altering the transition
function will also halt and will read its input in its entirity. Also
M' accepts an input X if and only if M itself does.
The $\DPDA$ M can diverge on some input if one of two things happen:
\begin{enumerate}
\item M loops among a set of states without progressing on the input. For example
if $\delta$ has tuples like (q,0,A;B,S,r) and (r,0,B;A,S,q), M would loop
among states q and r if in state q with A on top of stack it comes across a 0
in the input.
\item M could also diverge by pushing an indefinite number of symbols on the
stack.
\end{enumerate}
We now introduce a few informal notions:
\begin{enumerate}
\item If the machine does a ``pop'', we regard that as making progress.
\item A semi-ID is a triple of the form (state, input character, top of stack).
\end{enumerate}
If one looks at the semi-IDs that the machine goes through while performing
some computation, we immediately see that if the machine does not diverge then
we can repeat semi-IDs as long as the stack is ``shrinking'' between consecutive
appearances of the semi-ID. In any segment of a computation by the machine M, in
which a stack symbol A is never popped, the computation is unaffected by symbols
which are under the symbol A. We can use this fact to find semi-IDs (p,c,A) in which
A is never popped, and the input head is also not moved. If we succeed in finding
in such semi-IDs, then we know that M can diverge on some input.
For each c $\in \Sigma$, define the directed graph G$_c$ by:
\begin {eqnarray*}
V_c & = & Q \times \Gamma.\\
E_c & = & \{ (p,A) \rightarrow (q,B) : \delta(p,c,A) = (\overline{X}, \overline{S}, q)
\end{eqnarray*}
where $\overline{X}$ begins with the new top of stack symbol B. Note that
this requires $\overline{X} \neq \epsilon$. If $\overline{X} = \epsilon$ then
this is a ``pop'' move and M has made ``progress''.
\begin{proposition}
$\forall$ X, M(X) diverges iff the computation semi-ID (p,c,A) s.t. in G$_c$, node
(p,A) is on a directed cycle.
\end{proposition}
It turns out that this definition of the graph G$_c$ isnt powerful enough
as it does not take into account ``pop'' moves, so we define the graph
differently as follows:
\begin {eqnarray*}
V_c & = & Q \times \Gamma.\\
E_c & = & \{ (p,A) \rightarrow (q,B) : \delta(p,c,A) = (\overline{X}, \overline{S}, q)
\end{eqnarray*}
To construct the edges in G$_c$, we start with some node (p,A) and we run M
starting it off in semi-ID (p,c,A) and if (p,c,A) $\vdash$ (q,c,$\stackrel{B}{A}$), then add edge (p,A) $\rightarrow$ (q,B) to E$_c$, until one of the following
happens:
\begin{enumerate}
\item M moves the input head right.
\item M reaches state p again scanning A again.
\item M repeats some other (q,B) in same manner as 2.
\item M pops the A it started with.
\end{enumerate}
While none of 1-4 happens, add edges from (p,A) to every semi-ID (q,B)
encountered on the way.
\begin{claim}
At least one of 1-4 happens after atmost $\| {\rm Q} \| \times \| \Gamma \|$ steps.
\end{claim}
One can now construct all the edges in the graph by doing the above for
every node in the graph G$_c$.
\begin{proposition}[Correct Proposition]
$\forall$ X, M(X) diverges iff, M(X) reaches a semi-ID (p,c,A), s.t. (p,A)
is on a directed cycle in the graph G$_c$.
\end{proposition}
\begin{proof}[$\Leftarrow$]
If M on input X reaches a semi-ID which is on a directed cycle then it
obviously does not halt, and hence it diverges.
\end{proof}
\begin{proof}[$\Rightarrow$]
Suppose M diverges, then $\exists$ c on the input tape such that M does
not read any input symbol after c. Let p be the state and A be the symbol
on top of the stack when the $\DPDA$ first scanned the character c.
Since the $\DPDA$ did not progress further on the input tape nor did it
pop A off the stack, in the graph G$_c$ there is a cycle. Since each
node in G$_c$ corresponds to a semi-ID that M reaches in its computation
it is clear that M reaches a semi-ID (q,c,B) such that (q,B) is in a cycle
in the graph G$_c$.
\end{proof}
The final construction that yields the machine M' which accepts the same
language as M which is total consists of the following construction.
For every node (q,B) in G$_c$ which is on a cycle, change the transition
function $\delta$ so that $\delta$(q,c,B) $\rightarrow$ ``dead state''.
This construction will now ensure that the $\DPDA$ M' will read
the entire input and halt even if M did not halt.
\end{proof}
% \lecture{7}{September 22}{K.W. Regan}{Daniel F. Boyd, Michael J.
% Smolowitz}
\subsection{Digression: discussion of problem about reducibility relations}
[Lecture 7, scribed by Daniel Boyd and Mike Smolowitz.]
\bigskip
Just when will a reducibility relation be reflexive?
For a reducibility relation on a class of functions $\CF$ to be
reflexive, for all languages $A$ it would have to be true that $A
\leq_\CF A$. Then for all $A \subseteq \Sigma^*$, there exists a
function $f\in \CF$ such that for all $x \in A$, $x\in A \iff f(x) \in
A$.
So if $A = \emptyset$, then it's easy. $\emptyset \leq_\CF \emptyset$.
Well, this certainly looks like $\CF$ has to contain the identity
function, but we can fool around to remove even this condition:
Let $a_1$, $a_2$ be elements of $A$.
$$
f(x) = \cases{
a_2 & if $x=a_1$\cr
a_1 & if $x=a_2$\cr
x&otherwise}
$$
Then $f$ isn't the identity in $\CF$, yet $A\leq_m A$ via $f$.
The last case is if $||A|| = 1$. We know that $A\leq_m^\CF B$ via $f$
if and only if $\bar A \leq_m^\CF \bar B$ via $f$. So apply the last
case to $A$.
Warning: $A\leq_m B$ via $f$ means $A = f^{-1}(B)$, but is not the same
as $f(A) = B$.
{\bf Question:} Is it true that whenever, all functions in $\CF$ are
recursive, then $\leq^\CF$ is reflexive if and only if $\CF$ contains
the identity?
\section{Closure properties of CFLs}
[Lectures 7--8, scribed by Boyd and Smolowitz.]
\bigskip
Fact: The DCFLs are closed under complementation, but not closed under
intersection or union. For example:
$$ L = \{a^i b^j c^k : i=j \} $$
$L$ is the intersection of two DCFLs, yet $L$ is not CF.
But DCFL is closed under intersection with a regular set. A simple
sketch of this: let $D$ be a DPDA for a CFL $A$, and let $M$ be a DFA
for a regular language $R$. Define the DPDA $D'$ (which will accept
$A\cap R$) by the following sets of states and final states:
\begin{eqnarray*}
Q&=&Q_D\times Q_M \\
F'&=&F_D\times F_M
\end{eqnarray*}
The machine $D'$ runs a copy of $M$ in parallel with the finite
control of $D$. Whenever $D$ makes a right move on the input tape,
the simulated $M$ gets to make a transition on the new input symbol.
The combined machine accepts only when both of its components are
simultaneously in accepting states.
\subsection{Monoid of transformations}
One way of talking about $\Sigma^*$ is to call it the free monoid over
$\Sigma$ with operation $\cdot$ (concatenation). So don't be afraid
of the words `free monoid'.
\begin{definition}
Let $M = (Q, \Sigma, \delta, s, F)$ be a DFA. The monoid of
transformations $\CM$ of $M$ is defined as the collection of mappings
$g_c\colon Q\to Q$ over all $c\in \Sigma$ where $g_c(q) = \delta(q,
c)$, together with the identity and with their closure under
composition. ($\CM$ is 'generated' by the $g_c$s.
\end{definition}
\begin{example}
Let $\Sigma = \{a, b\}$. Consider this DFA
(start and final states are unimportant.)
Then $g_a$ is the transformation on $\{0, 1, 2\}$ performed by this
machine on reading an $a$. If in state 0 initially, an $a$ takes you
to state 1. If in state 1, an $a$ takes you to 2. In state 2, an $a$
takes you to state 0. This is written as $ g_a = {0 \quad 1 \quad 2
\choose 1 \quad 2 \quad 0}$, which is standard notation for
permutations.
Now note that $g_b$ isn't a permutation, because it has two 2s.
\centerline{
\hskip 2in
\vbox{\psfig{file=LN07fig1.eps}\vskip 1in}
\hss
\vbox{
\begin{eqnarray*}
g_a &=& {0 \quad 1 \quad 2 \choose 1 \quad 2 \quad 0}\\
g_b &=& {0 \quad 1 \quad 2 \choose 2 \quad 0 \quad 2}\\
g_{ab} &= g_b \cdot g_a = & {0 \quad 1 \quad 2 \choose 0 \quad 2 \quad 2}\\
g_{aa} &= g_a \cdot g_a = & {0 \quad 1 \quad 2 \choose 2 \quad 0 \quad 1}
\end{eqnarray*}
}
}
Note: the identity need not be in the composition of the $g_c$s, if
some state is a {\em source\/} in the graph of $\delta$.
\end{example}
Now, $\CM$ has the identity $g_\emptystring(q) = q$. $\CM$ is closed
under $\cdot$ (composition). $\cdot$ is associative and is {\em
something else which I didn't write down\/}. Anyway, these properties
define a monoid or a semigroup.
If for all $g\in \CM$, there exists an $h\in \CM$ such that $h \cdot g$
is the identity, then $\CM$ becomes a group (leaving behind the
pastures of immature monoidality. This can happen if and only if
every $g_c$ is a permutation.
Elements of $\CM$ can be encoded over the alphabet
$$
Q^Q = \{|Q|-\hbox{tuples of elements in} q\}
$$
$g\in \CM$ is encoded as the single combination character $(g(q_0),
g(q_1), g(q_2) \ldots g(q_{|Q|-1}))$.
\begin{definition}
The ``annotation'' of a string $w\in \Sigma^+$ by $M$ is the string
$w'$ of the same length over alphabet $Q^Q \times \Sigma$ such that
$$\forall i, w_i' = (g_{w_i w_{i+1}\cdots w_n}, w_i).$$
This gives information about the last state reached by $M(w)$ given
the state of $M$ before reading $w_i$.
\begin{example}
$w=abab$
$$
w' =
\underbrace{0 \quad 1 \quad 2 \choose 0 \quad 2 \quad 2}_{q_{abab}}
\underbrace{0 \quad 1 \quad 2 \choose 2 \quad 0 \quad 2}_{g_{bab}}
\underbrace{0 \quad 1 \quad 2 \choose 0 \quad 2 \quad 2}_{g_{ba}}
\underbrace{0 \quad 1 \quad 2 \choose 2 \quad 0 \quad 2}_{g_{b}}
$$
\end{example}
\end{definition}
This is a diagram that showed up here somewhere. Typically I include
such diagrams so they can be deleted later if someone thinks they
don't mean much.
\begin{figure}[t]
\centerline{\psfig{file=LN08fig1.eps}}
\caption{Inclusion diagram}
\end{figure}
The *-free regular languages are those that are representable with
$\cup$, $\cap$, $\cdot$, but no Kleene*. Also, $\NC^0 \subset \AC^0$.
\begin{notation}
Let $D$ be a DPDA. We will denote an ID of $D$ as $(q, \alpha, x)$
where $q$ is the current state of $D$, $\alpha = \alpha_1 \alpha_2
\ldots \alpha_m$ is the current contents of the stack with $\alpha_1$
at the top, and $x$ is the remaining portion of the input on the input
tape.
\end{notation}
\begin{lemma}
(This is in [HU79] as lemma 10.5 in section 4.)
Let $D$ be a DPDA, and $M$ be a DFA with states $\{p_0\ldots p_k\}$.
Then $D$ can be modified to $D'$ such that in any ID $(q, \alpha,
x)$ of $D$, the corresponding ID of $D'$ has $\alpha'$ fully
annotated by $M$. In other words, $D'$ has on its stack
$$\alpha' =
\left(
\begin{array}{c}
\delta^*_M(p_0, \alpha)\\
\delta^*_M(p_1, \alpha)\\
\vdots\\
\delta^*_M(p_k, \alpha)
\end{array},
\alpha_1
\right)
\cdots
\left(
\begin{array}{c}
\delta^*_M(p_0, \alpha_{m-1}\alpha_m)\\
\delta^*_M(p_1, \alpha_{m-1}\alpha_m)\\
\vdots\\
\delta^*_M(p_k, \alpha_{m-1}\alpha_m)
\end{array},
\alpha_{m-1}
\right)
\left(
\begin{array}{c}
\delta^*_M(p_0, \alpha_m)\\
\delta^*_M(p_1, \alpha_m)\\
\vdots\\
\delta^*_M(p_k, \alpha_m)
\end{array},
\alpha_m
\right)
$$
\end{lemma}
Idea:
Looking at the top stack symbol $\alpha_1'$ tells what $M$ would do on
$\alpha$. More concisely,
$$\alpha' =
(g_\alpha, \alpha_1)
(g_{\alpha_2\cdots\alpha_m}, \alpha_2)
(g_{\alpha_3\cdots\alpha_m}, \alpha_3)
\cdots
(g_{\alpha_{m-1}\alpha_m}, \alpha_{m-1})
(g_{\alpha_m}, \alpha_m)$$.
\begin{proof}
Use a normal form for $D$ in which every move has the form $(q, c,
A, \emptystring, \{R, S\}, r)$ (a POP move) or $(q, c, A, BA, \{R,
S\}, r)$ (a PUSH move).
Building $D'$: Initially, stack contains $\wedge$. (We may
suppose that DFA $M$ doesn't ever run on $\wedge$ or $g(\wedge)$ is
the identity on $Q_M$.)
Invariant: stack is nonempty and fully annotated.
POP moves preserve the invariant (nothing to do).
In PUSH moves, $D'$ reads $\delta^*(p_i, A\alpha_2 \alpha_3\ldots
\alpha_m)$. $D$ wants to write, for each state $p_i$,
$$
\delta^*(p'_i, BA\alpha_2\ldots \alpha_m) = \delta^*(\delta(p'_i), A
\alpha_2\ldots \alpha_m)
$$
and this can be computed locally since the ``A'' info is already
there. $g_{BA\alpha_2\ldots\alpha_m} = g_B \cdot
g_{A\alpha_2\ldots\alpha_m}$. This works for other annotations,
too.
\end{proof}
% a WIERD ASIDE follows
\begin{Comment}\label{MinL}
Define $\Min(L) = \{w\in L : (\not\!\exists v \in \Sigma^+) wv\in L\}$.
This is somewhat like forcing $L$ to have the prefix property, by
throwing away any string that has an extension that is also in $L$.
\end{Comment}
\begin{theorem}
If $L \in \DCFL$, then so is $\Min(L)$. (The proof prefers the
``freeze'' DPDA for the pruning proof.)
\end{theorem}
\begin{corollary}
If $L\in \CFL$ and $\Min(L)\notin \CFL$ then $L \notin \DCFL$.
\end{corollary}
\begin{figure}[t]
\centerline{\psfig{file=LN08fig2.eps}}
\caption{Motivation}
\end{figure}
\begin{proposition}\label{MinLregular}
If $L$ is regular, then $\Min(L)$ is regular.
\end{proposition}
\begin{proof}
Delete all arcs out of final states of DFA for $L$.
\end{proof}
\begin{Comment}
(Added by DFB) I think this conflicts with the given definition of
$\Min$. Consider
$$\Min(a^*) = \{ a^n : (\not\!\exists a^m, m>0)\; a^n a^m \in a^*\}
= \{ a^n : (\not\!\exists m>0)\; n+m \in \N\} = \emptyset.$$
In other words, $\Min(a^*)$ is the set of all strings of a's such
that there isn't a longer string of a's. That's the empty set.
I think something is wrong with this definition.
\end{Comment}
{\em Answer by KWR:\/}
Touch\'e: evidently I got $\Min(L)$ and $\Max(L)$ confused in
my lecture (or you did). The definition in Comment \ref{MinL} is for
$\Max(L)$, but the two stated results are indeed for
$\Min(L)$. $\Max(a^*) = \emptyset$ and $\Min(a^*) = \set{\emptystring}$.
Pages 244-245 of \cite{HU79} set the record straight.
%\lecture{09}{September 27}{K.W. Regan}{Dan Boyd, Mike Smolowitz}
% **** YOUR NOTES GO HERE:
\section{Predicting Machine Construction}
[Lecture 9, scribed by Boyd and Smolowitz.]
\begin{theorem}
Let $D$ be a DPDA, and let $M$ be a DFA. Then $D$ can be modified to $D'$,
which maintains in its top stack symbol $Z$ the information $\Delta_Z$.
$\Delta_Z$ is the set of pairs $(p,q)$, where $p \in Q_M$ and $q \in Q_D$,
such that there is a $w \in \Sigma^*$ such that: $M$ started in state $p$
accepts $w$, and $D$ started in state $q$ with the whole current stack
accepts $w$.
\end{theorem}
The idea is that as you begin reading the input $x$, you update the
``foreknowledge.''
\begin{corollary}
Let $L$ be a DCFL, and let $B$ be any regular set. Define the quotient
$L/B = \{x \in \Sigma^* : (\exists w \in B) \, xw \in L\} $. Then $L/B$ is a DCFL.
\end{corollary}
\begin{Comment}
\begin{theorem}
If $L$ is regular and B is {\it arbitrary}, then $L/B$ is regular.
\end{theorem}
\begin{proof}
Construct a DFA $M_L$. Put $q \in F'$ if $\exists y \in B$ such that M started
in state $q$ on $y$ accepts.
\end{proof}
\end{Comment}
One point of the DCFL theorem is that when B is regular, $\Delta_Z$ can be
defined constructively. The intuitive reason is that the problem:
\begin{quote}
INSTANCE: A CFL $A$, a regular set $B$.
QUESTION: Is $A \cap B \neq \emptyset$?
\end{quote}
is decidable.
\medskip
\noindent \begin{proof} (DCFL Theorem)
\noindent {\it Basis.}
$Z = \wedge. \quad \Delta_Z = \{(p,q) : L(M_p) \cap L(D_q) \neq \emptyset \} $,
where $L(M_p) = \{w \in \Sigma^* : \delta^*_M(p,w) \in F_m \}$
and $L(D_q) = \{w \in \Sigma^* : D$, started in state $q$, accepts $w\}$.
We need to solve $||Q_M|| \cdot ||Q_D||$ instances of that decision problem
to build $\Delta_\wedge$.
\medskip
\noindent Invariant: Every symbol $A$ on the stack has the correct symbol
$\Delta_A$ for the substack with that symbol as its top.
\medskip
\noindent Observation: $\Delta_A$ is independent of the bits of $x$ already
read, which are $x_0 \cdot \cdot \cdot x_{m-1}$.
\bigskip
\noindent Claim: It is sufficient to show how to update the stack in a move of
type $(q, c, A, BA, S, r)$.
\medskip
\noindent Reason:
\begin{itemize}
\item Whether the direction is $S$ or $R$ doesn't matter - it's independent
of the bits already used.
\item POP moves automatically preserve the invariant. In the NF (normal
form), either move is either ``POP $A$'' or ``PUSH $B$''.
\end{itemize}
\noindent {\it Induction Hypothesis.} $\Delta_A$ is correct.
The objective is to build $\Delta_B$ such that $\Delta_B$ depends {\it only}
on $D$ and $M$. We {\it can't} make $\Delta_B$ depend on the whole stack.
It does so indirectly, via $\Delta_A$. The {\it correctness} of $\Delta_B$
depends on the correctness of $\Delta_A$.
We want to put $(p,r)$ into $\Delta_B$ iff one of these two hold:
\medskip
\noindent (1) There is some string $u$ and $(p',q') \in \Delta_A$ such that:
$\delta_M^*(p,u) = p'$; and $D$, started in state $r$ with stack $B \atop
A$, gets to state $q'$ with stack $A$, with this being the first time after
state $q$ that $D$ scans $A$ again, and having read exactly $u$.
Idea: $w = uv$. If $(p',q') \in \Delta_A$, and (1) holds, then:
\begin{itemize}
\item There is a $v$ such that $D$ in state $q'$ with $A$ as the top-of-stack
accepts V.
\item There is a $w$ such that $D$ in state $r$ with $B$ as the top-of-stack
accepts $w = uv$.
\end{itemize}
\noindent (2) There is a $u \in \Sigma^*$ such that: $\delta_M^*(p,u) \in F_M$;
and $D$, started in state $r$ with stack $B$, never pops that $B$ and accepts
$u$.
\medskip
We have correctness, from (1) and (2). The construction reduces to solving
instances of the same decision problem.
\end{proof}
This is a top-down approach; the text does it from the bottom-up.
%\lecture{**LECTURE-NUMBER**}{**DATE**}{**LECTURER**}{**SCRIBE**}
%\lecture{10--14}{Sept.--Oct.}{K.W. Regan}{K.W. Regan}
% **** YOUR NOTES GO HERE:
\section{LR$(k)$ Grammars}
[Lectures 10--14, postpared by K.W. Regan.]
\bigskip
These notes get to the theoretical heart of the LR$(k)$ principle
with a minimum of new conceptual overhead.
It does not lead to the most efficient parsers for LR$(k)$
grammars, but provides a basis for addressing issues
of efficiency later.
Let $G = (V,T,P,S)$ be any context-free grammar.
Call $G$ ``start-normal'' if $S$ does not appear on the
right-hand side of any production. (It is trivial to change
any given CFG into one which is ``start-normal'' by adding
a new start symbol.) Let
$\rderives$ stand for `` generates by a rightmost derivation.''
The motivation is that an LR($k$) parser reading an input $x \in T^*$
works backward from $x$ to find a derivation of $x$, and since
the input is conventionally read left-to-right by a DPDA,
the desired derivations are rightmost.
\begin{definition}\label{LRkitem}
For any $k \geq 1$, an {\em LR$(k)$ item\/} for the CFG $G$ has
form either
\[
A \into \alpha \bullet \beta \on{z} \qquad \mbox{or} \qquad
A \into \alpha \bullet \beta \on{y\$},
\]
where $A \into \alpha\beta$ is a production in $G$,
$z \in T^k$, and $y \in T^{ |y|$. Then there exists $u \in T^*$ such that
$z = uy$. Then $u$ is the top portion of the stack,
meaning that the most recent moves by $D$ were to
shift $u$ from input to stack. Let $c$ be the first symbol of $u$,
and consider the earlier move when $D$ shifted $c$.
Since the form $\gamma w$ represented during these moves did
not change, at that point $\beta$ was its top of stack.
Now we claim that at this point, with $D$ scanning $c$ and the
next up-to-$(k-1)$ characters after $u$ being $v$, that the
complete item $B \into \beta \bullet \on{cv}$ was valid for $\delta_2 \beta$.
This is because $S \rderives \delta_2 B z$ and $z \supseteq cv$,
by the definition of validity. Thus $D$ would not have shifted
$c$ at that point; instead, it would have performed a reduction.
(ii)~$|z| = |y|$. Then $z = y$. By similar reasoning, with $cv$ now
being the first up-to-$k$ symbols of $y$ or $z$, the complete
item $B \into \beta \bullet \on{cv}$ is valid for $\gamma$, together
with the distinct item $A \into \alpha \bullet \on{cv}$ used in the
reduce move. But this violates the LR$(k)$ condition that no
two complete items which are valid for the same $\gamma$ can have
the same lookahead string.
(iii)~$|z| < |y|$. Then $y = uz$ for some $u \in T^*$.
Let $cv$ be the first up-to-$k$ symbols of $y$, and $\beta$
ends at the same place $u$ does.
First suppose that $\beta$ contains the symbol $c$, so
that $\beta$ has the form $\beta_1 c \beta_2$.
Let $dv'$ be the first up-to-$k$ symbols of $z$.
Then the incomplete item $B \into \beta_1 \bullet c \beta_2 \on{dv'}$
is valid for $\gamma$.
But condition (b) in the definition of LR$(k)$
states that then no complete item in $I^k(\gamma)$ should
have an ``on string'' which begins with $c$, and
$A \into \alpha \bullet \on{c}$ is such an item.
Finally, suppose $\beta$ is completely to the right of $c$
(this includes the subcase of (iii) where $\beta$ is empty).
Then there exists a string $u' \in T^*$ such that
$\eta_2$ = $\gamma c u' B z$.
Trace the purported rightmost derivation $S \rderives \eta_2$
backward until one reaches the step
in which $c$ was introduced. This step can be represented as
$\delta'' B' z' \rderive \delta'' \beta'_1 c \beta'_2 z'$.
Here $\beta'_2$ must contain a variable, since $B$ is to the
right of $c$ in $\eta_2$, and likewise all intermediate
steps between $\delta'' \beta'_1 c \beta'_2 z'$ and $\eta_2$
have variables to the right of $c$. Thus $\delta'' \beta'_1 = \gamma$.
Hence, with $dv'$ as the first up-to$k$ symbols of $z'$,
the incomplete item $B' \into \beta'_1 \bullet c \beta_2 \on{dv'}$
belongs to $I^k(\gamma)$, causing the same contradiction as before.
\bigskip
This proves the claim.
In particular, this proves that $D$ can never ``loop,''
since at some point there would have to be a branch off the
loop which goes back to $S$.
Finally, suppose $D$ enters its dead state at some point.
This can only happen if $I^k(\gamma)$ becomes empty, and
this could only happen after a reduce move, producing
$\delta A y$ from $\gamma y$, with reference to the above.
From the claim, it follows that $S \rderives \delta A y$
(note that the definition of valid item only gives
$(\exists w)\,S \rderives \delta A w$).
Trace the derivation backward from $\delta A y$ to $S$
until one finds the step in which the $A$ in introduced,
and by reasoning similar to (iii) above, this
yields a valid item in $I^k(\delta A)$.
This completes the proof of Theorem \ref{DPDA}.
\qed
\begin{corollary}
Every LR$(k)$ grammar is unambiguous.
\end{corollary}
\proof
It follows from the {\em Claim\/} in the last proof that there
cannot exist two different rightmost derivations from $S$ of any
terminal string $x$.
\qed
\bigskip
{\em Remarks:\/} I also think this settles another question implicit
in the text: the CFG $G$ need not be ``reduced'' in any form.
Deadwood symbols, unreachable symbols, $\epsilon$-productions,
even trivial productions such as $A \into A$ are all AOK.
(Unless $A$ is never used in a derivation, having $A \into A$
will automatically violate the LR$(k)$ conditions.)
It is worth scanning the proof of the main claim for
airtightness under the possibility that $\alpha$ and/or $\beta$
is empty---my way of breaking down the cases according to
$z$ vs.\ $y$ seems to handle that by itself.
My proof didn't use the clause that $D$ only shifts a
character $c$ when $I^k(\gamma)$ is nonempty and contains
some item with $c$ just to the right of the $\bullet$.
The clause isn't needed to describe the operations of $D$.
So what this proves is that when the parser runs on an input $x \in L(G)$,
there is always at least one valid item that corresponds to any shift move.
One in particular comes from the production which produced the
shifted character in the derivation of $x$; there may be others.
Similarly, even if the actual input $x$ is not in $L(G)$,
so long as $I^k(\gamma)$ is nonempty, there always is
at least one valid item which corresponds to the shift.
These remarks prove the equivalence of parsers with
slightly different programs from $D$ above.
\bigskip
Now we show how to convert a given DPDA into an equivalent LR$(1)$ grammar.
This shows the equivalence of DPDAs and LR$(k)$ grammars for all $k \geq 0$.
Following Hopcroft-Ullman, we take a detour via LR$(0)$ grammars for
$L(D)\$$, where $\$$ is a character not in $\Sigma$.
\begin{lemma}\label{niceNF}
For every DPDA $D$ we can find an equivalent DPDA $D'$ whose state set
$Q'$ can be partitioned into $Q_R \cup Q_S$, such that every
arc out of a state in $Q_R$ moves the input head right,
and every arc out of a state in $Q_S$ keeps the input head stationary
and does not depend on the input character scanned.
\end{lemma}
\noindent
This is pretty much how Hopcroft-Ullman defines a DPDA to begin with:
if a state has an ``$\epsilon$-move,'' then it has no other reading moves
(ch.\ 5, p113). The above is a little bit stronger in that
the input head's action doesn't depend on the stack symbol either.
This seems needed to make the grammar constructed below LR$(0)$.
To see this intuitively, imagine further that in a state in $Q_R$,
$D'$ first shifts the current input symbol $c$ to its stack before
making the move. Then every distinctive action by $D'$ is in a
transition which doesn't depend on the current input symbol at all,
and thus $D'$ functions with ``zero lookahead.''
But it is not necessary to make this latter modification explicitly
in order to see the LR$(0)$ property in the grammar.
\proof
Given $D = (Q,\Sigma,\Gamma,\delta,\wedge,s,F)$, let $Q_R$ be a
copy of $Q$, and take $Q_S := Q \times \Sigma$.
For all states $p \in Q_R$, wherever $D$ has a tuple
$(p,c,A,X,R,q)$, $D'$ has the same tuple. But wherever $D$ has
$(p,c,A,X,S,q)$, $D'$ instead has $p,c,A,X,R,(q,c))$.
Now in a state $(q,c)$ in $Q_S$, wherever $D$ has a tuple
$(q,c,B,Y,S,r)$, for all $d \in \Sigma$ $D'$ has the same tuple
$((q,c),d,B,Y,S,(r,c))$. And if $D$ has
$(q,c,B,Y,R,r)$, which finally reads $c$, then for all $d \in \Sigma$,
$D'$ has $((q,c),d,B,Y,S,r)$, which signifies that now $D$ has
``caught up with'' $D'$ so that $D'$ can go back to states in $Q_R$.
It is clear that $D$ and $D'$ have essentially
the same computations.
\qed
\begin{theorem}
For every DCFL $L$, we can find an LR$(0)$ grammar for $L \!\cdot\! \$$,
where $\$$ is not in the alphabet of $L$.
\end{theorem}
\proof
There exists a DPDA $D$ which accepts $L\$$, such that every accepting
computation simultaneously pops the initial bottom-of-stack character
$\wedge$ and goes to a unique accepting state $f$.
For ease of exposition, we suppose that $D$ is not only in the
normal form of Lemma \ref{niceNF}, but also uses only
PUSH and POP moves on its stack. That is, in every tuple
$(p,c,A,X,\mbox{D},q)$, either $X = \epsilon$ or $X = BA$ for some
$B \in \Gamma$ ($B = A$ allowed).
The CFG $G = (V,T,P,S)$ has $T = \Sigma \cup \set{\$}$ and
$V = \set{S} \cup (Q \times \Gamma \times Q) \cup
(Q \times (\Sigma \cup \set{e}) \times \Gamma \times Q)$, where
$e$ is a ``place-holder'' for the empty string.
The productions fall into six groups:
\begin{enumerate}
\item[(0)]
For all $p,q \in Q$, $c \in \Sigma \cup \set{\$}$, and $A \in \Gamma$,
$P$ has $[p,c,A,q] \into c$ and $[p,e,A,q] \into \epsilon$.
(This includes the productions $[p,\$,\wedge,f] \into \$$ for all $p \in Q$.)
\item[(1)]
%
% For all $g \in Q$, $P$ has $S \into [s,\wedge,g]$.
%
$P$ has $S \into [s,\wedge,f]$.
%
\item[(2)]
For each tuple $(p,c,A,\epsilon,R,q)$ in $\delta$, $P$ has
$[p,A,q] \into [p,c,A,q]$.
(This includes $[p,\wedge,f] \into [p,\$,\wedge,f]$ for all $p \in Q$.)
\item[(3)]
For each tuple $(p,c,A,\epsilon,S,q)$ in $\delta$, $P$ has
$[p,A,q] \into [p,e,A,q]$.
\item[(4)]
For each tuple $(p,c,A,BA,R,q)$ in $\delta$, and all $r,g \in Q$, $P$ has
$[p,A,r] \into [p,c,A,q][q,B,g][g,A,r]$.
\item[(5)]
For each tuple $(p,c,A,BA,S,q)$ in $\delta$, and all $r,g \in Q$, $P$ has
$[p,A,r] \into [p,e,A,q][q,B,g][g,A,r]$.
\end{enumerate}
\noindent
{\em Then\/} we apply to $G$ the (polynomial-time)
algorithm which eliminates all deadwood variables.
The resulting grammar has the property that whenever
$\gamma \in {V}^*$, there exists
some terminal string $v$ such that $\gamma \implies v$.
The intuition is that in (4) and (5), $g$ stands for a
{\em guess\/} as to what state $D$ will be in when the particular
$A$ next becomes top-of-stack.
Correct guesses yield a derivation which mimics the actions of $D$
in an accepting computation, while any one incorrect guess will
be shown to kill any chance that a terminal string can be derived.
In (2) and (4), the ``4-domino'' $[p,c,A,q]$ records that the last
move by $D$ was the unique tuple beginning $(p,c,A,\dots.)$.
The point of the normal form in Lemma \ref{niceNF} is that in (3)
and (5), the ``4-domino'' $[p,e,A,q]$ likewise comes from a unique
last move, since if $D$ has an $\epsilon$-move in state $p$
with top-of-stack symbol $A$, this move is unique (and independent of
the current input).
This seems to be needed for the LR$(0)$ property.
We also call the symbols of the form $[p,A,q]$ ``3-dominoes.''
For intuition, we consider derivations in which each step
expands the rightmost 3-domino in the sentential form, but
4-dominoes are not expanded until the very end, calling this
kind of derivation ``rightmost'' as well.
Now we observe the following {\em invariants\/}:
\begin{enumerate}
\item[(a)]
In every sentential form derivable from $S$ (not just in a
rightmost derivation), the dominoes ``match up like dominoes.''
\item[(b)]
In a rightmost derivation, the only two 3-dominoes which can
touch are the rightmost 3-domino and its neighbor.
\item[(c)]
In any sentential form (not necessarily
from a rightmost derivation), any chain of touching 4-dominoes
represents left-to-right a portion of a valid computation by $D$,
giving the sequence of states, input head motions, and
top-of-stack symbols encountered.
% \item[(d)]
% Let $\gamma \in V^*$ be a prefix
% of a sentential form in a rightmost derivation which
% ends in a 4-domino $X$. Let $v \in \Sigma^*$ be such
% that $\gamma \implies^* v$, and let $a \in \Sigma \cup \set{\$}$.
% Then $D$ on input $va$ makes a sequence of moves in which the
% last move is the tuple specified by $X$ and leaves the
% input head scanning the $a$.
\end{enumerate}
\noindent
Invariant (c) holds because the 4-dominoes correspond
directly to tuples of $D$. This is analogous to Lemma 10.6
in the text, and should likewise be formally proved by
induction on lengths of derivations in $G$, but the above
seems an acceptable ``handwave.'' The following is my attempt
to do Lemma 10.7 without quite so much formal machinery:
\bigskip
{\it Claim:\/}
Let $\gamma \in V^*$, and take some terminal string $v$ such that
$\gamma \implies^* v$. Then there exists a string $\gamma_v$ of
4-dominoes such that $\gamma \implies^* gamma' \implies^* v$, and $\gamma_v$ gives a sequence of valid moves
of $D$ on input $v$ over which it reads all of $v$.
\bigskip
The claim follows from invariants (a) and (c).
First we prove that $L(G) = L(D)$. If $D$ accepts $x$, then
consider the unique {\em leftmost\/} derivation in which at each
step, the production chosen corresponds to the next move of
$D$, and in productions of type (4) or (5), the guess
$g$ is read off from the computation path of $D$.
The end result is a derivation of $x\$$.
Now suppose $S \rderives x\$$. Consider a derivation which is rightmost
for 3-dominoes. Then one of the sentential forms $\alpha$
consists entirely of 4-dominoes. Since $\alpha \implies^* x\$$,
invariant (c) implies that $\alpha$ represents a valid
accepting computation of $D$ on input $x\$$, so $D$ accepts $x\$$.
Now we show that $D$ has the LR$(0)$ property.
We need to show that for all $\gamma \in (T \cup V)^*$
such that $I(\gamma)$ contains a complete item
$X \into \alpha\bullet$, $I(\gamma)$ does not contain
a distinct complete item $Y \into \beta\bullet$, nor
an item of the form $Z \into \bullet a$,
where $a \in \Sigma \cup \set{\$,\epsilon}$.
We attack the $Y$ item first, and without loss
of generality, may suppose $|\alpha| \leq |\beta|$.
This breaks down into three cases:
\begin{enumerate}
\item[(1)]
Neither $X \into \alpha$ nor $Y \into \beta$ is a terminal
production (type 0):
Then $\alpha$ and $\beta$ are nonempty. By validity,
each is a suffix of $\gamma$, so $\alpha$ is a suffix of $\beta$.
None of the right-hand-sides in (1)--(5)
can be a suffix of any other right-hand side except itself---in
particular, $[s,\wedge,f]$ cannot be a suffix of another production
because only the initial step produces it.
Hence $\alpha = \beta$.
All five types (1)--(5) are such that the right-hand side
includes all information about the left-hand side.
Hence the two productions cannot be distinct.
(This is a little snappier than Lemma 10.9, ``Case 1'' in the text,
owing to my putting both states into a 4-domino.)
\item[(2)]
Both productions are of type (0). If $\alpha \neq \epsilon$,
then both $\alpha$ and $\beta$ are the same terminal $c$.
Let $v$ be a terminal string such that $\gamma \rderives v$,
and take the 4-domino chain $\gamma_v$ from the Claim.
Then $\gamma_v X \implies vc$ and $\gamma_v Y \implies vc$.
By invariant (c), $\gamma_v$ specifies a sequence of valid
moves by $D$ on input $vc$ which leaves the input head scanning $c$.
Let $q$ be the state $D$ winds up in and $A$ the top-of-stack
symbol after this sequence of moves.
Then since $\gamma_v X$ and $\gamma_v Y$ both occur as
initial segments in (non-rightmost) derivations from $S$,
and are chains of 4-dominoes, they too must be specify valid
sequences of moves. But both $X$ and $Y$ must be moves
in state $q$ reading $c$ and $A$, and since $D$ is deterministic,
they must specify the same move. Thus $X = Y$,
so once again the two productions cannot be distinct.
If both $\alpha$ and $\beta$ are $\epsilon$, then $X$ and $Y$
both have ``$e$'' as their second component.
Thus with $\gamma_v$ as before, $D$ on input $v$ has first the sequence of moves specified by $\gamma_v$, which leaves the head scanning
the cell to the right of the last symbol in $v$,
and then the move specified by $X$ vis-a-vis $Y$.
But since both $X$ and $Y$ specify $\epsilon$-moves,
our normal form for $D$ assures that these moves are independent of
whatever symbol happens to be to the right of $v$, and since
$D$ is deterministic, that they are the same move.
Hence $X = Y$ in this case as well.
Last, if $\alpha =\epsilon$ and $\beta = c$, then by similar
reasoning we get a case where $D$ on input $vc$ simultaneously
has an $\epsilon$-move and a read-move when scanning the
$c$, which is also ruled out by our normal form.
\item[(3)]
Exactly one of the productions is of type (0).
By the suffix conditions and our assumption $|\alpha| \leq |\beta|$,
we must have $\alpha = \epsilon$.
Then $\gamma X$ is a prefix of a right-sentential form,
and $\gamma$ ends in $\beta$. Now $\beta$ can't be a
right-hand side from (4) or (5), because this would
violate invariant (b) for rightmost derivations.
Nor can $\beta$ be a single 4-domino, since then the variable $X$
could never have been produced in a rightmost derivation.
So this is impossible.
\end{enumerate}
Finally, we need to show that $Z \into \bullet a$ cannot co-exist
with $X \into \alpha\bullet$ in $I(\gamma)$.
By validity, there exists $w \in T^*$ such that
$S \rderives \gamma Z w$, and $\alpha$ is a suffix of $\gamma$.
As in case (3) just above, $\alpha$ cannot be a right-hand side
of a production of types (1)--(5).
Nor can $\alpha$ be a terminal, since this is a rightmost
derivation. Hence $\alpha$ must be $\epsilon$,
and by validity, there exists $w' \in T^*$ such that
$S \rderives \gamma X w'$.
Again let $v$ be such that $\gamma \rderives v$, and
let $\gamma_v$ be the chain of 4-dominoes from the claim.
Then $\gamma_v X$ and $\gamma_v Z$ are chains of
4-dominoes which occur in derivations from $S$, so invariant (c)
applies to them too. Thus $D$ on input $va$ has the sequence of
moves specified by $\gamma_v$, which leaves the head scanning
$a$ (or the cell to the right of $v$ if $a = \epsilon$), followed by
the valid move specified by $X$ or $Z$. But $X$ specifies an
$\epsilon$-move, since $\alpha = \epsilon$, and by our
normal form, $Z$ must specify the same $\epsilon$-move.
Thus $Z = X$. This completes the entire proof.
\qed
Now define the grammar $G_1$ from $G$ by changing the
productions $[p,\$,\wedge,f] \into \$$ in (0) to
$[p,\$,\wedge,f] \into \epsilon$. Clearly if
$L(G) = L\$$, then $L(G_1) = L$.
What goes wrong in the above proof if we try to show that
$L(G_1)$ is LR$(0)$? The problem is that $I(\gamma)$ can now
have a new kind of complete item $X \into \alpha\bullet$ with
$\alpha = \epsilon$, namely $[p,\$,\wedge,f] \into \epsilon\bullet$.
This can conflict with an item of the form $Z \into \bullet c$
where $Z$ is the 4-domino $[p,c,\wedge,q]$.
With reference to the last paragraph, let
$\gamma \implies^* v$, and take $\gamma_v$ as before.
Then $\gamma_v X$ is a chain of 4-dominoes and $\gamma X \implies v$
also, but
Invariant (c) no longer holds for it because $[p,\$,\wedge,f]$
no longer comes from a valid move (before, it came from
the tuple $(p,\$,\wedge,\epsilon,R,f)$ which read the $\$$).
There is now no contradiction with $Z$ specifying a valid
move of $D$ in state $p$ with stack $\wedge$ reading some input
symbol $c$ which comes after $v$. Below is a concrete
example for a DPDA $D$ which accepts a language $L$ that doesn't
have the prefix property.
However, this conflict goes away if we have ``$\!\!\!\on{y}$'' lookahead
in the sole case $y = \epsilon$
(where we have been writing this as$\on{\$}$).
Since $[p,\$,\wedge,f]$ can only appear as the rightmost
symbol in a derivation, the {\em only\/} valid LR$(1)$ item
corresponding to the production is $[p,\$,\wedge,f] \into \bullet \on{\$}$;
that is, no item $[p,\$,\wedge,f] \into \bullet \on{c}$ is ever
valid for $c \in \Sigma$. Hence, by the definition of
an LR{\em (1)\/} grammar, there is no conflict with
$[p,c,\wedge,q] \into \bullet c \on{\dots}$.
\begin{theorem}
$G_1$ is LR(1). Thus every DCFL has an LR(1) grammar.
\end{theorem}
\proof
The above remarks, plus the idea that for $k \geq 0$, every
LR$(k)$ grammar is also an LR$(k+1)$ grammar, are enough
to constitute a proof.\footnote{Hecque, it's more than the text has!}
\qed
\noindent
Hence a language $L$ is a DCFL only if, as well as if, there is
some $k$ such that $L$ has an LR$(k)$ grammar.
\begin{corollary}
The above statement remains true if ``LR($k$) grammar'' is defined
by the more-restrictive condition that whenever
$I^k(\gamma)$ contains a complete item, it contains
no other critical item, where an item
$A \into \alpha \bullet \beta \on{\dots}$ is defined to be
``critical'' if $\beta \notin V^*$.
\end{corollary}
The following example will help shed light on these observations.
\begin{example}
Let $D$ be the DPDA with $Q = \set{0,1,2,3}$,
$\Sigma = \set{\rma,\rmb}$, $\Gamma = \set{A,\wedge}$,
start state 0, unique final state 3, and tuples
\[
\set{
(0,\rma,\wedge,A\wedge,\rmR,1),
(1,\rma,A,AA,\rmR,1),
(1,\rmb,A,\epsilon,\rmR,2)} \cup
\]
\[
\set{
(2,\rma,\wedge,A\wedge,\rmR,1),
(2,\rmb,A,\epsilon,\rmR,2),
(2,\$,\wedge,\epsilon,\rmR,3)
}.
\]
Then $L(D) = \set{\rma^m \rmb^m : m \geq 1}^{+}\$$.
In fact, $D$ is the ``most obvious'' DPDA for this language, and
since it makes no $\epsilon$-moves (i.e., runs in real time),
it is automatically in the normal form of Lemma \ref{niceNF}.
The corresponding grammar $G_1$ has productions:
\begin{enumerate}
\item[(0)]
$[p,\rma,A,q] \into \rma$, \quad $[p,\rma,\wedge,q] \into \rma$,
\quad $[p,\rmb,A,q] \into \rmb$, \quad $[p,\rmb,\wedge,q] \into \rmb$,
\quad and $[p,\$,\wedge,3] \into \epsilon$, for all $p,q \in Q$.
\item[(1)]
$S \into [0,\wedge,3]$.
\item[(2-3)]
$[1,A,2] \into [1,\rmb,A,2]$, \quad $[2,A,2] \into [2,\rmb,A,2]$,
\quad and $[2,\wedge,3] \into [2,\$,\wedge,3]$.
\item[(4-5)]
\begin{eqnarray*}
[0,\wedge,r] &{\into} &[0,\rma,\wedge,1][1,A,g][g,\wedge,r],\\
{[1,A,r]} &{\into} &[1,\rma,A,1][1,A,g][g,A,r],\\
{[2,\wedge,r]} &\into &[2,\rma,\wedge,1][1,A,g][g,\wedge,r],
\end{eqnarray*}
for all $r,g \in Q$.
\end{enumerate}
Now consider the following two rightmost derivations, the
first of the string $\rma\rmb$, the second of the string
$\rma\rmb\rma\rmb$: $S \rderive [0,\wedge,3]$
\begin{eqnarray*}
&\rderive &[0,\rma,\wedge,1][1,A,2][2,\wedge,3]\\
&\rderive &[0,\rma,\wedge,1][1,A,2][2,\$,\wedge,3]\\
&\rderive &[0,\rma,\wedge,1][1,A,2]\\
&\rderive &[0,\rma,\wedge,1][1,\rmb,A,2] \rderive^2 \rma\rmb,
\end{eqnarray*}
and $S \rderive [0,\wedge,3]$
\begin{eqnarray*}
&\rderive &[0,\rma,\wedge,1][1,A,2][2,\wedge,3]\\
&\rderive &[0,\rma,\wedge,1][1,A,2][2,\rma,\wedge,1][1,A,2][2,\wedge,3]\\
&\rderive &[0,\rma,\wedge,1][1,A,2][2,\rma,\wedge,1][1,A,2][2,\$,\wedge,3]\\
&\rderive &[0,\rma,\wedge,1][1,A,2][2,\rma,\wedge,1][1,A,2]\\
&\rderive &[0,\rma,\wedge,1][1,A,2][2,\rma,\wedge,1][1,\rmb,A,2]\\
&\rderive &[0,\rma,\wedge,1][1,A,2][2,\rma,\wedge,1]\;\rmb\\
&\rderive &[0,\rma,\wedge,1][1,A,2]\;\rma\;\rmb \rderive^3 \rma\rmb\rma\rmb.
\end{eqnarray*}
Now fix attention on the viable prefix
$\gamma = [0,\rma,\wedge,1][1,A,2]$.
The second displayed line of the first derivation shows that the item
$[2,\$,\wedge,3] \into \bullet$ is valid for $\gamma$.
But the line
\begin{eqnarray*}
&\rderive &[0,\rma,\wedge,1][1,A,2][2,\rma,\wedge,1]\;\rmb
\end{eqnarray*}
shows that the item $[2,\rma,\wedge,1] \into \bullet \rma$
is also valid for $\gamma$. Hence $G_1$ is not an LR(0) grammar,
though changing the last production in (0) to
$[2,\$,\wedge,3] \into \$$ makes it so.
But using the LR(1) item $[2,\$,\wedge,3] \into \bullet \on{\$}$
solves the problem without introducing $\$$ into the language.
\end{example}
\subsection{Some final remarks about LR($k$) grammars}
As remarked before, our choice of formalizing items
as having single lookahead strings does not lead to the
most efficient parsers if programmed literally.
For one thing, it is natural to save space by grouping
all lookahead strings $z$ such that
$A \into \alpha \bullet \beta \on{z}$ are valid for the same $\gamma$
into a single entry. There are other efficiency tricks,
including so-called LALR parsing, which are described
in some other texts, including Aho and Ullman's ``Dragon Book''
on compilers. My main interest in this line has been to
come back to the question:
\begin{quote}
What is a deterministic context-free grammar?
\end{quote}
The simple example $S \into \rma S \rma | \rmb S \rmb | \epsilon$,
which generates the non-DCFL $\set{xx^R : x \in \set{\rma,\rmb}^*}$
and is easy to parse, says intuitively that the answer
``an LR($k$) grammar'' is too restrictive. This last grammar is
unambiguous, and this suggests the answer
``an unambiguous grammar.'' Note that
$\set{\rma^i \rmb^j \rma^k \rmb^l : i=l \OR j=k}$ is an example
of a CFL which does not have an unambiguous grammar, so this
answer would still be a nontrivial restriction on the
notion of a context-free {\em language\/}. But there are
unambiguous CFGs which are considered difficult to parse
because their parse trees grow exponentially in the size
of terminal strings.
What I've had in mind is to develop a notion of CFGs that can
be parsed by a {\em two-way\/} DPDA. A 2DPDA on input $x$
has an input tape which holds $\wedge x \$$, and is allowed
to make left moves of its input head. 2DPDAs can accept
non-CFLs; for instance, a 2DPDA can accept
$\set{0^n 1^n 2^n}$ by first comparing 0s against 1s, making
left moves until reading a 0, and then comparing 1s against 2s.
The special reason for interest in 2DPDAs is that even though
an individual 2DPDA $D$ can run for exponential time,
there is an efficient general method due to Cook
for simulating $D$ by a RAM algorithm which
runs in {\em linear\/} time. Oddly enough, Cook's procedure
is not known to run in linear time when ported to a Turing machine.
If time allows, I'll demonstrate Cook's procedure in two class hours.
Two-way DPDAs begin to hit the level of power where,
as with $\P$ and $\NP$, we know hardly anything.
I am interested in whether one can formalize conditions
on CFGs $G$ which allow parsing by 2DPDAs.
One might call such a parser a ``shift-reduce-review'' parser.
Any of you who sees a good way to start doing this is welcome
to pursue it as a research topic with me.
%\lecture{**LECTURE-NUMBER**}{**DATE**}{**LECTURER**}{**SCRIBE**}
% \lecture{18--21}{Oct. 18,20,22,25}{K.W. Regan}{D. Sivakumar}
% **** YOUR NOTES GO HERE:
\section{Rational Relations}
[Lectures 18--21, scribed by D. Sivakumar.]
\bigskip
Let $\rho \subseteq \Sigma^* \times \Gamma^*$ be a binary relation on strings.
Define
the language $L_\rho \subseteq \Sigma^* \times \Gamma^*$ to be
$\set{\langle x,y \rangle ~|~ \rho(x,y) {\rm~holds}}$,
where
$\langle \cdot,\cdot \rangle$ denotes the standard pairing function given by
$\langle x,y \rangle = \doublebits(x) \cdot 10 \cdot \doublebits(y)$.
\noindent
({\it Note\/}: For the special case when $\Sigma = \Gamma = \set{0,1}$, if
we need $\langle \cdot,\cdot \rangle$ to be one-to-one {\em and} onto, then
we can use the pairing function described in {\cite{Reg88}}. This pairing
function, due to KWR, is computable by a deterministic finite-state
transducer (hence in linear time) and is one-to-one and onto.)
\begin{definition}
Let $A \subseteq \Sigma^*, B \subseteq \Gamma^*$ be any two languages.
We say that $A$ {\it $\rho$-redues} to $B$, denoted $A \rhoredu B$, if
for all $x \in \Sigma^*$,
\[
x \in A \iff (\exists y \in B)~(\rho(x,y)).
\]
\end{definition}
\noindent
Given a language $B$ and a relation $\rho$, there is a unique $A$ such that
$A \rhoredu B$, namely,
$A = \inverserel{\rho}(B) := \set{x~|~(\exists y \in B)~\rho(x,y)}$.
If $\rho$ is the graph of a total function $f : \Sigma^* \into \Gamma^*$,
then $A \rhoredu B \equiv (\forall x) x \in A \iff f(x) \in B$.
\begin{definition}
A relation $\rho$ is said to be $g(n)${\it -length bounded\/} if
\[
(\forall x, y) \rho(x,y) \implies |y| \leq g(|x|).
\]
\end{definition}
\noindent
{\bf Examples.}
\begin{enumerate}
\item
$\rho(x,y) \equiv$ ``$x$ is a prefix of $y$''. Then for any $B$,
$\inverserel{\rho}(B) \equiv \Prefs(B)$.
\item
For every partial multivalued function $f$, define the relation
$\rho_f(x,y) \iff f(x) \mapsto y$, that is, $y \in \setf(x)$, or, ``$y$ is
a value of $f(x)$''. Conversely, given $\rho$, we can define the partial
multivalued function $f_\rho(x) \mapsto y \iff \rho(x,y)$.
With these in hand, we can define the complexity classes
$\NPMV$ and $\NPMV_g$ as follows:
\begin{eqnarray}
\NPMV & = & \set{f_\rho : \rho {\rm~is~polynomial~length~bounded~and~}
L_\rho \in \NP}, \nonumber \\
{\rm ~and~} \NPMV_g & =
& \set{f_\rho : \rho {\rm~is~polynomial~length~bounded~and~}
L_\rho \in \P}. \nonumber
\end{eqnarray}
\end{enumerate}
\bigskip
\noindent
We will now give the formal definition of rational relations on
$\Sigma_1^* \times \Sigma_2^* \times \ldots \times \Sigma_k^*$.
\begin{definition}
A tuple $(a_1, a_2, \ldots, a_k) \in
\Sigma_1^* \times \Sigma_2^* \times \ldots \times \Sigma_k^*$
is called a {\it singleton\/}
if for all $i, 1 \leq i \leq k:~a_i \in \Sigma_i \cup \set{\epsilon}$.
\end{definition}
\begin{definition}
The {\it rational expressions\/} that describe rational relations on
$\Sigma_1^* \times \Sigma_2^* \times \ldots \times \Sigma_k^*$
are inductively defined as follows:
\bigskip
\noindent
{\it Basis.\/}
\begin{itemize}
\item [(0)]
${\mbox \O}$ is a rational expression that denotes the empty relation
$\emptyset$.
\item [(1)]
Any singleton is a rational expression that denotes the relation with
one tuple.
\end{itemize}
\bigskip
\noindent
{\it Induction.\/}
\begin{itemize}
\item [(2)]
If $\rho$ and $\sigma$ are rational expressions, then
$\rho \cup \sigma := \set{\vec{x} ~|~ \vec{x} \in \rho \OR \vec{x} \in \sigma}$
is a rational expression that denotes the union of the two relations.
\item [(3)]
If $\rho$ and $\sigma$ are rational expressions, then
$\rho \cdot \sigma := \set{\vec{x} ~|~ (\exists \vec{y} \in \rho) (\exists
\vec{z} \in \sigma)~\vec{x} = \vec{y}\cdot\vec{z}}$
is a rational expression that denotes the concatenation of the two relations.
\item [(4)]
If $\rho$ and $\sigma$ are rational expressions, then
$\rho^* := \set{\vec{\epsilon}} \cup \set{\vec{x} ~|~ (\exists n \geq 1)~
\vec{x} \in \rho_n}$,
where $\vec{\epsilon}$ is the all-$\epsilon$ $k$-tuple,
is a rational expression that denotes the Kleene closure of the relation $\rho$.
\end{itemize}
\end{definition}
\noindent
Observe that ${\mbox \O}$ is the identity for the union operation
and $\epsilon$ is
the identity for the concatenation operation.
\bigskip
\noindent
{\bf Example.}
The rational expression $\rho := ((a,a) \cup (b,b))^* \cdot ((\epsilon,a) \cup
(\epsilon,b))^*$ denotes the relation $\set{\langle x,y \rangle ~|~
x \sqsubseteq y}$. Therefore, for any set $B \in \set{a,b}^*$, there exists a
unique set $A \in \set{a,b}^*$ such that $A \rhoredu B$, and this is
just the set $A = \Prefs(B)$.
\begin{definition}
A rational relation $\rho$ is said to be {\it free\/} if there are regular
expressions $\alpha, \beta$ such that $(\forall x,y)~(x,y) \in \rho \iff
x \in L(\alpha) \AND y \in L(\beta)$.
\end{definition}
\begin{proposition}\label{freeregular}
If $\rho$ is a free rational expression, then $L_\rho \eqdef \set{x\#y ~|~
(x,y) \in \rho}$ is regular.
\end{proposition}
\noindent
The converse of Proposition (\ref{freeregular}) is not true, however.
For example, the
rational relation $\rho := \set{(a,a),(b,b)}$ is not free, but $L_\rho$ is
finite and, therefore, regular. Another example is the rational relation
for substrings, namely,
$\pi := ((\epsilon,a)\cup(\epsilon,b))^* ((a,a)\cup(b,b))^*
((\epsilon,a)\cup(\epsilon,b))^*$.
The language $L_\pi = L_{\mbox \it pat} = \set{\langle x,y \rangle ~|~ x
{\rm~is~a~substring~of~} y}$ cannot even be accepted by a $k$-head
DFA for any fixed $k$.
\bigskip
\noindent
{\bf Rational Relations and GSM$_\epsilon$ Mappings}
\begin{definition}
A {\it transition graph with output (TGO)\/} is the directed graph
of a finite automaton
$M = (Q, \Sigma, \Gamma, \delta, s, F)$ where $Q$ is a set of states
that label the vertices of the graph, $s \in Q$ is a designated start
state, $F \subseteq Q$ is a set of accepting states, $\Sigma$ and $\Gamma$
are some alphabets, $\delta \subseteq Q \times \ratrel(\Sigma \times
\Gamma) \times Q$, and where each arc is labelled by a rational relation
$\rho \in \ratrel(\Sigma \times \Gamma)$.
\end{definition}
\begin{definition}
The {\it relation computed by $M$\/} is defined by
\begin{eqnarray}
\rho_M & \eqdef & \set{(x,y)~|~
(\exists q_0, \ldots, q_m \in Q, q_0 = s, q_m \in F) \nonumber \\
& &~~(\exists x_1, \ldots, x_m \in \Sigma^*) (\exists y_1, \ldots, y_m \in \Gamma^*)
~x = x_1 \cdot x_2 \ldots x_m, y = y_1 \cdot y_2 \ldots y_m {\rm~and~}
\nonumber \\
& &~~(\forall i : 1 \leq i \leq m) (x_i, y_i) \in \rho_i {\rm~where~}
(q_{i-1}, \rho_i, q_i) \in \delta}.\nonumber
\end{eqnarray}
\end{definition}
\bigskip
\noindent
Consider the following TGO:
\vspace{2.0in}
\noindent
This is a rational relation that is {\em not\/} a generalized
homomorphism. To see this, consider a string of the
form $\ldots 0001{\bf 10}10 \ldots$;
we cannot infer what the TGO produces on the boldfaced substring ``10'',
without the knowledge about which of ``00'' or ``11'' precedes it.
\bigskip
We will now show a normal form of a TGO, and then proceed to show
the equivalence of TGO's and rational relations. The idea behind the
use of the normal form is that we can convert any TGO into one that is
in the normal form and, consequently, it suffices to exhibit the rational
relation for TGO's in the normal form.
The normal form for TGO's is given by the following:
\vspace{2.5in}
\begin{lemma}\label{ratrelnf}
The rational relation corresponding to a TGO $M$ in its normal form
shown above is given by $\rho_M = (\alpha \cup \beta \gamma^* \eta)^*
\cdot \beta \gamma^*$.
\end{lemma}
\proof
By inspection. \qed
\begin{lemma}\label{specialtgo}
For any TGO $M$, we can find an equivalent TGO $M'$
such that $s' = 1$ and $F' = \set{f}$ where $f$ is numbered $2$.
The TGO $M'$ is called {\it special\/}.
\end{lemma}
\proof
Given $M$, add a new final state $f$, number $f~2$ and add arcs
$(f', (\epsilon, \epsilon), f)$ for all original final states $f'$
of $M$. \qed
\begin{theorem}\label{tgotoratrel}
For any TGO $M$, $\rho_M$ is a rational relation.
\end{theorem}
\proof
By Lemma \ref{specialtgo}, we may assume wlog.
that the TGO $M$ is special.
Define the numerical predicate $P(n,m) \equiv$
``for all special $M$ such that $|Q| = n$ and such that there do not
exist an $m'$ and a relation $\rho$ which satisfy
$m < m' < n \AND (m', \rho, n) \in \delta$,
$\rho_M$ is rational''.
We prove the theorem by induction on $n$ and $m$.
The basic idea is that if $m$ is the highest numbered node other than $n$ which
has an in-arc to node $n$, we can eliminate the arc from $m$ to $n$ and
apply the induction hypothesis.
{\it Basis $(n = 2, m = 1)$.\/} Follows from Lemma \ref{ratrelnf}.
{\it Induction $(n \geq 2$).\/} Assume, as induction hypothesis (IH), that
for all $n' < n$ and $m' < n'$, $P(n',m')$ holds, and that
for all $m' < m$, $P(n,m')$ holds. We need to show that $P(n,m)$ is true.
Given a special TGO $M$ with $|Q| = n$, let $m$ be the highest numbered
node with an in-arc to $n$. Note that $n \neq f$ and $n \neq s$,
because $f$ is numbered $2$, $s$ is numbered $1$ and $n \geq 3$.
For every out-neighbor $q$ of $n$ ($q = m$ included), consider the diagram:
\vspace{2.5in}
Any computation that uses the arc $(m, \beta, n)$ comes in from $m$ and
exits $n$ via some other arc. Simultaneously for every $q$ which is an
out-neighbor of $n$, do the following:
\begin{itemize}
\item
Replace $\alpha$ by $\alpha \cup \beta \gamma^* \eta$.
\item
Delete the arc $(m, \beta, n)$.
\item
If $(m, \beta, n)$ was the last arc into node $n$,
delete node $n$. Now, $|Q| = n-1$,
and by IH $P(n-1, {\mbox \it any})$ is true; therefore, $P(n,m)$ follows.
If $(m, \beta, n)$ was not the last arc into node $n$, repeat the
procedure for the next highest-numbered arc.
Again, by IH, $P(n,m-1)$ is true; therefore $P(n,m)$ follows.
\qed
\end{itemize}
\begin{definition}
A {\it GSM$_\epsilon$\/} is the special case of TGO in which every label
$\rho$ on an arc is a singleton or a finite union of singletons.
\end{definition}
\begin{theorem}\label{ratreltotgo}
For every rational relation $\rho$, there is a GSM$_\epsilon$ $M$ such that
$\rho = \rho_M$.
\end{theorem}
\proof
(By induction on the structure of rational relations.)
{\it Basis.\/}
\begin{itemize}
\item
$\rho = {\mbox \O}, M = {\mbox \O}$.
\item
$\rho$ is a singleton. $M$ is one of the following four TGO's.
\vspace{3.0in}
\end{itemize}
{\it Induction.\/}
\begin{itemize}
\item
$\rho \cup \sigma$:
\vspace{3.0in}
\item
$\rho \cdot \sigma$:
\vspace{2.0in}
\item
$(\rho)^*$:
\vspace{2.5in}
\end{itemize}
\qed
\begin{theorem}\label{inverseredn}
Let $\rho$ be a rational relation on $\Sigma^* \times \Gamma^*$.
Then we can find an alphabet $\Delta$, a regular set $R \subseteq \Delta^*$
and homomorphisms $h:\Delta \into \Gamma^*, t:\Delta \into \Sigma^*$
such that for all sets $B \subseteq \Gamma^*, \inverserel{\rho}(B) =
t(h^{-1}(B) \cap R)$.
\end{theorem}
\proof
By Theorem \ref{ratreltotgo}, there is a special GSM$_\epsilon$ $M$ such that
$\rho = \rho_M$. Let $M = (Q, \Sigma, \Gamma, \delta, s, \set{f})$ where
$\delta \subseteq Q \times (\Sigma \cup \set{\epsilon}) \times
(\Gamma \cup \set{\epsilon}) \times Q$.
Let $\Delta = \set{[p,a,b,q] \in \delta}$ be the alphabet of ``dominoes''.
Let $h:\Delta \into \Gamma^*$ be the erasing homomorphism defined as
$h([p,a,b,q]) = b$, and let $t:\Delta \into \Sigma^*$ be the erasing
homomorphism defined as $t([p,a,b,q]) = a$.
\begin{tabbing}
----\=---------\=----\=------------\=--------\kill
\> Let $R$ \> $:=$ \> $\{\vec{c} \in \Delta^* |$ \> $\vec{c}$
is a sequence of dominoes in $\delta$ which ``match''
like dominoes, such that \nonumber \\
\> \> \> \> the first domino begins with $s$,
and the last domino ends with $f$\}. \nonumber
\end{tabbing}
\begin{lemma}
$R$ is regular.
\end{lemma}
\proof By inspection. \qed
\noindent
We need to show that for all $x$, $x \in \inverserel{\rho} \iff
x \in t(h^{-1}(B) \cap R)$.
\noindent
For all $x$:
\begin{eqnarray}
x & \in & t(h^{-1}(B) \cap R) \nonumber \\
& \iff & (\exists y \in \Delta^*)
(t(y) = x \AND y \in R \AND y \in h^{-1}(B)) \nonumber \\
& \iff & (\exists y \in \Delta^*)(\exists z \in B)
(t(y) = x \AND y \in R \AND h(y) = z) \nonumber \\
& \iff & (\exists y \in \Delta^*)(\exists z \in B)
(t(y) = x \AND h(y) = z \AND y \nonumber \\
& & {\rm ~~~~~~~is~a~valid~computation~sequence~of~} M(x)
{\rm ~which~gives~output~} z) \nonumber \\
& \iff & (\exists z \in B) (x,z) \in \rho_M \nonumber \\
& \equiv & x \in \inverserel{\rho}(B). \nonumber
\end{eqnarray}
\noindent
This completes the proof. \qed
\begin{definition}
For any $A \subseteq \Sigma^*$ and relation $\rho$ on
$\Sigma^* \times \Gamma^*$, define the {\it forward reduction by
$\rho$\/} to be $\rho(A) \eqdef \set{y~|~(\exists x \in A)
(x,y) \in \rho}$.
\end{definition}
\begin{theorem}
For every rational relation $\rho$ on $\Sigma^* \times \Gamma^*$,
there exists an alphabet $\Delta$
and regular set $R \subseteq \Delta^*$ and homomorphisms
$h:\Delta \into \Gamma^*, t:\Delta \into \Sigma^*$ such that
for all sets $A \subseteq \Sigma^*, \rho(A) = h(t^{-1}(A) \cap R)$.
\end{theorem}
\proof
Same $R$, same $t$, same $h$, same proof as Theorem \ref{inverseredn}!
\noindent
We need to show that for all $z$, $z \in \rho(A) \iff
z \in h(t^{-1}(A) \cap R)$.
\noindent
For all $z$:
\begin{eqnarray}
z & \in & h(t^{-1}(A) \cap R) \nonumber \\
& \iff & (\exists y \in \Delta^*)
(h(y) = z \AND y \in R \AND y \in t^{-1}(A)) \nonumber \\
& \iff & (\exists y \in \Delta^*)(\exists x \in A)
(h(y) = z \AND y \in R \AND t(y) = x) \nonumber \\
& \iff & (\exists y \in \Delta^*)(\exists x \in A)
(h(y) = z \AND t(y) = x \AND y \nonumber \\
& & {\rm ~~~~~~~is~a~valid~computation~sequence~of~} M(x)
{\rm ~which~gives~output~} z) \nonumber \\
& \iff & (\exists x \in A) (x,z) \in \rho_M \nonumber \\
& \equiv & z \in \rho(A). \nonumber
\end{eqnarray}
\noindent
This completes the proof. \qed
\bigskip
\noindent
{\it Observations.\/}
\begin{enumerate}
\item [(1)]
If $M$ makes no output on $\epsilon$ moves, then $t$ is 1:1.
\item [(2)]
If $M$ never erases an input symbol, then $h$ is 1:1.
\item [(3)]
If $M$ is a nondeterministic Mealy machine, both $h$ and $t$ are 1:1.
\item [(4)]
If we want $\Delta = \Sigma = \Gamma = \set{0,1}$,
then $t$ and $h$ can be $r:1$ generalized homomorphisms,
where $r = 4 \lceil \log_2|Q| \rceil + 18$ is the number of symbols
needed to encode $[0^k, 00, 00, 0^k]$ using the tupling function.
\end{enumerate}
% \lecture{**LECTURE-NUMBER**}{**DATE**}{**LECTURER**}{**SCRIBE**}
% \lecture{22-23}{October 27th and 29th}{K.W. Regan}
% {Debra Burhans and Kannan Govindarajan}
\section{The Chomsky-Sch\"{u}tzenberger Representation Theorem}
[Lectures 22--23, scribed by Burhans and Govindarajan.]
\begin{definition}
Let $\Gamma_n$ be the alphabet \{ $[_1, [_2, \ldots, [_n, ]_1,]_2,\ldots, ]_n $\}.
The Dyck set of order n, is the language of the grammar:\\
\begin{center}
$G_n : S \rightarrow SS ~ | ~ \epsilon ~ | ~ [_1 ~ S ~ ]_1 ~ | ~ [_2 ~ S ~ ]_2 ~ | ~ \ldots ~ | ~ [_n ~ S ~ ]_n$
\end{center}
\end{definition}
Note that the grammar $G_n$ is ambiguous but the language L($G_n$) = $D_n$ is
a \DCFL.
\paragraph{Question:}
Which of the following grammars are LR(1)?
\begin{enumerate}
\item $S \rightarrow \epsilon ~ | ~ [_i S ]_i S$
\item $S \rightarrow \epsilon ~ | ~ S [_i S ]_i $
\end{enumerate}
\begin{theorem}
For every CFL L, over some alphabet $\Sigma$, we can find an n $>$ 0, an alphabet
$\Delta$, a regular set R $\subseteq ~ \Delta^*$ and homomorphisms
\begin{enumerate}
\item h : $\Delta ~ \rightarrow ~ \Gamma_n^*$.
\item t : $\Delta ~ \rightarrow ~ \Sigma^*$
\end{enumerate}
such that L = $t(h^{-1}(D_n) \cap R)$.
\end{theorem}
\begin{proof}
Suppose for the moment that $\epsilon \not\in L$. Let G be a CFG in Chomsky
Normal Form for L. Take n to be the number of type $V \rightarrow VV$ productions
in G. Let $\Delta := \Sigma \cup \Gamma_n$, and homomorphisms h and t are defined as follows:\\
\[ h(x) = \left\{ \begin{array}{ll}
\epsilon & \mbox{if$ x \in \Sigma$}\\
x & \mbox{otherwise}
\end{array}
\right. \]
\[ t(x) = \left\{ \begin{array}{ll}
\epsilon & \mbox{if $x \in \Gamma_n$}\\
x & \mbox{otherwise}
\end{array}
\right. \]
Number the type $V \rightarrow VV$ productions in G by i := 1,$\ldots$, n. Let
$G_R$ be the CFG defined by:\\
\begin{itemize}
\item For each production $A \rightarrow BC$ in G, with number i, and each
terminal production \mbox{$D \rightarrow a$}, $a \in \Sigma$ let $G_R$ have
\begin{center}
$ A \rightarrow [_i B ~~ | ~ ~ D \rightarrow a ~ ~ | ~ ~D \rightarrow a]_iC$
\end{center}
\end{itemize}
$G_R$ is a right-linear grammar, so
\begin{center}
R := L$(G_R)$ is regular.
\end{center}
\paragraph{Note:} $\epsilon \in D_n$, therefore, if $\epsilon \in L$,
we first write the grammar G for L $\setminus$ \{$\epsilon$\} and at the end define
$R'$ = R $ \cup ~ \{ \epsilon \}$.\\
\noindent We need to prove: L(G) = $ t(h^{-1}(D_n) \cap L(G_R))$
\paragraph{{\rm L(G)} $ \subseteq t(h^{-1}(D_n) \cap L(G_R))$ part:}
Let the induction hypothesis P(m) be the following:\\
P(m) $\equiv$ For any derivation A $\Rightarrow^*$ x in G of m or fewer steps,
there is a derivation in $G_R$ of a string y such that t(y) = x, y $\in ~ h^{-1}(D_n)$ and y ends in a symbol a $\in ~ \Sigma$. Clearly
\begin{center}
$\forall m P(m) \implies L(G) \subseteq t(h^{-1}(D_n) \cap L(G_R))$
\end{center}
\paragraph{Basis (m=1):}
If A $\Rightarrow_G$ a, then since $\epsilon \in D_n$, a $\in h^{-1}(D_n)$
and $G_R^A$ has A $\rightarrow$ a, therefore, a $\in L(G_R^A)$.
(Note: $G_R^A$ is $G_R$ with A as the start symbol)
\paragraph{Induction (m $\ge$ 2):}
Let A $\Rightarrow_G$ BC ${\Rightarrow_G}^*$ x.\\
Let v, w be such that B $\Rightarrow_G^*$ v, C $\Rightarrow_G^*$ w, and vw = x.\\
By IH applied to B, $\exists$ a string $y_v$ such that B ${\Rightarrow_G}^* y_v$,
and t($y_v$) = v, and $y_v$ ends in a terminal symbol a.
Then in $G_R$, there is the leftmost derivation A $\Rightarrow ~ [_i B ~ \Rightarrow^* ~ [_i u D \Rightarrow [_i u a = y_v$.\\
Now do the derivation A $\Rightarrow^* ~ [_i u D ~ \Rightarrow [_i u a ]_i C$.
By IH applied to C, $\exists$ a string $y_w$ such that C $\Rightarrow_{G_R}^* y_w$
and t($y_w$) = w, then y = $y_v$.$y_w$ is the desired string in L($G_R$).
Since $y_v$ and $y_w ~ \in h^{-1}(D_n)$, so is y.
\paragraph{{\rm L(G)} $ \supseteq t(h^{-1}(D_n) \cap L(G_R))$ part} :
Let the induction hypothesis P(m) be the following:\\
P(m) $\equiv$ For every derivation A $\Rightarrow^*$ y in $G_R$ such that h(y)
$\in D_n$ in m or fewer steps, t(y) $\in$ L(G). Clearly
\begin{center}
$\forall m P(m) \implies L(G) \supseteq t(h^{-1}(D_n) \cap L(G_R))$
\end{center}
\paragraph{Basis (m=1) :}
y $\in \Sigma$, so this is true because G and $G_R$ have the same terminal
productions.
\paragraph{Induction (m $\ge$ 2) :}
Let A $\Rightarrow_{G_R}^m$ y, then this derivation starts with some non-terminal
production of the form A $\Rightarrow_{G_R} ~ [_i$B and y begins with $[_i$.
Note that it can't begin with A $\rightarrow$ a$]_i$C, because h(y) $\in D_n$
and can't begin with $]_i$. Since h(y) $ \in D_n$, there is a matching $]_i$ in
y. That is, we can write y = $[_i v ]_i w$ such that h(v) $\in D_n$ and h(w) $\in D_n$.
The production which produced the $]_i$ in the derivation of y must have had the
form D $\rightarrow$ a$]_i$C, where G has the production A $\rightarrow$ BC,
and D $\rightarrow$ a is in both grammars. Therefore
\begin{center}
$B \Rightarrow_{G_R}^{m'} v,~ ~ m' < m$ and $C \Rightarrow_{G_R}^{m''} w, ~ ~ m'' < m$
\end{center}
By IH, B $\Rightarrow_G^*$ t(v) and C $\Rightarrow_G^*$ t(w). Since t is a homomorphism
which erases symbols in $\Gamma_n$, in particular $[_i$ and $]_i$, t(y) = t(v).t(w).
Thus we have A $\Rightarrow_G$ BC $\Rightarrow_G^*$ t(v).C $\Rightarrow_G^*$ t(v).t(w) = t(y).
\end{proof}
\subsection{Restating and Refining Chomsky-Sch\"{u}tzenberger}
\begin{theorem}
For all CFLs L over $\Sigma$ we can find n, $\Delta = \Gamma_n \cup \Sigma$,
a regular set R $\subseteq \Delta^*$ and homomorphisms t : $\Delta \rightarrow \Sigma^*$, h : $\Delta \rightarrow \Gamma_n$,
such that L = t($h^{-1}(D_n) \cap R$).
\end{theorem}
\paragraph{Fact:} With a different R, h and $\Delta$, one can make t a 1:1
homomorphism. [Ronald V. Book, 1975, unpublished?]
\paragraph{Refinement 1: } Suppose $\Sigma$ = \set{$c_1,\ldots,c_m$}, then define
$\Gamma$' = $\Gamma_n \cup \set{[_{n+1},\ldots,[_{n+m},]_{n+1},\ldots,]_{n+m}}$.
Modify $G_R$ by replacing each terminal $c_j \in \Sigma$, by $[_{n+j} ]_{n+j}$
to get $G_{R'}$ where $R'$ = L ( ``new'' $G_R$). Let $t'$ erase $\Gamma_n$ and
map $[_{n+j} \rightarrow \epsilon$, $]_{n+j} \rightarrow c_j$. Therefore
\begin{center}
L(G) = $t'(D_{n+m} \cap R')$.
\end{center}
\paragraph{Refinement 2: }
Take $\Delta = \set{(,),[,]}.$\\
Recode $[_i ~ ~ \equiv ~ ~ (^{i-1}[(^{n+m-i}$.\\
Recode $]_i ~ ~ \equiv ~ ~ )^{n+m-i}])^{i-1}$.
\noindent Adjust $t'$ to $t''$ accordingly. $t''$ will erase any block with a [, and it will erase
)$\ldots$)])$\ldots$) if ] doesn't come in the first m places. If ] comes in the
$j^{th}$ place, with j $<$ m, then $t''$ maps block to $c_j$. So
\begin{center}
L(G) = $t''(D_2 \cap R'')$.
\end{center}
\paragraph{Research questions:}
\begin{enumerate}
\item Prove that if the size of the alphabet $\Sigma$ is large enough, then there
does not exist a homomorphism $t'''$ so that for all context free grammars
G, L(G) = $t'''(D_2 \cap R''')$.
\item Does this hold when $\Sigma = \set{0,1}$?
\end{enumerate}
\paragraph{Refinement 3: }
With a larger $\Delta$ again, we can find homomorphisms h : $\Delta \rightarrow
\set{(,),[,]}^*$, t : $\Delta \rightarrow \Sigma^*$ and L(G) = t($h^{-1}(D_2 \cap R)$), (R $\subseteq \Delta^*$) $\in {\cal REG}$.\\
\noindent Therefore ${\cal CFL} \equiv$ the closure of \{$D_2$\} under $h^{-1}$, h \footnote{With $h^{1:1}$ in place of h too.} and $\cap_R$.
\paragraph{Challenge questions:}
Define AFL(A) := closure of $\set{\Sigma^*,\phi,A}$ under h, $h^{-1}$ and $\cap_R$.
We know AFL($D_2$) = ${\cal CFL}$.
\begin{enumerate}
\item What is AFL(\{$0^n1^n ~ | ~ n \geq 0$ \})?
\item What is AFL($D_1$)?
\end{enumerate}
% \lecture{**LECTURE-NUMBER**}{**DATE**}{**LECTURER**}{**SCRIBE**}
% \lecture{24-25}{November 1st and 3rd}{K.W. Regan}
% {Debra Burhans and Kannan Govindarajan}
\section{Rational Relations Versus Regular Languages}
[Lectures 24--25, scribed by Burhans and Govindarajan.]
\bigskip
Given a language L $\subseteq ~ \Sigma^*$, define the relation $\sim_L$ as follows:
\begin{center}
$\forall x,y \in \Sigma^*,~ ~ x \sim_L y ~ ~ {\rm if}~ ~ \forall z \in \Sigma^*( x.z \in L \Leftrightarrow y.z \in L)$.
\end{center}
For any equivalence relation $\sim$ on a set S and any D $\subseteq$ S, define
the index of $\sim$ on D to be the number of elements in D which fall into
different equivalence classes.
\begin{itemize}
\item D {\em shatters} $\sim$ if no two distinct elements in D are equivalent.
\item Let $N_L(n) \equiv$ Index of $\sim_L$ on $\Sigma^{\leq n}$.
\end{itemize}
\begin{theorem}[Myhill-Nerode Theorem]
L is regular if and only if $\sim_L$ has finite index on $\Sigma^*$, i.e.
$N_L(n)$ is bounded as n $\rightarrow ~ \infty$.
\end{theorem}
\begin{definition}
Given a relation $\rho$ on $\Sigma_1^* \times \ldots \times \Sigma_k^*$ define
$(x_1,x_2,\ldots,x_k) \sim_\rho (y_1,y_2,\ldots,y_k)$ if $\forall z_1 \in \Sigma_1^*, ~ z_2 \in \Sigma_2^*, \ldots ,~ z_k \in \Sigma_k^*$.
\begin{center}
$\rho(x_1.z_1,x_2.z_2,\ldots,x_k.z_k) ~ \Leftrightarrow ~ \rho(y_1.z_1,y_2.z_2,\ldots,y_k.z_k) $
\end{center}
\end{definition}
A ``k-ary'' Myhill-Nerode theorem would read :\\
\begin{center}
$\forall$ relations $\rho$, $\rho$ is rational $\Leftrightarrow ~ \sim_{\rho}$ has finite index on $\Sigma_1^* \times \ldots \times \Sigma_k^*$.
\end{center}
\paragraph{$\Rightarrow$ is false:}
Let $\rho$ be $\{(x_1 ~ , ~ x_2) ~ : ~ x_1 \sqsubseteq x_2 \} $.\\
D = $\{ (a ~ , ~ a^n b) : n \geq 1 \} $. D is infinite and D shatters $\sim_\rho$.\\
Let $(x_1 ~, ~ x_2) = (a~,~a^m b)$ and $(y_1 ~, ~ y_2) = (a~,~a^n b)$ and
m $<$ n. Take z = $(a^{n-1} ~ , ~ a^{n-1})$. Clearly $(x_1.z_1 ~ , ~ x_2.z_2) \not\in \rho$ and
$(y_1.z_1 ~ , ~ y_2.z_2) \in \rho$.
\paragraph{But $\Leftarrow$ is true!}
If $\sim_\rho$ has finite index, build a k-ary transition graph N.
\begin{itemize}
\item The states of N correspond to the equivalence classes of $\sim_\rho$.
\item $F_N = \{ [(x_1,x_2,\ldots,x_k)] ~ | ~ \rho(x_1,x_2,\ldots,x_k) holds \}.$
\item Transitions are on singletons $(a_1,\ldots,a_k)$, $a_j \in \Sigma_j$ or $a_j = \epsilon$,
$\delta([(x_1,\ldots,x_k)],(a_1,\ldots,a_k)) = [(x_1.a_1,\ldots,x_k.a_k)]$
\end{itemize}
\paragraph{Note:}
This is not a k-tape DFA because N can make stationary moves. We can however
make N special by adding a state f with $(\epsilon,\ldots,\epsilon)$ arcs.
>From this we can use the algorithm to construct the corresponding rational
expression for $\rho$.
\begin{definition}
A rational relation $\rho(x_1,\ldots,x_k)$ is said to be length preserving if
$|x_1| ~ = \ldots = ~ |x_k|$.
\end{definition}
\paragraph{Research question:}
Characterize rational relations of finite index. Being length preserving is
sufficient for a rational relation to have finite index, but is not necessary.
\vspace{2.0in}
\paragraph{Note:} The definition of accepting computation forces the k-tape NFA
to read all of its input.
\begin{theorem}
$\rho$ is a k-ary rational relation if and only if there is a k-tape ${\rm NFA}_\epsilon$ N such that N accepts $\rho$.
\end{theorem}
\begin{proof}
Same as k=2 case.
\end{proof}
\begin{theorem}
If $(\epsilon,\ldots,\epsilon) \not\in \rho$ then $\rho$ is rational if and only if
there is a k-tape ${\rm NFA}_\epsilon$ N that accepts $\rho$ with no arcs labeled
$(\epsilon,\ldots,\epsilon)$.
\end{theorem}
\subsection{A Pumping Lemma for Rational Relations}
\begin{lemma}[Pumping Lemma for Regular Languages]
If L is regular then there exists $n > 0$ such that for all
$x \in L$ with $|x| \geq n$,
there exist $u,v,w \in \Sigma^*$ such that
$x = uvw$, $|uv| \leq n$, $v \neq \epsilon$, and
for all $c \geq 0$, $uv^cw \in L$.
\end{lemma}
\begin{lemma}[Rational Pumping Lemma]
If $\rho$ is rational, then there exists $n > 0$ such that
for all $(x_1,\ldots,x_k) \in \rho$,
if $(\exists i : ~|x_i|~ \ge~ n)$, then there exist $k$-tuples
$(u_1,\ldots,u_k)$, $(v_1,\ldots,v_k$, and $(w_1,\ldots,w_k)$
such that for each $i$,
$x_i = u_iv_iw_i \AND |u_iv_i| \leq n$, and for all $c \geq 0$,
$(u_1v_1^cw_1,\ldots,u_kv_k^cw_k) \in \rho$,
{\it and\/} $(v_1,\ldots,v_k) \neq (\epsilon,\ldots,\epsilon)$.
\end{lemma}
\begin{proof}
The proof is the same proof by induction on $\rho$ that was done for k=2.
As $\rho$ is rational, there is a k-tape $\NFA_\epsilon$ M \footnote{M has no arcs labeled $(\epsilon,\ldots,\epsilon)$ except from the start state s to the final state f if $(\epsilon,\ldots,\epsilon) \in \rho$.} such that $\rho = \rho_M$.
Let n = number of states in M, let $\stackrel{\rightharpoonup}{c}$ be some accepting computation of
M on $(x_1,\ldots,x_k)$. Some $x_i$ has length $\geq $ n
and every arc label is a
singleton, therefore there must exist n transitions $\stackrel{\rightharpoonup}{c}$
of the form
\begin{center}
$(p_j,(a_{j_1},\ldots,a_{j_k}),q_j) $ such that $a_{j_i} \neq \epsilon$
\end{center}
Let S = $\set{s} \cup \set{q_1,\ldots,q_j,\ldots,q_n'}$ be the set of states
encountered after reading a character in $x_i$ where $n'$ = $|x_i| ~ \geq ~ n$.
Since $\|S\| \geq n+1$, there must be two repeated states.
\end{proof}
\paragraph{Example:}
Let $\rho$ = \{ (p,t) : p is not a substring of t\}.\\
Given n, let $(x_1,x_2)$ = $(a^{n+1},a^nba^n)$. Let $\bar{x} = \bar{u}\bar{v}\bar{w}$, $(v_1,v_2) \neq (\epsilon,\epsilon)$. By $|u_2v_2| ~ \leq n$,
$v_2$ comes to the left of b.
There are two possibilities:
\begin{enumerate}
\item If $v_1 \neq \epsilon$, pump down to get
$(a^m,\_ba^n)$, $m < n+1$, so $m \leq n$.
$a^m$ is a substring of $\_ba^n$. \_ stands for an arbitrary string of a's.
\item If $v_1 = \epsilon$ then $v_2 \neq \epsilon$,
so pump up to get $(a^{n+1},a^Nba^n)$
with $N \geq (n+1)$.
\end{enumerate}
\begin{corollary}
Rational relations are not closed under complement.
\end{corollary}
\paragraph{Question:} Can one pump each component of $\rho$ separately? In which
case the pumping lemma reads as follows:
\begin{lemma}[Modified Rational Pumping Lemma]
If $\rho$ is rational, then ($\exists$ n $>$ 0) such that $\forall (x_1,\ldots,x_k)$
such that $(x_1,\ldots,x_k) \in \rho ~, ~ \exists i :~
|x_i| \geq n,~ \exists( u_1,\ldots,u_k , v_1,\ldots,v_k , w_1,\ldots,w_k)$
such that for each i
$x_i = u_iv_iw_i \wedge$ for each i
$ |u_iv_i| \leq n \wedge (\forall (c_1,\ldots,c_k) > (0,\ldots,0)) $\\
$(u_1v_1^{c_1}w_1,\ldots,u_kv_k^{c_k}w_k) \in \rho \wedge (v_1,\ldots,v_k)
\neq (\epsilon,\ldots,\epsilon)$.
\end{lemma}
\paragraph{Answer:}
No, the rational relation $\rho$ = $(a,b)^+$ is an example.
\paragraph{Exercises:}
Prove that complements of length preserving rational relations are
also length preserving rational relations.
\paragraph{Footnote to the Pumping Lemma proof :}
Find a step m such that for some i, $|a_{i1},a_{i2},\ldots,a_{im}|$ = n and
$\forall j \neq i ~ ~ |a_{j1},a_{j2},\ldots,a_{jm}| \leq m$.
m is the step at which some head has read n symbols on its tape.
If $\rho(x_1,\ldots,x_k)$ holds, and there exists some i
such that $|x_i| \geq n$,
then there exists an m which is the first step at which some head moved off
cell n on its tape.
% \lecture{**LECTURE-NUMBER**}{**DATE**}{**LECTURER**}{**SCRIBE**}
% \lecture{26}{November 5, 1993}{K. Regan}{Daniel F. Boyd}
%
% \begin{Comment}
% (Help on problem set, a remnant from last time). For problem (1):
% Define $\rho\v x 1 k $ to be length-preserving if, whenever $\rho
% \v x 1 k $ holds, $|x_1| = |x_2| = \ldots |x_k|$.
%
% Prove that if $\rho$ is rational, then so is $\lambda \backslash
% \rho$,
%
% $$\lambda = \{ \v x 1 k | |x_1| = |x_2| = \ldots |x_k| \}.$$
%
% Footnote to the PL proof: If $\rho \v x 1 k $ holds and there exists
% an $i$ such that $|x_i \geq n$, then there exists an $m$ such that $m$
% is the step at which some head moves off cell $n$ on its tape. Find a
% step $m$ such that for some $i$, $|a_{i1}, a_{i2}, \ldots, a_{im}| =
% n$ and, for all $l$, $a_{l1}, a_{l2}, \ldots, a_{lm}| \leq n$.
%
% \end{Comment}
\section{Descriptive Complexity}
[Lecture 26, scribed by Boyd.]
\bigskip
There are three main ways to represent a language in a formal system.
\begin{enumerate}
\item Strings as ground objects: strings are like natural numbers. A
formula $\Psi$ with one free variable $x$ of type string (or natural
number).
$$L(\Psi) = \{ x : \Psi(x)\,\hbox{is true}\}$$
\item Strings as {\tt Array[0..n-1] of Char}, with predefined
relations
$$Z(i) = \cases{1 & if char $i$ = 1\cr 0 & if not.}$$
or, for alphabets $\Sigma$ other than $\{0,1\}$,
$$Z_c(i) = \cases{\hbox{true} & if $\hbox{char}\; i = c$\cr
\hbox{false} & if not.}$$
and possibly other relations --- (Seeing strings as relational
structures) -- or a sentence $\sigma$ with constants $0, 1, N$ and
variables $i, j$ of type {\tt index into string}, and later, {\tt
index into index into string}.
$$L(\sigma) = \{ x : x \models \sigma \}$$
(Read that as $\sigma$ is true for $x$ with $N := |x|$. ``$\models$''
(\verb#\models#) is used to mean ``satisfies''.
\item Strings as bit-strings. $x = x_1 \cdot x_2 \cdots x_n$
Represent by a boolean formula $\Psi$ with $n$ free variables
$x_1\ldots x_n$ of type $\{0,1\}$ (or more generally of type
$\Sigma$)
$$L_\Psi = \{x | \Psi \vrange x 1 n = \hbox{true}, \hbox{where $x = x_1
\ldots x_n$}\}$$
A boolean formula (over $\neg$, $\And$, $\Or$) is the special case of
a circuit over ($\neg$, $\Or$, $\And$) where each gate has fan-out 1.
(The lecturer sketched some examples:)
\vspace{2in}
$$\phi_3=((x_1\land x_2)\lor(x_2\land x_3))
\land((\neg(x_1\land x_2))\lor(\neg(x_2\land x_3)))\qquad
L(\phi_3) = \{110, 011\}$$
Problem: to define a {\em language\/}, you need one boolean formula
for each input length; it's a non-uniform description of a language.
One needs a family $\{\Phi_n | n = 0, 1, 2, \ldots\}$ of formulas.
\end{enumerate}
(1) and (2) are uniform -- only one object is needed to specify $L$
for all lengths.
\begin{example}
$$\sigma : \exists i : \neg Z(i) \land ( \forall j : j \neq i \implies
Z(j)$$
$$
L_\sigma = 1*01*.
$$
Implicitly, $j, i$ range over $\{0, \ldots, N-1\}$. We are saying
that some $x_i$ equals $0$ and that all other places are 1.
Alternatively (this is preferred):
$$\sigma : \exists i : Z(i) = 0 \land (\forall j, j = i \lor Z(j) =
1)$$
Predicates used: $Z(\cdot)$, $=$.
\end{example}
\begin{example}
$$\tau = \exists i : Z(i) = 0 \land ( \forall j :
((j < i) \implies Z(j) = 0) \land ((j > i) \implies Z(j) = 1))$$
$$L_\tau = 0*01$$
Predicates: $Z$, $=$, $<$. $=$ and $<$ can be defined in terms of $\le$
thusly: $(i=j) \equiv (i\leq j) \land (j \leq i)$.
\end{example}
\begin{example}
$$\rho: \exists k : \forall i, j
[ ( 2k=N
\land i \leq k
\land k < j
\land \hbox{NDIFF}(i, j) )
\implies (
Z(i) = 1 \iff Z(j) = 1 ) ] $$
where $\hbox{NDIFF}(i,j) \equiv (j-i=N)$.
$$L_\rho = \{ x : |x|\,\hbox{is even}\;
\forall i, x_i = x_{\floor{{x\over 2}} + i}
\equiv ww\;\hbox{for}\,w\in \Sigma^*\}$$
Here, we used NDIFF like a subtraction function.
\end{example}
Claim: as long as we stay in the area delineatedby $\sigma$ and
$\tau$, we get a subset of regular languages. With
$\hbox{BIT}(i,c)$ (the $c$th bit of $i$ is 1), we can do anything a TM
can do.
% \input{DFBmacs.tex} %uncomment if you dare
% \def\vrange#1 #2 #3 {(#1_{#2}, \ldots #1_{#3})}
% \def\emsg{\emptystring}
%\lecture{**LECTURE-NUMBER**}{**DATE**}{**LECTURER**}{**SCRIBE**}
% \lecture{27-28}{November 8,10, 1993}{K. W. Regan}{Daniel F. Boyd,
% Mike Smolowitz}
\section{Operations on Rational Relations}
[Lectures 27--28, scribed by Boyd and Smolowitz.]
\bigskip
A formula $\Psi\vrange x 1 k $ with $k$ free variables of type {\tt STRING}
defines a $k$-ary relation $\rho_\Psi = \{ \vrange x i k | \Psi \vrange x 1 k
\;\hbox{holds}.\}$. It also defines the language $\Theta_\Psi =
\{ \langle x_1 \ldots x_k \rangle | \Psi\vrange x i k \;\hbox{holds}.\}$.
Here are some operations on $k$-ary relations
$\rho \subseteq ( \Sigma^* \times \Sigma^* \times \cdots \Sigma^*)$
(all the $\Sigma$s are the same alphabet):
\subsection{Set operations}
Boolean $(\cup, \cap, \sim)$, which are equivalent to logical
$(\lor, \land, \neg)$.
\subsection{Explicit Transformations}
\label{ssec:xt}
\subsubsection{Substitution}
Let $\sigma$ be an $m$-ary relation. Let $k>0$, let $t:\{1\ldots m\}
\mapsto \{1\ldots k\}$ ($m\leq k$, $m > k$ are both ok).
Define
$$\sigma_t = \{ \vrange x 1 k | \rho \vrange x {t(1)} {t(m)}
\:\hbox{holds}\}.$$
(In logic, this would be substitution of variables for variables.)
\subsubsection{Instantiation}
Let $\sigma$ be $(k+1)$-ary, let $w$ be any fixed string. Define
$$\sigma_w = \{ \vrange x 1 k | (x_1, \ldots, x_k, w) \in \sigma\}$$
(In logic, this is substituting a fixed value for a variable.)
\begin{proposition}
The rational relations are not closed under explicit transformation.
\end{proposition}
\begin{example}
Let $\Sigma = \{a,b\}$, and define
$$\rho = \{(x,y,z) | x \sqsubseteq y \;\hbox{and $z$ is a suffix
of $y$}\}$$
$\rho$ is rational. For the rational expression, consider cases (i)
$(x,z)$ overlap in $y$ (ii) they don't.
\begin{eqnarray*}
\rho =&&
\overbrace{((a,a,\emsg)\cup(b,b,\emsg))^*}^{\hbox{$x\sqsubseteq y$}}
\overbrace{((a,a,a)\cup(b,b,b))^*}^{\hbox{overlap}}
\overbrace{((\emsg,a,a)\cup(\emsg,b,b))}^{\hbox{suffix}}\\
&\cup&
((a,a,\emsg)\cup(b,b,\emsg))^*
\underbrace{((\emsg,a,\emsg)\cup(\emsg,b,\emsg))^*}_{\hbox{no overlap}}
((\emsg,a,a)\cup(\emsg,b,b))\\
\end{eqnarray*}
But now let $t(1) = 1$, $t(2) = 2$, $t(3) = 1$. $\rho_t = \{(x,y,x)
\in \rho\}$. Then $\rho_t$ is the set of all pairs $(x,y)$ where $x$
is a prefix of $y$ and $x$ is a suffix of $y$.
This is not a rational relation. Imagine a 3TNFA $N$ for $\rho$, and
try to map it over to a 2TNFA $N'$ for $\rho_t$. Intuitively, $N'$
needs a third head on the $x$ tape, (so it can scan part of $x$ twice
in case it needs to match it twice with different parts of $y$).
\end{example}
\subsubsection{A Taxonomy of Explicit Transformations}
\label{sssec:taxonomy}
Explicit transformations can be broken down into:
\begin{enumerate}
\item {\bf Permutation of $k$ coordinates}
\label{perm}
It suffices to consider the
following two transformations, as together they generate the entire
symmetric group on $k$ items:
\begin{eqnarray*}
\rho_{(1,2)} &=& \{ x_2, x_1, x_3,\ldots,x_k) | \vrange x 1 k \in \rho\}\\
\rho_{(1\ldots k)} &=& \{ ( x_2, x_3, \ldots, x_k, x_1) | \vrange x 1 k \in
\rho \}
\end{eqnarray*}
\begin{proposition}
The rational relations are closed under permutation of coordinates.
\end{proposition}
\begin{proof}
Relabel the tapes of the KHNFAs.
\end{proof}
\item {\bf Adding a non-quantified variable}
\label{addvar}
$$ \rho' = \{ x_1, \ldots x_k, x_{k+1}) | \vrange x 1 k \in \rho\} $$
\begin{proposition}
If $\rho$ is rational, then so is $\rho'$.
\end{proposition}
\begin{proof}
$N'$ reads and ignores $x_{k+1}$. ($N'$ still has to guess
where $x_k$ ends.)
\end{proof}
\item {\bf Instantiating a variable $x_{k+1}$ to a fixed string $w$.}
\label{instance}
\begin{proposition}
Ditto.
\end{proposition}
\begin{proof}
Ditto.
\end{proof}
\item {\bf Identifying two variables}
\label{ident}
$$
\rho'' = \{ \vrange x 1 {k-1} | ( x_1, \ldots, x_{k-1}, x_{k-1} ) \in \rho\}
$$
\end{enumerate}
\begin{proposition}
Every explicit transformation under \ref{ssec:xt} is a
finite sequence of operations (\ref{perm}, \ref{addvar},
\ref{instance}, \ref{ident}).
\end{proposition}
\begin{proposition}
Operation \ref{ident} is the one under which rational relations are
not closed.
\end{proposition}
\begin{proof}
Reductio ad absurdum: They aren't closed; they are closed under
(\ref{perm}, \ref{addvar}, \ref{instance}), so (\ref{ident}) is the
one.
\end{proof}
On the homework, (\ref{perm}, \ref{addvar}, \ref{instance}) are the
``innocuous'' explicit transformations.
\subsection{Unbounded Existential Quantification}
\label{sec:uboundq}
$E(\rho)$ is the $(k-1)$-ary relation $E(\rho) := \{\vrange x 2 k |
(\exists x_1 \in \Sigma^*) \vrange x 1 k \in \rho\}$. This could also be
written as $\{\vrange x 1 {k-1} | (\exists x_k \in \Sigma^*) \vrange x 1 k \in
\rho \}$. This is a very powerful operation.
\begin{Comment}
In a sense, it could
be thought of as instantaneously atomically searching the entire space
of possible computations of a DGSM. -- DB
\end{Comment}
\subsection{Bounded Existential Quantification}
\label{sec:bquant}
Let $S(n)$ be any positive, real-valued function. Then $E_S(\rho) =
\{ (x_1, \ldots, x_{k-1}, z) | (\exists x_k : |x_k| \leq S(|z|)\; \vrange x
1 k \in \rho\}$. $E_S$ is $k$-ary, but $z$ is used only for its
length.
\begin{definition}
The {\sl rudimentary\/} relations are all those relations defined
from the rational relations by
\begin{enumerate}
\item Booleans
\item Explicit Transformation
\item Bounded Existential Quantification where $S(n) \in O(n)$.
({\it i.e.\/} linear-length-bounded existential quantification)
\end{enumerate}
\end{definition}
The following are equivalent:
\begin{itemize}
\item Saying $(\exists x):|x| \leq c|z|$ for strings
\item Saying $(\exists x):x\le(2^{|z|})^c$ where $z=2^k -1$
\end{itemize}
These are essentially like ``polynomial magnitude-bounded
quantification''.
Also polynomial-length-bounded quantification $(\exists x) |x| <
|z|^c$ is equivalent to $2^{\hbox{polylog}(x)}$-magnitude-bounded
quantification.
If $S(n) = c \log n$, then there are at most $|z|^c$ many strings $x$
such that $|x| \leq c \log (|z|)$. A parallel RAM with $n^c$
processors can try them all in parallel, in unit time.
\section{Aside}
\label{sec:regs}
Suppose $R$ is any language. Define $\iota_R = \{(x,x) | x \in R\}$.
If $R$ is regular, then $\iota_R$ is rational. (Exercise.)
For any language $L$, $L\cap R = \iota_R(L) = \iota_R^{-1}(L)$ because
\begin{eqnarray*}
\iota_R(L) =& \{ y | \exists x \in L, (x,y) \in \iota_R\} &= L\cap R\\
\iota_R(L)^{-1} =& \{ x | \exists y \in L, (x,y) \in \iota_R\} &= L\cap R
\end{eqnarray*}
In the notation of Harju and Kleijn \cite{HaKl93}, $\CM$ (the {\it marking\/}
function) stands for the operation of concatenating $\$$.
\begin{Comment}
If $\CC$ is closed under $h^{-1}, H$ and is nonempty, is $\{\$\} \in
\CC$?
Consider the rational relation $\tau = ((a,\emsg)\cup(b,\emsg))^*(\emsg,\$)$.
$\tau(L) = \{\$\}$. Can $\tau$ be expressed using $h, h^{-1}$?
\end{Comment}
Harju and Kleijn \cite{HaKl93} show that for regular $R$,
$\iota_R \in \CH^{-1}\cdot \CH \cdot \CH^{-1} \cdot \CM$. (Boyd and
Smolowitz attempted to show that $\iota_R \in \CH \cdot \CH^{-1} \cdot
\CM$.)
\begin{Comment}
Is $\iota_R \in \CG\CH \cdot \CH^{-1} \cdot \CM$? Can the gh be made
total with $[d:e]$ fixed delay?
\end{Comment}
$h^{-1}(L)$ is always defined as a language. {\em Watchword\/}: where papers
refer to ``linear bounded erasing'', look for a fixed-delay gh.
%\lecture{**LECTURE-NUMBER**}{**DATE**}{**LECTURER**}{**SCRIBE**}
%\lecture{29}{November 12}{K.W. Regan}{Mike Smolowitz, Dan Boyd}
% **** YOUR NOTES GO HERE:
\section{Examples of Rudimentary Languages}
[Lecture 29, scribed by Boyd and Smolowitz.]
\bigskip
Let $L = \{x \in \{a,b\}^* : \#a(x) = \#b(x)\}$. $L$ is non-regular, but it is
rudimentary. Here is how we determine it.
Define two homomorphisms: $h_1(a) = a, \: h_1(b) = \epsilon \, ; \: h_2(a) =
\epsilon, \: h_2(b) = a$. Then $\forall x \in \Sigma^*, x \in L \Leftrightarrow
h_1(x) = h_2(x)$.
Define $\rho_1 := \{(x,y) : h_1(x) = y\}$ and $\rho_2 := \{(x,y) : h_2(x) =
y\}$. Then $\forall x \in \Sigma^*, x \in L \Leftrightarrow (\exists y) \:
[(x,y) \in \rho_1 \wedge (x,y) \in \rho_2]$.
$\rho_1$ and $\rho_2$ are both rational, so they are both rudimentary. To get
$L$ to be rudimentary, we need ``$(\exists y)$'' to be linear length-bounded.
Note that if $h_1(x) = y$ or $h_2(x) = y$, then $|y| \leq |x|$, so adding the
length constraint won't change the truth value.
Thus we may formally define
$$x \in L \leftrightarrow (\exists y: |y| \leq |x|) \: [(x,y) \in \rho_1
\cap \rho_2].$$
Use the formal definition of a relation $\sigma$ obtained by length-bounded
existential quantification from $\rho_1 \cap \rho_2$.
Let $\sigma(x,z) \leftrightarrow (\exists y: |y| \leq |z|) \: [(x,y) \in
\rho_1 \cap \rho_2]$. ($z$ is a place-holder for $\sigma$, but sets the
length bound for $y$.) Finally we get to $L$ by an existential
quantification of type (2d), i.e. identifying two variables:
$$x \in L \leftrightarrow (x,x) \in \sigma.$$
Since $\rho_1, \rho_2 \in \RUD, \rho_1 \cap \rho_2 \in \RUD$, and $\sigma \in
\RUD$, we have $L \in \RUD$.
By similar means, this language is also in \RUD:
\begin{displaymath}
B = \{x \in \{ (, ), [, ] \}^*: \mbox{\# of ['s in $x$ = \# of ]'s in $x$}
\wedge \mbox{\# of ('s in $x$ = \# of )'s in $x$} \}.
\end{displaymath}
\begin{lemma}
If $L \in \RUD$ and $h$ is a homomorphism, then $h^{-1}(L) \in \RUD$.
\end{lemma}
\begin{proof}
For all $x$, $x \in h^{-1}(L) \leftrightarrow (\exists y) \: [y \in L
\wedge h(x) = y]$. \\
Let $c$ := max $\{|h(a)|: a \in \Sigma \}$. (Homomorphisms always have a finite
amount of expansion that they can do.) Then whenever $h(x) = y$, necessarily
$|y| \leq c|x|$.
Hence $\forall x, x \in h^{-1}(L) \leftrightarrow (\exists y: |y| \leq c|x|) \:
[y \in L \wedge h(x) = y]$.
Let $\tau(x,y) \leftrightarrow y \in L \wedge h(x) = y$.
Let $\sigma = \{(x,z): (\exists y: |y| \leq c|z|) \: \tau(x,y) \}$.
In $\tau$'s definition, ``$y \in L$'' is rudimentary, and ``$h(x) = y$'' is
rational. To be completely pedantic, let $\lambda = \{(x,y): y \in L \}$,
adding an unidentified variable by operation (2b).
Thus $\sigma = \lambda \cap \rho_h$ = rudimentary $\cap$ rational, and so
$\sigma$ is rudimentary. Therefore $h^{-1}(L)$ is rudimentary.
\end{proof}
\medskip
\noindent Q: Are rudimentary languages preserved under {\it forward}
homomorphism?
\noindent A: $y \in h(L) \leftrightarrow (\exists x) \: [x \in L \wedge
h(x) = y]$.
This would be rudimentary if we could find a constant $c$ and guarantee that
$|x| \leq c|y|$. But this might not hold true, if $h$ can perform erasing.
We will see that the answer to this question is ``no.''
Thus \RUD\ is closed under length-preserving homomorphisms; under $d : e$
gh's; with fixed $d$ \& $e$ (exercise); or even $d : e$ rational relations.
\medskip
Recall that $\Gamma_2 = \{ (, ), [, ] \}$.
Define $H_) = \{x \in \Gamma_2^*: \mbox{the shortest nonempty prefix of $x$
which belongs to $B$ ends in )} \: \}$ \\
and $H_] = \{x \in \Gamma_2^*: \mbox{the shortest nonempty balanced prefix
of $x$ ends in ]} \: \}$.
\begin{lemma}
$\forall x, x \in D_2 \Leftrightarrow ( \: x \in B$; for all
ways of writing $x = u(v, \: (v \in H_) \:$; and for all ways
of writing $x = u[v, \: [v \in H_] \: )$.
\end{lemma}
\begin{proof}
Let $\pi(x) \leftrightarrow x \in B \wedge (\forall u,v \in \Gamma_2^*) \:
\mbox{\large \{} \{ x = u(v \rightarrow (v \in H_) \} \wedge
\{x = u[v \rightarrow [v \in H_] \} \mbox{\large\} }$.
(Note: curly braces were used to avoid confusion with the characters of
$\Gamma_2$ that appear in the expression.)
Most of the expression for $\pi(x)$ is clearly rudimentary:
\begin{itemize}
\item $x \in B$ is certainly rudimentary, because $B \in \RUD$.
\item The boolean operators $\wedge$ and $\rightarrow$ are rudimentary.
\item Without loss of generality, we can restrict $u$ and $v$ to have
length $|x|$ or less.
\item $x = u(v$ is an instance of the concatenation operation, which is
rudimentary, applied twice. The expressions $(v$, $u[v$, and $[v$ are similar.
\item Note that $(\forall x: |x| \leq |z|) \: Q(x) \equiv \: \sim (\exists x:
|x| \leq |z|) \: \sim Q(x)$. Hence length-bounded quantification is a
composition of three rudimentary operations.
\end{itemize}
It remains to show that $H_)$ and $H_]$ are rudimentary. They have similar
structure, so we will do it for $H_]$ only, using the definition of $B$.
For all x, we have:
\begin{eqnarray*}
x \in H_] & \leftrightarrow & (\exists y: |y| \leq |x|) \: \mbox{\large[}
[\: y \neq \epsilon \wedge y \sqsubseteq x \wedge y \in B \wedge
\mbox{$y$ ends in ']'} \: ] \\
& & \wedge \: (\forall z: |z| \leq |y|) \:
[\: (z \neq \epsilon \wedge z \sqsubseteq y \wedge z \in B) \rightarrow z = y
\: ] \mbox{\large]}.
\end{eqnarray*}
The $z$ part says that there is no shorter prefix than y which is nonempty
and balanced.
Every constituent relation is rational, so $H_]$ is rudimentary. Thus $\pi(x)$
is rudimentary. Since $\pi(x)$ is equivalent to $x \in D_2$, $D_2$ is
rudimentary as well.
\end{proof}
\noindent {\it Note:} Technically, to complete the definition of $D_2$, we need
to say not ``$x \in H_]$'', but actually ``$[v \in H_]$''.
Define $\rho(v) \equiv [v \in H_]$. Then $\rho(v) \leftrightarrow
(\exists w: |w| \leq 2|v|) \: [ \, w = [v \wedge w \in H_] \, ]$.
\medskip
\noindent {\it Research problem:} Can one get every rudimentary language with
$c = 1$? Or is there somewhere you'll always need to say ``$\exists w:
|w| \leq |v| + 1$''?
%\lecture{**LECTURE-NUMBER**}{**DATE**}{**LECTURER**}{**SCRIBE**}
%\lecture{30}{November 15}{K. W. Regan}{Mike Smolowitz, Dan Boyd}
% **** YOUR NOTES GO HERE:
\section{RUD and CFL}
[Lecture 30, scribed by Boyd and Smolowitz.]
\bigskip
\noindent {\it Recall:} The class RUD of rudimentary languages is closed
under $h^{-1}$. Also, if $L \in \RUD$, then $h(L) \in \RUD$, {\it provided}
that $(\exists c > 0) \: (\forall x \in L) \: |h(x)| \geq |x|/c$.
$h$ is a homomorphism; it can ``wipe out'' strings $w \not\in L$ so long as
it is restrained on $x \in L$ (i.e. $h$ leaves a constant fraction, or amount
of evidence, unerased). So
$$y \in h(L) \leftrightarrow (\exists x: |x| \leq c|y|) \: (h(x) = y
\: \wedge \: x \in L).$$
Note that the ``$\exists x$'' part is linear length-bounded; the remaining
relations are rudimentary. Thus $h(L)$ is rudimentary if $h$ obeys the
above condition.
\medskip
Recall KWR's proof of: For all CFL's $L$, $\exists n, t, h, R:
L = t(h^{-1}(D_n) \cap R)$. The homomorphism $t$ was not length-preserving,
but it had the property that $\forall z \in h^{-1}(D_n) \cap R, |t(z)| \geq
|z|/3$.
$R = L(G_R)$, with the grammars $G$ and $G_R$ described as follows:
$$
\parbox[t]{3 in} {
\begin{center}
\underline{$G$}
\end{center}
\begin{itemize}
\item Productions have the form $A \rightarrow BC$.
\item To derive $y$, with $|y| = m$, use $m-1$ variable productions and
$m$ terminal productions.
\end{itemize} }
\qquad
\parbox[t]{3 in} {
\begin{center}
\underline{$G_R$}
\end{center}
\begin{itemize}
\item The corresponding productions have the form $A \rightarrow (_iB$ and
$D \rightarrow \; )_iC$.
\item This grammar gives you $m-1 \; (_i$'s and $m-1 \; )_i$'s.
\item $t(z) = y$.
\item $|z| \leq 2(m-1) + m \leq 3m = 3|y|$.
\end{itemize} }
$$
Moreover, when we had $L = t'(h_2^{-1}(D_2 \cap R')$, then $\forall z \in
h_2^{-1}(D_2 \cap R'), |t(z)| \geq |z|/3k$, where $k$ = number of pure variable
productions in the given CFG $G$ for $L$. So $k$ does not depend on $|z|$.
By KWR's inclusion of all rational relations in the rudimentary relations,
$R \in \RUD$. Also, $D_2 \in \RUD$. Therefore $h_2^{-1}(D_2)$, $h_2^{-1}(D_2)
\cap R$, and $t(h_2^{-1}(D_2) \cap R)$ are all in RUD. Using the Chomsky -
Sch\"{u}tzenbeger Representation Theorem, we have proved:
\begin{theorem}
Every CFL is rudimentary.
\end{theorem}
\begin{proposition}
Every finite intersection of CFL's is rudimentary.
\end{proposition}
Thus there are rudimentary non-CFL's, such as $\{ww \; | \; w \in \Sigma^*\}$.
\section{RUD and the Arithmetic Hierarchy}
\noindent {\it Question:} Where is RUD in the Arithmetic Hierarchy?
\begin{proposition}
Every language $L \in \RUD$ is a DCSL; i.e. $L$ belongs to DSPACE[$O(n)$]. \\
{\it Strengthened version:} For every rudimentary relation $\rho$,
$\Theta_\rho \in $ DSPACE[$O(n)$], where \\
$\Theta_\rho = \{ \; | \; \rho(x_1, \ldots ,x_k)$ holds \}.
\end{proposition}
\begin{proof}
We will do structural induction on the way $\rho$ is built up.
\noindent {\it Basis.} For every rational relation $\rho$, there is a constant
$C_\rho$ and a Turing machine $M_\rho$ such that $L(M_\rho) = \Theta_\rho$
and $M_\rho$ runs in space $C_\rho n$. This is true with $C_\rho \leq 3$.
$M_\rho$ has $2k$ tracks. On odd tracks $i'$ for the $i$th tape, $M_\rho$
maintains the current location of head $h_i$. $M_\rho$ remembers the state of
the $k$-head NFA in its finite control.
Let $N$ be the $k$-tape NFA such that $N$ accepts $\rho$. Without loss of
generality, some head of $N$ advances for each step. Also, $N$ has at most
two branches at each step. Hence every computation of $N(x_1, \ldots ,x_k)$
runs for at most $n := |x_1| + |x_2| + \ldots + |x_k|$ steps.
$M_\rho$ is deterministic, and keeps one more tape with $n$ cells to cycle
through all $w \in \{0,1\}^n$ which determine the different computation paths
by $N$. Then $M_\rho()$ halts and accepts iff it finds an
accepting computation of $N$.
\noindent {\it Note:} Life here is much easier if we use concat($x,y,z$) as the
only basis predicate.
\medskip
\noindent {\it Induction.} The cases are: $\rho = \sigma \cup \tau$; $\rho =
\sigma \cup \tau$; $\rho = \; \sim\sigma$; explicit transformations; and
$\rho = \{ \; | \; \exists x_1: |x_1| \leq z,
(x_1, \ldots ,x_k) \in \sigma\}$.
\end{proof}
Therefore rudimentary relations are recursive.
In the next two lectures, we will state and prove Wrathall's Theorem
about the class $\RUD$, namely, that $\RUD$ equals the linear time hierarchy.
%\lecture{**LECTURE-NUMBER**}{**DATE**}{**LECTURER**}{**SCRIBE**}
% \lecture{31--32}{November 17,19}{K.W. Regan}{D. Sivakumar\footnotemark}
% \footnotetext{Lecture Notes for Nov 17
% partially based on Debra Burhans' notes.}
% **** YOUR NOTES GO HERE:
\section{The Linear Time Hierarchy}
[Lectures 31--32, scribed by Sivakumar, including Debra Burhans' notes
for part of lecture 31.]
\bigskip
Given a binary relation $\rho$ and a length bound $S(n)$, we can write
$$E_S(\rho) = \set{x~|~(\exists y : |y| \leq S(|x|)~\rho(x,y)}.$$
Technically, $E_S(\rho)$ contains $\epsilon$ iff $\rho$ contains
$(\epsilon, \epsilon)$. For any class $\cal{C}$ of languages, define
$$
E_{lin}[\CC] := \set{L~|~{\rm~for~some~} \rho {\rm~with~} \theta_{\rho} \in \CC,
{\rm~and~} c > 0, L = E_{cn}(\rho)}.
$$
Now define $\Sklin{0} = \Pklin{0} = \DLIN$, the class of languages accepted
in linear time by deterministic multitape TMs, and for $k \geq 1$,
$\Sklin{k} = E_{lin}\left[\Pklin{k-1}\right], \Pklin{k} = {\rm co-}\Sklin{k}$.
Finally define
$$\LINH = \bigcup_{k = 1}^{\infty}\Sklin{k}.$$
\begin{proposition}
Let $\NLIN$ denote the class of languages accepted in linear time by
{\em nondeterministic} multitape Turing Machines. Then $\Sklin{1} = \NLIN$.
\end{proposition}
\proof
By definition, $\Sklin{1} = E_{lin}[\DLIN]$. Therefore, we will prove that
$E_{lin}(\DLIN) = \NLIN$.
\bigskip
\noindent
$\supseteq$ :
Let $L$ be a language in $\NLIN$, and let $N$ be a nondeterministic multitape
Turing Machine such that $L(N) = L$. The idea is to simulate $N$ by a
nondeterministic multitape Turing Machine $N'$ which behaves as follows:
on input $x$, $N'$ nondeterministically
writes {\em in advance} all the guesses made by $N$ on a fresh tape. Call this
guess string $y$. Then $N'$ begins to simulate $N$; whenever $N$ makes
a guess, $N'$ consults the string $y$ and continues its simulation of $N$.
The crucial points to note are: (a) since $N$ is a machine that runs in linear time,
the length of the guess string $y$ is at most $c|x|$ for some constant $c$,
and (b) after writing the guess string $y$, the behavior of $N'$ is completely
deterministic. It is easy to see that $N'$ accepts the language $L$.
To wit,
\begin{eqnarray}
x \in L(N') & \iff & (\exists y : |y| \leq c|x|)~N'
{\rm~accepts~} x {\rm~with~guess~string~} y \nonumber \\
& \iff & N {\rm~accepts~} x {\rm~with~the~same~
guesses~as~prescribed~by~} y \nonumber \\
& \iff & x \in L(N). \nonumber
\end{eqnarray}
\noindent
$\subseteq$ :
Let $L$ be a language in $E_{lin}[\DLIN]$ defined by a binary relation $\rho$
and a constant $c > 0$ such that
$x \in L \iff (\exists y : |y| \leq c|x|)~\rho(x,y)$ and
$\theta_{\rho} \in \DLIN$. Let $M$ be a deterministic linear time Turing
Machine such that $L(M) = \theta_{\rho}$, that is, $(x,y) \in L(M)$ iff
$|y| \leq c|x| \AND \rho(x,y)$.
A nondeterministic Turing Machine
$N$ such that $L(N) = L$ behaves as follows: on input $x$, $N$ guesses
a string $y$ of length $c|x|$ and simulates $M$ on $(x,y)$, and accepts
iff $M$ accepts. It is easy to see that $L(N) = L$. \qed
\bigskip
\noindent
{\it Notation:\/} Wrathall writes $\sigma_k$ for $\Sklin{k}$. We will use
$\NLIN[\CC]$ in place of $E_{lin}[\CC]$. Wrathall's $\NL(\CC)$ is the
same as our $\NLIN^{\CC}$, and denotes the class of languages accepted in
nondeterministic linear time with an oracle set from the class $\CC$.
We will use $\LINH[\CC]$ to denote $\NLIN[\CC] \cup \NLIN[{\rm co-}\NLIN[\CC]]
\cup \NLIN[{\rm co-}\NLIN[{\rm co-}\NLIN[\CC]]] \cup \ldots$, etc.
\bigskip
Note that taking complements (${\rm co-}\CC = \set{\tilde L | L \in \CC}$)
is a rudimentary operation, and $E_{lin} = $ (identify $x$ and $z$) $\circ$
(linear length bounded $\exists$). Hence
\begin{proposition}
For any class $\CC$, $\LINH[\CC]$ is contained in the closure of $\CC$ under
rudimentary operations.
\end{proposition}
\begin{corollary}
If $\DLIN \subseteq \RUD$, then $\LINH \subseteq \RUD$.
\end{corollary}
\noindent
So to prove Wrathall's theorem, it suffices to show $\RUD \subseteq \LINH$ and
$\DLIN \subseteq \RUD$.
For the second part, it turns out that it is easier to prove $\NLIN \subseteq \RUD$.
To answer the question we raised earlier about where $\RUD$ fits in the
Chomsky hierarchy, we will prove a chain of results, one of which is
$\RUD \subseteq \LINH$. Our main conceptual tool in the chain of proofs
is the alternating Turing Machine model of Chandra, Kozen and Stockmeyer
(see ``Structural Complexity Theory, Vol II'' by Balcazar, Diaz and Gabarro, for a
complete treatment of this concept). Let $\ATIME[t(n)]$ denote the class
of languages accepted by alternating Turing Machines (to be defined)
that run in time $t(n)$.
Our task can now be clearly specified as follows:
\begin{itemize}
\item [(1)] $\RUD \subseteq \LINH \subseteq \ATIME[O(n)] \subseteq \DSPACE[O(n)]$.
\item [(2)] $\NLIN \subseteq \RUD$.
\end{itemize}
Since $\DSPACE[O(n)]$ is exactly the class of languages accepted by deterministic
linear bounded automata, part (1) above lets us conclude that $\RUD = \cal{CSL}$,
the class of context-sensitive languages.
\section {Alternating Turing Machines}
An alternating TM $M$ has $Q$, its set of states, partitioned into
$Q_{\exists} \cup Q_{\forall} \cup Q_{\rm det}$. Technically, $Q_{\rm det}$
is only optional, but we will include it for clarity of exposition.
A configuration
$I = [v\Choose{q}{c}w]$ is {\em existential\/} if $q \in Q_{\exists}$,
and {\em universal\/} if $q \in Q_{\forall}$. Wlog. we may suppose that
$M$ has a unique accepting state $q_{\rm acc}$, and a unique rejecting
state $q_{\rm rej}$, which are halting states, and it is immaterial which one of
$Q_{\exists}$ and $Q_{\forall}$ they belong to. The transition function
$\delta_M$ is defined as for an NTM, but the definition of acceptance
is different. A halting configuration $[v\Choose{q_{\rm acc}}{~~c}w]$ is
{\em accepting\/}, and a halting configuration $[v\Choose{q_{\rm rej}}{~~c}w]$ is
{\em rejecting\/}. A non-halting configuration $[v\Choose{q}{c}w]$ with
$q \in Q_{\exists}$ is {\em accepting\/} if at least one of the next
configurations is accepting. A non-halting configuration $[v\Choose{q}{c}w]$ with
$q \in Q_{\forall}$ is {\em accepting\/} if {\em all\/} of the next
configurations are accepting. Finally, acceptance is defined by
$x \in L(M) \iff [\Choose{~s}{x_1}x_2 \ldots x_n]$ is accepting.
\bigskip
\noindent
{\bf Observations.\/}
\begin{enumerate}
\item Every NTM $N$ is an ATM with $Q_{\exists} = Q_N$.
\item If $L \in \NLIN$, then $\tilde{L}$ is accepted by an ATM with
only universal states in $O(n)$ time.
\end{enumerate}
\begin{definition}
For any computation path $\vec{c}$, define $\alt(\vec{c})$ to be the
number of alternations between $Q_{\exists}$ and $Q_{\forall}$ in $\vec{c}$.
\end{definition}
If $s \in Q_{\exists}$ and for every computation path $\vec{c}$ of $M$,
$\alt(\vec{c}) \leq k$,
then $M$ is called a $\Sigma_k$ machine.
If $s \in Q_{\forall}$ and for every computation path $\vec{c}$ of $M$,
$\alt(\vec{c}) \leq k$,
then $M$ is called a $\Pi_k$ machine.
\begin{definition}
The class $\Sigma_k{\mbox {\rm -TIME}}[t(n)]$ is defined to be the set of all
languages $L$ such that $L$ is accepted by a $\Sigma_k$ machine $M$.
The class $\Pi_k{\mbox {\rm -TIME}}[t(n)]$ is defined to be the set of all
languages $L$ such that $L$ is accepted by a $\Pi_k$ machine $M$.
\end{definition}
\begin{definition}
The class $\ATIME[t(n)]$ is defined to be the set of all languages $L$
such that $L$ is accepted by an ATM $M$ which runs in time $O(t(n))$ on inputs
of length $n$.
\end{definition}
\noindent
The following propositions are easy to prove.
\begin{proposition}
For every $k$, $\Sigma_k{\mbox {\rm -TIME}}[t(n)] \subseteq \ATIME[t(n)]$, and
the converse is not true.
\end{proposition}
\begin{proposition}
For every $k$, $\Sklin{k} = \Sigma_k{\mbox {\rm -TIME}}[O(n)]$ and
$\Pklin{k} = \Pi_k{\mbox {\rm -TIME}}[O(n)]$.
\end{proposition}
\begin{theorem}
$\ATIME[O(n)] \subseteq \DSPACE[O(n)]$.
\end{theorem}
\proof
Let $M$ be an ATM which runs in time $cn$ on inputs of length $n$. We
may assume wlog. that $M$ has binary branching on its existential and
universal states.
We will build a
deterministic TM $M'$ that runs in $\DSPACE[O(n)]$ and simulates a
left-to-right evaluation of the computation tree of $M$ on any given
input $x$. In addition to the work tapes of $M$, $M'$ maintains an
extra tape that contains pairs from the set
$\set{
\langle \exists, 0 \rangle,
\langle \exists, 1 \rangle,
\langle \forall, 0 \rangle,
\langle \forall, 1 \rangle}$.
$M'$ performs a depth-first, left-to-right evaluation of the computation
tree of $M$.
At each point during the simulation, the extra tape of $M'$
contains information about
the states encountered in the current computation path of $M$.
$M'$ has a way of remembering in its internal control the following information:
\begin{enumerate}
\item whether it has already evaluated the left branch of a state
\item whether it can skip the right branch of a state
\end{enumerate}
Whenever $M'$ moves up the computation tree, it ``replays'' the computation
sequence from the initial configuration upto and including the current
node. $M'$ accepts iff $M$ accepts (according to the definition of
acceptance for an ATM).
Since $M$ runs in time $O(n)$, the work tapes of $M$ never grow beyond
length $O(n)$. It remains, therefore, to prove that the extra tape of
$M'$ never grows beyond $O(n)$ length. This follows from the fact that
no computation path of $M$ is longer than $O(n)$ steps. \qed
\begin{theorem}
$\RUD \subseteq \LINH$.
\end{theorem}
\proof
We will prove this by induction on the structure of rudimentary
relations.
\bigskip
\noindent
{\it Basis.\/}
\begin{itemize}
\item [(0)]
If $\rho$ is rational, there is a $k$-tape NFA which accepts $\theta_{\rho}$.
Since a nondeterministic linear time TM can easily simulate a $k$-tape NFA for
any fixed $k$, $\theta_{\rho} \in \NLIN$.
\end{itemize}
\bigskip
\noindent
{\it Induction.\/}
\begin{itemize}
\item [(1a)]
$\rho = \sigma \cup \tau$. By induction hypothesis, there
is a $k$ such that $\theta_{\sigma} \in \Sklin{k} \AND
\theta_{\tau} \in \Sklin{k}$ via $\Sklin{k}$ machines $M_{\sigma}$ and
$M_{\tau}$, both of which have existential states $s_{\sigma}$ and
$s_{\tau}$ as their start states.
Define $M_{\rho}$ to be an ATM which begins with an existential state
$s$ with two branches---one leading to $s_{\sigma}$ and the other to
$s_{\tau}$. Since $M_{\sigma}$ and $M_{\tau}$ are both $\Sklin{k}$ machines,
all computation paths from $s_{\sigma}$ and $s_{\tau}$ have at most
$k$ alternation of existential and universal states. Since
$s_{\sigma}$ and $s_{\tau}$ are both existential states,
any path of $M$ still has $k$ or fewer alternation of
existential and universal states. In other words, $M_{\rho}$ is also
a $\Sklin{k}$ machine, and it is easy to see that $L(M_{\rho}) = \theta_\rho$.
\item [(1b)]
$\rho = \sigma \cap \tau$. By induction hypothesis, there
is a $k$ such that $\theta_{\sigma} \in \Sklin{k} \AND
\theta_{\tau} \in \Sklin{k}$ via $\Sklin{k}$ machines $M_{\sigma}$ and
$M_{\tau}$, both of which have existential states $s_{\sigma}$ and
$s_{\tau}$ as their start states.
Define $M_{\rho}$ to be an ATM which begins with a universal state
$s$ with two branches---one leading to $s_{\sigma}$ and the other to
$s_{\tau}$. Since $M_{\sigma}$ and $M_{\tau}$ are both $\Sklin{k}$ machines,
all computation paths from $s_{\sigma}$ and $s_{\tau}$ have at most
$k$ alternation of existential and universal states. Since
$s_{\sigma}$ and $s_{\tau}$ are both existential states,
any path of $M$ still has $k+1$ or fewer alternation of
existential and universal states. In other words, $M_{\rho}$ is a
$\Pklin{k}$ machine, and it is easy to see that $L(M_{\rho}) = \theta_\rho$.
The above proof is a ``lazy proof''---a less lazy proof would be to prove
that $\Sklin{k}$ is closed under intersection.
\item[(1c)]
$\rho = \tilde{~}\sigma$. By induction hypothesis, there
is a $k$ such that $\theta_{\sigma} \in \Sklin{k}$
via a $\Sklin{k}$ machines $M_{\sigma}$ which has an existential
state $s_{\sigma}$ as its start state. By interchanging the
accepting and rejecting states and swapping $Q_{\exists}$ with
$Q_{\forall}$, we get a $\Pklin{k}$ machine $M_{\rho}$ such that
$L(M_{\rho}) = \theta_{\rho}$.
\item[(2a)]
(Permutation of indices) \\
Wlog. we may suppose that
$\rho(x_1,x_2,\ldots,x_k) = \sigma(x_2,x_1,\ldots,x_k)$.
By appropriately relabelling the tapes of a $\Sigma_k$
machine $M_{\sigma}$ that
accepts $\theta_{\sigma}$, we can get a $\Sigma_k$ machine $M_{\rho}$
that accepts $\theta_{\rho}$.
\item[(2b)]
(Adding a dummy index)
$\rho(x_1,x_2,\ldots,x_k) = \sigma(x_2,x_1,\ldots,x_{k-1})$.
Obvious.
\item[(2c)]
(Instantiate a component)
$\rho(x_1,x_2,\ldots,x_k) = \sigma(x_2,x_1,\ldots,x_{k-1},w)$.
Modify $M_{\sigma}$ to do the following: on input $(x_1,\ldots,x_{k-1})$,
deterministically append $w$ in time at most $2(|(x_1,\ldots,x_{k-1})| + |w|)$,
and simulate $M_{\sigma}$.
\item[(2d)]
(Identify two variables)
Similar to instantiation, only this time $M_{\sigma}$ is re-programmed to
make an extra copy a component of its input.
\item[(3)]
(Bounded existential quantification) \\
$\rho(x_1,x_2,\ldots,x_{k-1},z) = (\exists x_k : |x_k| \leq d|z|)
\sigma(x_1,x_2,\ldots,x_{k-1},y)$.
Given a $\Sigma_k$ machine $M_{\sigma}$, we construct $M_{\rho}$ as
follows: on input $(x_1,x_2,\ldots,x_{k-1},z)$,
$M_{\rho}$ existentially ``generates''
all strings $y$ of length at most $d|z|$ and simulates $M_{\sigma}$
on $(x_1,x_2,\ldots,x_{k-1},y)$ on each of the leaves of the
binary tree that generates all these strings. Observe that all nodes
in this binary tree are existential states, and therefore, every
computation path of $M_{\rho}$ on $(x_1,x_2,\ldots,x_{k-1},z)$
has no more than $k$ alternations, that is, $M_{\rho}$ is a $\Sigma_k$
machine.
\end{itemize}
\noindent
This completes the inductive step. By induction, we conclude that
$\RUD \subseteq \LINH$. \qed
\begin{corollary}
$\RUD \subseteq \LINH \subseteq \ATIME[O(n)] \subseteq \DSPACE[O(n)]$.
\end{corollary}
\begin{corollary}
For any class $\CC$, the closure of $\CC$ under rudimentary operations
contains $\LINH[\CC]$.
\end{corollary}
\begin{theorem}
$\NLIN \subseteq \RUD$.
\end{theorem}
\proof
Let $N$ be an NTM which runs in time $cn$ and accepts a language $A$.
Let $\alpha = \{(x,y)~|~y \in \set{L,R,S}^*$ and $y$ encodes
the input head movements of $N(x)$, and $N(x)$ accepts $\}$.
Let $A' = \theta_{\alpha}$.
We claim that $A' \in \NTIME[n]$. An NTM for $A'$ would first extract
$x$ from $(x,y)$, then simulate $N(x)$ and verify that
$y$ correctly encodes the head movements of $N(x)$. Furthermore, $N'$
is {\em real time\/}---it reads one character of the input at each step.
Now,
$$
\forall x : x \in A \iff (\exists y : |y| \leq c|x|)~(x,y) \in \alpha.
$$
In other words, $A' \in \RUD \implies A \in \RUD$. Hence to prove the
theorem, it suffices to prove that $A' \in RUD$.
Note that if $N'$ has $k$ work tapes, it can be simulated in real time by
an NTM $N''$ which has $2k$ stacks. It follows from the lemma below
that $L(N'') \in \RUD$,
completing the proof of Wrathall's theorem. \qed
\begin{lemma}[\cite{GrHo69}]
There are $2k$-many CFL's $B_1,\ldots,B_{2k}$ over some alphabet $\Delta$
and a length-preserving homomorphism $h : \Delta \into \Sigma^*$ such
that $L(N'') = h(B_1 \cap B_2 \cap \cdots B_{2k})$.
\end{lemma}
\proofsketch
Let $\Delta = $ dominoes of the form
$[p,c_0,c_1,\ldots,c_{2k},A_1,\ldots,A_{2k},q] \in \delta_{N''}$.
Assume that the input head always moves right and that $N$ makes no
$\epsilon$-moves. The character $c_i, i \geq 1$ stands for the character on
the $i$-th work tape of $N''$, $c_0$ stands for the character scanned on
the input tape, and the $A_i$'s stand for the action performed on the
work tapes. Call a chain of dominoes {\em consistent on tape $j$\/} if
they match and for any pair
$[p,c_0,c_1,\ldots,c_{2k},A_1,\ldots,A_{2k},q],
[q,d_0,d_1,\ldots,d_{2k},A_1',\ldots,A_{2k}',r]$,
$d_j$ is what $N''$ sees on tape $j$ after action $A_j$ on $c_j$.
Define
$B_j = \{$ chains consistent on tape $j$ and which end in an accepting
state $\}$, and define $h([p,c_0,c_1,\ldots,c_{2k},A_1,\ldots,A_{2k},q]) = c_0$.
Clearly, each of the $B_j$'s is a CFL since the tapes are stack-restricted.
The lemma follows from the observation that
$x \in L(N'') \iff x \in B_1 \AND x \in B_2 \AND \ldots \AND x \in B_{2k}$. \qed
%\lecture{**LECTURE-NUMBER**}{**DATE**}{**LECTURER**}{**SCRIBE**}
% \lecture{33--34}{November 22,29}{K.W. Regan}{D. Sivakumar}
% **** YOUR NOTES GO HERE:
\section{Star-free Regular Languages}
[Lectures 33--34, scribed by Sivakumar.]
\begin{definition}
A {\em star-free regular expression\/} is defined inductively by the
following grammar:
\begin{itemize}
\item [] {\em Basis.\/} $E \into {\mbox \O} ~|~ \epsilon ~|~ c$
(for all $c \in \Sigma^*$).
\item [] {\em Induction.\/} $E \into (E \cup E) ~|~ (E \cap E) ~|~
(\tilde{~}E) ~|~ (E \cdot E)$.
\end{itemize}
Any language $L(\alpha)$ of a star-free regular expression $\alpha$
is a {\em star-free regular language\/}.
\end{definition}
\bigskip
\noindent
{\bf Examples.}
\begin{enumerate}
\item $\Sigma^* = \tilde{~}{\mbox \O}$.
\item $(c_1 \cup c_2 \cup \ldots \cup c_k)^* =
\tilde{~}((\Sigma^*)\cdot(c_{k+1} \cup \ldots \cup c_n)(\Sigma^*))$.
\item $(ab)^* = [\tilde{~}(a \cup b \cup
(\tilde{~}{\mbox \O})aa(\tilde{~}{\mbox \O}) \cup
(\tilde{~}{\mbox \O})bb(\tilde{~}{\mbox \O})) \cap
((a(\tilde{~}{\mbox \O})b) \cup \epsilon)]$.
\end{enumerate}
\noindent
The basic idea is that we can't have regular expressions of the form
$(aa)^*$ or $(aaa)^*$---in other words, {\em modular counting is
disallowed\/}. Star-free regular expressions are the central
subject of study for the monograph {\em Counter-free Automata\/}
by McNaughton and Papert (1971). In this monograph, McNaughton and
Papert characterize the class of star-free regular languages in a
number of interesting ways, two of which we will study. One of these
characterizations, due to M.P.Sch\"utzenberger, is in terms of the
{\em monoid of transformations\/} of the minimum-state DFA for the
regular set. To understand this clearly, we provide below some
definitions, which are standard in abstract algebra (see
Birkhoff and Bartee (1970), or Ross and Wright (1991) for better
treatments).
\begin{definition}
A {\em monoid\/} $(S,\circ)$ is a set $S$ with a binary
operation $\circ$ which satisfies
\begin{enumerate}
% \item {\em Closure.\/} $(\forall x,y \in S)~x \circ y \in S$.
\item [(1)] {\em Associativity.\/} $(\forall x,y,z \in S)~
x \circ (y \circ z) = (x \circ y) \circ z$.
\item [(2)] {\em Identity.\/} $(\exists e \in S)~(\forall x \in S)~
x \circ e = e \circ x = x$.
\end{enumerate}
\end{definition}
\begin{definition}
A {\em group\/} is a monoid $(S,\circ)$ which satisfies
\begin{enumerate}
\item [(3)] {\em Existence of inverses.\/}
$(\forall x \in S)~(\exists x^{-1} \in S)~
x \circ x^{-1} = x^{-1} \circ x = e$, where $e$ is the
identity element of the monoid.
\end{enumerate}
\end{definition}
\begin{definition}
A {\em sub-monoid\/} of a monoid $(S,\circ)$ is a subset
$T \subseteq S$ which satisfies
\begin{enumerate}
\item [(1)] $e \in T$, where $e$ denotes the identity of the monoid $(S,\circ)$.
\item [(2)] $(\forall x,y \in S)~x,y \in T \implies x \circ y \in T$.
\end{enumerate}
\end{definition}
\begin{definition}
A monoid $(S,\circ)$ is said to be {\em aperiodic\/} if no
sub-monoid of $(S,\circ)$ forms a non-trivial group (the
set $\set{e}$ is referred to as the trivial group).
\end{definition}
\bigskip
\noindent
For any DFA $M$ over an alphabet $\Sigma$, let $\phi_c$ denote the
mapping of states induced by the character $c \in \Sigma$, that is,
$\phi_c : Q \into Q$ is defined by $\phi_c(p) = q$ if $\delta_M(p,c) = q$.
Let $\CM$ denote the closure of the set $\set{\phi_c~|~c \in
(\Sigma \cup \epsilon)}$ under
$\circ$ (composition of mappings).
The following proposition is elementary.
\begin{proposition}
$(\CM,\circ)$ is a monoid (called the {\em monoid of transformations\/} of $M$).
\end{proposition}
\noindent
Finally, here is the promised theorem:
\begin{theorem}\label{starfree}
The following are equivalent:
\begin{enumerate}
\item [(1)] $A$ is a star-free regular language.
\item [(2)] $A$ is definable in the McNaughton-Immerman formal system
with $0,{\bf N},Z(i),=,\leq$ only.
\item [(3)] The monoid of transformations $(\CM,\circ)$ of
the minimum-state DFA for $A$ is aperiodic.
\end{enumerate}
\end{theorem}
\bigskip
\noindent
As an application of Theorem \ref{starfree}, we will now show that
the regular language $L_1 = (aa)^*$ is not star-free. The following is
a minimum-state DFA for $L_1$.
\vspace{3in}
\noindent
The monoid elements $\phi_{\epsilon} = {\mbox{\rm ID}}$ and
$\phi_a =
\left( \begin{array}{ccc}
1 & 2 & 3 \\
2 & 1 & 3
\end{array} \right)$
form a group that is isomorphic to $S_2$, the symmetric group on
two elements.
Next consider the regular language $L_2 = (ab)^*$, whose minimum-state
DFA is given above.
\noindent
The monoid elements are as follows:
\begin{itemize}
\item []
$\phi_{\epsilon} = {\mbox{\rm ID}}$,
\item []
$\phi_a =
\left( \begin{array}{ccc}
1 & 2 & 3 \\
2 & 3 & 3
\end{array} \right)$,
$\phi_b =
\left( \begin{array}{ccc}
1 & 2 & 3 \\
3 & 1 & 3
\end{array} \right)$,
\item []
$\phi_{ab} = \phi_b \circ \phi_a =
\left( \begin{array}{ccc}
1 & 2 & 3 \\
1 & 3 & 3
\end{array} \right)$,
$\phi_{ba} = \phi_a \circ \phi_b =
\left( \begin{array}{ccc}
1 & 2 & 3 \\
3 & 2 & 3
\end{array} \right)$,
\item []
$\phi_{aa} = \phi_a \circ \phi_a =
\left( \begin{array}{ccc}
1 & 2 & 3 \\
3 & 3 & 3
\end{array} \right) = d$ (the ``dead'' mapping),
\item []
$\phi_{bb} = \phi_b \circ \phi_b =
\left( \begin{array}{ccc}
1 & 2 & 3 \\
3 & 3 & 3
\end{array} \right) = d$,
\item []
$d \circ ({\mbox any}) = ({\mbox any}) \circ d = d$,
\item []
$\phi_{ab} \circ \phi_a = \phi_{ab} \circ \phi_b = \phi_b \circ \phi_{ab} = d$,
\item []
$\phi_a \circ \phi_{ba} = \phi_{ba} \circ \phi_b = d$,
\item []
$\phi_{ab} \circ \phi_{ba} = \phi_{ba} \circ \phi_{ab} = d$,
\item []
$\phi_a \circ \phi_{ab} = \phi_{ba} \circ \phi_a = \phi_a$,
\item []
$\phi_b \circ \phi_{ba} = \phi_{ab} \circ \phi_b = \phi_b$.
\end{itemize}
\noindent
Upon careful inspection, we conclude that the monoid of transformations
listed above does not have any sub-monoid that forms a non-trivial
group. Intuitively, the reason why $(ab)^*$ is star-free while
$(aa)^*$ is not is that the latter attempts to ``count'' (modulo 2)
the number of $a$'s, while the former does not. By the same token,
it is easy to observe that $(abab)^*$ is not star-free since it
``counts'' (modulo 2) the pattern $ab$.
\noindent
Here are some more examples of regular languages that are not
star-free:
\begin{enumerate}
\item $L_1 := \set{x~|~|x| {\rm~is~even}}$.
\item $L_2 := \{x \in \set{0,1}^* ~|~ x~$ has exactly two 1's and the
first 1 occurs in an odd position $\}$. (The set $\set{{\mbox {\rm ID}},\phi_0}$
is isomorphic to $S_2$.)
\item $L_3 := L_2 \cap \{x~|~$ the last 1 in $x$ occurs in an even
position $\}$. (Once again, $\set{{\mbox {\rm ID}},\phi_0}$ is isomorphic
to $S_2$.)
\end{enumerate}
\section{Closure properties of Star-free Languages}
Let $\SF$ denote the class of all star-free regular languages.
We will show that $\SF$ is not closed under 1:1 homomorphisms.
To see this, consider the language $L_1 = (ab)^*$ over $\Sigma = \set{a,b}$.
We know that $L_1 \in \SF$; taking $h:\Sigma \into \Sigma^*$ to be
the homomorphism defined by $h(a) = h(b) = a$, we get $L_2 = h(L_1)$ to
be the language $(aa)^*$, which we know is not star-free.
Next we will prove a useful lemma about star-free languages that we will
use later to characterize the monoid of transformations of star-free
languages.
\begin{lemma}
For any language $B \subseteq \Sigma^*$ and $c \in \Sigma$, let
$B_c := \set{x~|~cx \in B}$. If $B \in \SF$, then $B_c \in \SF$.
\end{lemma}
\proof
We will prove this by induction on the structure of star-free
regular expressions.
\bigskip
\noindent
{\it Basis.\/}
\begin{itemize}
\item [(0)] If $B$ is either ${\mbox \O}$ or $\epsilon$,
then $B_c$ is ${\mbox \O}$ or $\epsilon$, respectively.
\end{itemize}
\noindent
{\it Induction.\/}
\begin{itemize}
\item [(1)]
$B = B_1 \cup B_2$. $B_c = (B_1)_c \cup (B_2)_c$. By induction
hypothesis applied to $B_1$ and $B_2$, and by the closure of $\SF$
under $\cup$, we conclude that $B_c \in \SF$.
\item [(2)]
$B = B_1 \cap B_2$. $B_c = (B_1)_c \cap (B_2)_c$. By induction
hypothesis applied to $B_1$ and $B_2$, and by the closure of $\SF$
under $\cap$, we conclude that $B_c \in \SF$.
\item [(3)]
$B = D \cdot A$.
\begin{eqnarray}
B_c & = & \set{x~|~cx \in D \cdot A} \nonumber \\
& = & \set{x~|~(\exists y,z)~x = yz \AND cy \in D \AND z \in A} \cup
\set{x~|~\epsilon \in D \AND cx \in A} \nonumber
\end{eqnarray}
If $\epsilon \not \in D$, then $B_c = D_c \cdot A$; if
$\epsilon \in D$, then $B_c = D_c \cdot A \cup A_c$. Either way, by
induction hypothesis applied to $D$ and $A$, $B_c \in \SF$.
\item [(4)]
$B = \tilde{~}D$.
\begin{eqnarray}
B_c & = & \set{x~|~cx \not \in D} \nonumber \\
& = & \tilde{~} \set{x~|~cx \in D} \nonumber \\
& = & \tilde{~} (D_c) \nonumber
\end{eqnarray}
By induction hypothesis applied to $D$ and the closure of $\SF$ under
complementation, we conclude that $B_c \in \SF$.
\end{itemize}
This completes the induction step, and by induction, we have
that $B \in \SF \implies B_c \in \SF$. \qed
%\lecture{**LECTURE-NUMBER**}{**DATE**}{**LECTURER**}{**SCRIBE**}
% \lecture{35}{December 1st}{K.W. Regan}{Debra Burhans and Kannan Govindarajan}
\subsection{An Instructive Example}
[Lecture 35, scribed by Burhans and Govindarajan.]
\medskip
\begin{claim}
Let $L(M) = (0+1)(00)^*$. There is no *-free expression for L.
\end{claim}
\begin{proof}
Suppose $L \in \SF$, $L_1$ = \{ x $|$ 1x $\in$ L \}. By the last theorem, $L_1 \in$
SF but $L_1$ = $(00)^*$ which is known not to be SF, so $L_1$'s syntactic monoid
is not aperiodic.
\end{proof}
\begin{theorem}
Let M be the minimum state DFA for a language L. Let ${\cal M}$ be the monoid
of transformations of M. The states of M are in 1-1 correspondence with the
equivalence classes under the relation $x \sim_1 y ~ \equiv ~ (\forall v, xv \in L \leftrightarrow yv \in L)$.
And the elements of ${\cal M}$ are in 1-1 correspondence with the equivalence
classes under $x \sim_2 y ~ \equiv ~ (\forall u,v) uxv \in L \leftrightarrow uyv \in L$.
\end{theorem}
\paragraph{Idea behind proof:} In one direction, suppose x,y are such that
$\forall$ states p,
\begin{center}
$\delta_M^*(p,x) = \delta_M^*(p,y)$
\end{center}
This means that $\phi_x$ and $\phi_y$ when interpreted as mapping states to
states are in the same equivalence class of functions. In M in the above
example, there are 4 equivalence classes under the relation $\sim_1$ corresponding
to the four states of the minimum state DFA. But there are 6 equivalence classes
under the relation $\sim_2$. These are:
\begin{enumerate}
\item $\phi_\epsilon$.
\item $\phi_0$.
\item $\phi_1$.
\item $\phi_{00}$.
\item $\phi_{10}$.
\item $\phi_{dead}$, where $dead$ is any string not in $10^* \cup 0^*$.
\end{enumerate}
\begin{table}[hbt]
\begin{center}
\begin{tabular}{||r|r||r|r|r|r|r|r||} \hline
& & & & & & & \\
& & $\epsilon$ &0 &1 &00 &10 & dead \\ \hline \hline
[
$
\left( \begin{array}{cccc}
1 & 2 & 3 & 4 \\
1 & 2 & 3 & 4
\end{array} \right)
$
]
&
$\epsilon$ &$\epsilon$ &0 &1 &00 &10& dead \\ \hline
[
$
\left( \begin{array}{cccc}
1 & 2 & 3 & 4 \\
2 & 3 & 2 & 4
\end{array} \right)
$
]
&0 & 0 & 00 & dead &0 &dead &dead \\ \hline
[
$
\left( \begin{array}{cccc}
1 & 2 & 3 & 4 \\
2 & 4 & 4 & 4
\end{array} \right)
$
]
&1 & 1 &10 &dead &1 &dead &dead \\ \hline
[
$
\left( \begin{array}{cccc}
1 & 2 & 3 & 4 \\
3 & 2 & 3 & 4
\end{array} \right)
$
]
& 00 &00 &0 &dead &00 &dead &dead \\ \hline
[
$
\left( \begin{array}{cccc}
1 & 2 & 3 & 4 \\
3 & 4 & 4 & 4
\end{array} \right)
$
]
& 10 & 10 & 1 &dead &10 &dead &dead \\ \hline
[
$
\left( \begin{array}{cccc}
1 & 2 & 3 & 4 \\
4 & 4 & 4 & 4
\end{array} \right)
$
]
&dead & dead &dead & dead & dead & dead &dead \\ \hline
\end{tabular}
\end{center}
\caption{Multiplication table of the equivalence classes under $\sim_2$}
\label{tbl:mult}
\end{table}
Choose the elements 0 and 00 and rename them as a and e, and look
at the multiplication table restricted to a and e. It looks as follows.
\begin{enumerate}
\item aa = e.
\item ae = a.
\item ea = a.
\item ee = e.
\end{enumerate}
Therefore the two elements a and e form a sub-group with the identity element being e.
\paragraph{Eilenberg's condition:}
A monoid ${\cal M}$ contains no non-trivial group if and only if $\exists$ t
such that $\forall a \in {\cal M}, ~ a^{t+1} = a^t$.
\begin{corollary}
Every finite monoid ${\cal M}$ has the property that $\exists q \exists t \forall a \in {\cal M} ~ ~a^{t+q}=a^t$.
\end{corollary}
\begin{corollary}
SF is not closed under forward 1:1 homomorphisms \footnote{As a matter of fact nor under inverse 1:1 homomorphisms.}
\end{corollary}
\begin{proof}
Consider the forward 1:1 homomorphism:
h(a) = a.\\
h(b) = a.\\
h($(ab)^*$) = $(aa)^*$.
Therefore SF is not closed under forward 1:1 homomorphisms.
\end{proof}
\paragraph{Research Problems:}
\begin{enumerate}
\item What is the closure of SF under homomorphisms?
\item What is the closure of SF under d:e generalized homomorphisms.
\end{enumerate}
Is the answer to any/both of the above two questions all regular languages?
\begin{lemma}
Every language in SF can be generated by
\begin{center}
$E \rightarrow ~ \phi ~ | ~ \epsilon ~ | ~ c ~ | ~ (E \cup E) ~ | ~ ( \sim E ) ~| ~ E d E$
\end{center}
\end{lemma}
\begin{proof}
The only case that needs checking is C = AB, where A,B $\in$ SF.
But
\begin{eqnarray*}
B & = & [\bigcup_{c \in \Sigma} c.B_c], so \\ \nonumber
A\cdot B & = & [\bigcup_{c \in \Sigma} A.c.B_c.]\\ \nonumber
\end{eqnarray*}
\end{proof}
%\lecture{**LECTURE-NUMBER**}{**DATE**}{**LECTURER**}{**SCRIBE**}
% \lecture{36}{December 3rd}{K.W. Regan}{Debra Burhans and Kannan
% Govindarajan}
\section{The Equivalence of SF and FOL}
[Lectures 36--37, scribed by Burhans and Govindarajan.]
\begin{definition}
For strings $z_0, \ldots, z_k$ over $\Sigma$ of the same length N, let
$$ denote their shuffle, and let $[z_0, \ldots, z_k]$
denote their shuffle as a word of length N over the alphabet
$\Sigma^{k+1}$.
$$ can be represented as a $k + 1 \times N$
matrix as follows:
\begin{center}
\[ \left( \begin{array}{c}
z_{00}~ z_{01}~ \ldots ~ z_{0N-1}\\
z_{10}~ z_{11}~ \ldots ~ z_{1N-1}\\
\vdots\\
z_{k0}~ z_{k1}~ \ldots ~ z_{kN-1}
\end{array} \right) \]
\end{center}
$[z_0, \ldots, z_k]$ can then be thought of as the column vectors of this
matrix:
\begin{center}
\[ [z_0, \ldots, z_k] = \left( \begin{array}{c}
z_{00} \\ z_{10} \\ \vdots \\ z_{k0}
\end{array} \right)
\left( \begin{array}{c}
z_{01} \\ z_{11} \\ \vdots \\ z_{k1}
\end{array} \right)
\ldots
\left( \begin{array}{c}
z_{0N-1} \\ z_{1N-1} \\ \vdots \\ z_{kN-1}
\end{array} \right) \]
\end{center}
\end{definition}
\begin{definition}
Every formula $\phi$ in FOL (as in Barrington, McNaughton, et al) with free
variables $\underline{i_1}, \ldots, \underline{i_k}$ defines the relation:
\begin{center}
$\{(x, i_1, \ldots, i_k) : x \models \phi (\underline{i_1}, \ldots, \underline{i_k})\}$
\end{center}
\end{definition}
\begin{theorem}
If A $\in$ SF then the relation $substr_A = \set{ : x_i, \ldots,
x_{j-1} \in A }$ is definable by a FOL formula $\sigma_A$(i,j), i.e., the
SF languages are FO representable.
\end{theorem}
\paragraph{Notes:} The proof is based on Barrington's but has been
simplified by making the following changes:
\begin{itemize}
\item Instead of the $prefix_A \equiv \phi$ (\_ ,j) and $suffix_A \equiv$
$\phi$ (j,\_ ) relations, the $substr_A$ relation defined above is used.
\item Binary numbers i are represented in unary notation as $0^{i-1}10^{N-1-i}$.
\end{itemize}
\paragraph{Note for purists:}
Since the following representations are equivalent, they are used
interchangeably in the text:
\begin{itemize}
\item $i = 0 \equiv \forall i ~~ i \leq j$
\item $i = N \equiv \forall i ~~ j \leq i$
\item $i = 1 \equiv \forall j ~~ j = 0 ~ \vee ~ i \leq j$
\item $i \neq j \equiv \neg (i = j)$
\item $i = j + 1 \equiv \forall k ~~ \neg ((i < k)~ \wedge ~
(k < j)) ~ \wedge ~ (i < j) $
\end{itemize}
\begin{proof}\\
Proof is by induction on the structure of a SF expression.\\
\noindent{\bf Basis}\\
\begin{tabular}{l l l l l}
& & \underline{$\sigma_A$} & & \underline{$\phi_A$}\\
& & & & \\
$A = \emptyset$ & & $(i \neq i) \wedge (j \neq j)$ & & $(0 \neq 0)$\\
$A = \set{\epsilon}$ & & $i = j$ & & $N = 0$ \\
$A = \set{c}$ & & $(j = i + 1) ~ \wedge ~ (z(i) = c)$ & & $(N = 1) ~ \wedge$
\end{tabular}
\noindent{\bf Induction}\\
\begin{tabular}{l l l l l}
& & \underline{$\sigma_A$} & & \underline{$\phi_A$}\\
& & & & \\
$A = B \cup C$ & & $\sigma_B \vee \sigma_C$ & & $\phi_B \cup \phi_C$ \\
$A = \sim B$ & & $ \sim \sigma_B $ & & $\sim \phi_B$ \\
\vspace{5 mm}
\end{tabular}\\
Finally, for the case $A = B.C$ we need to define \\
\centerline {$\set{ : x_i, \ldots, x_{j-1} ~ \in ~ B.C}$
$~ \Leftrightarrow ~(\exists k ~ (x_i, \ldots, x_{k-1}) \in B ~ \wedge ~
(x_k, \ldots, x_{j-1}) \in C)$} \\
\noindent So,
\begin{eqnarray*}
\sigma_A & := & \exists k ~ \sigma_B (i, k) \wedge \sigma_C (k, j) \wedge (i
\leq k) \wedge (k \leq j) \\ \nonumber
\phi_A & := & \exists k ~ \sigma_B(0, k) \wedge \sigma_C(k,N) \wedge (0 \leq k)
\wedge (k \leq N)\\
\end{eqnarray*}
\paragraph{Note:}Numbering from 0 and using substr
seems to avoid Barrington's use of ``E
$\rightarrow$ EdE''
\end{proof}
\paragraph{Question:}
What is the effect of agglutination of alphabet characters in SF languages?
\paragraph{Note from KWR:}
Lecture 37, on Monday, December 6, was on the proof of
$\FOL \subseteq \SF$. I gave an outline of the proof.
The main idea is: Given a formula $\phi$ of FOL, we may
suppose $\phi$ is in {\em prenex normal form\/}; i.e.,
with a ``quantifier block'' followed by a ``matrix''
of atomic predicates connected by Boolean operations but
without quantifiers.
First let $u_1,\dots,u_m$ be all the variables in the
matrix, and work with the ``agglutinated alphabet''
$\Gamma_m = \set{0,1}^{m+1}$.
The first place corresponds to the string $x$.
Values of variables in the other places
are represented in {\em unary\/} notation;
for instance, the number $i$ corresponds to the string
$0^i 1 0^{n-1-i}$.
The first part, done in class, is to show that
each of the atomic predicates $Z(u)$, $u = v$, and
$u < v$, with the appropriate extensions using $m-1$ or $m$
``dummy variables,''
is definable by a *-free expression over $\Gamma_m$.
Hence so is the entire matrix, since Boolean operations
are simulated directly by *-free operations.
Now we have to add-in the quantifiers one-by-one,
stepping down $\Gamma_m$ to $\Gamma_{m-1}$ each time.
(We can order the variables so that the place quantified
is always the last free place.)
Because we have negation it suffices to consider
an intermediate stage $\psi = (\exists u_k)\eta$,
where $\eta$ has free variables $u_1,\dots,u_k$, and
by the induction hypothesis,
there is a *-free expression $\alpha$ for
$\eta$ over $\Gamma_k$.
The goal is to find a *-free expression $\beta$ for
$\psi$ over $\Gamma_{k-1}$. The method is to
let $M_{\alpha}$ be the unique minimum-state DFA for $\alpha$,
and since we use unary encodings, to observe that
every accepting computation by $M_{\alpha}$
has exactly one transition where it reads a `1' in the
last place. The remainder of this proof is the first
problem on the take-home final.
Reason carefully about properties a {\em minimum-state\/}
DFA must have. Be sure that in addition to
proving the key ``$L_{pq}$ lemma,'' you explain how it
fits into finishing this proof.
\section{``Random-Access'' TMs and Sub-Linear Time}
[Lecture 38, prepared by Regan.]
\bigskip
A {\em random-access Turing machine\/} (RAM-TM)
is just like an ordinary Turing machine with an input tape
and some number $k \geq 2$ of worktapes, except that it
has no input tape head. Instead, the first worktape
(called tape~1) holds a ``pointer'' to the input tape,
whose address is governed by the current contents of tape~1.
We make the convention that tape~1 holds a binary number
written with the {\em least\/} significant bit first,
not counting a left endmarker $\wedge$ in cell 0 and a
right endmarker $\$$ that may be present.
(In class I said ``...most significant bit first,'' but
least is better, although if leading 0s are tolerated
in addresses then it doesn't matter.)
The syntax for transitions is exactly the same, and the
only difference in semantics is that the input symbol $c_0$
is taken from the addressed input tape cell.
Allender and Gore \cite{AlGo91b} use the convention that
tape~1 inititally holds the length $n$ of the input in
binary notation (or since we number from 0, give it $n-1$).
A natural restriction, which they seem not to adopt, is that
the address tape must always
hold a value between $0$ and $n$.
More popular is the convention that an ``address out of range''
returns `\$'; then it is possible to compute $n$
deterministically in $O(\log n)$ time by binary search.
There are also several differing conventions in how the
input tape itslef may be accessed:
\begin{itemize}
\item[(1)]
The input tape may only be polled when the RAM-TM is in a
special {\em input query state\/} $q_{?}$, whose formalism
is exactly the same as for an oracle query.
\item[(2)]
Same as (1), but with the draconian proviso that
on transit from state $q_{?}$, the address tape is
{\em entirely blanked out\/}.
\item[(3)]
The input tape is polled in each transition, using whatever
the address-tape holds even if $M$ is in the middle of
``loading'' the intended address from another tape.
\end{itemize}
A RAM-TM may be deterministic or nondeterministic, or even
{\em alternating\/}.
Indeed, the first paper to define the random-access mechanism
as such was titled ``Alternation'' \cite{CKS81}.
To define alternating RAM-TMs syntactically, all one needs
to do is partition the state set $Q$ into
$Q_{\exists}$, $Q_{\forall}$, and $Q_D$; also, the
deterministic part $Q_D$ can be divided arbitrarily between
$Q_{\exists}$ and $Q_{\forall}$ instead.
The semantics is the same.
\begin{example}\label{0*1*}
There is a deterministic $O(\log n)$ time RAM-TM $M$ such that
{\em if\/} the input $x$ belongs to
$\set{0^m1^k : m,k \geq 0}$, then $M$ can tell whether $m$ is odd
or even.
Under the convention which allows ``address out of range,''
the algorithm is to write $1$, $11$, $111$, $\dots$ on the
address tape until getting the `$\$$' response, and then
begin a binary search which looks for the break between 0s and 1s.
Note that if the input $x$ is not in $0^* 1^*$, then this
binary search can be deceived.
It is easy to show that the {\em language\/}
$A = \set{0^m1^k : m,k \geq 0, m \mbox{ is odd}}$
cannot be decided by an ATM without looking at all $n$ bits:
picture an ``Input Demon'' which is always poised to
foil you with a `1' or a `0' in the one bit of the input $x$
that you didn't examine if you prematurely announce
your decision about whether $x \in A$.
(Properties which require examining all the bits are termed
{\em elusive\/}, and there was some interest around 1980 in
classifying exactly
which graph properties are elusive---I believe
there's a conjecture which hasn't been solved yet.)
In class I ditzed around with trying to do the binary
search under the convention that $n-1$ is originally
given and ``addresses out of range'' are {\em streng verboten\/}.
This is a question for computational contortionists.
The {\em real point\/} of this example was intended to be that
having alternation quashes a lot of these difficulties.
I sketched ATMs which decide both the language $A$ and the
language $0^* 1^*$ itself.
\end{example}
An ATM $M$ running under convention (3) can be looked at this way:
The computation tree of $M$, which unfolds independently
of the input under (3), is really a {\em formula\/}.\footnote{
Technically, two branches of $M$ might come back together
in the same ID, and the computation graph need not even be
acyclic. But we can always give $M$ an extra worktape on which
it records the sequence of branchings, thus making every ID
unique to its path and making the computation graph a tree.
If the original $M$ runs in $O(\log n)$ time and space, so
does the new ATM.
}
An existential node in the tree is a binary $\OR$ in the formula,
and a universal node is an $\AND$.
After a given branch polls an input bit $x_i$ at its leaf,
it can only be one of four possible functions:
accept regardless of $x_i$, reject regardless of $x_i$,
accept iff $x_i = 1$, or accept iff $x_i = 0$.
These correspond to the four possible entries in a formula:
$1$, $0$, the variable $x_i$, or its negation $\neg x_i$,
respectively. The definition of $L(M)$ for an ATM is
the same as evaluating this formula on the particular
assignment ot the variables which the actual input
$x \in \set{0,1}^*$ represents.
The following lemma is helpful conceptually:
\begin{lemma}\label{niceATM}
An ATM $M$ which runs under convention (1) or (2)
in time $t(n)$ and space $s(n)$
can be simulated by an ATM $M'$ which runs under convention (3)
in time $3t(n)$ and space $s(n)$.
\end{lemma}
\begin{proof}
Assume $M$ runs under convention (1).
Then replace every state $q$ by an existential state
$q_e$, whose function is to ``guess'' the input bit.
Give $q_e$ two children $q_0$ and $q_1$ which are
universal states and correspond to the two guesses.
The left child of $q_0$ then polls the input and stops right away,
accepting iff the bit is $0$; likewise the left child of
$q_1$ polls the input and accepts iff the bit is $1$.
The right child of $q_0$ simulates the original state $q$,
but only includes the arcs of $q$ defined for the input bit being $0$.
The right child of $q_1$ simulates the transitions of $q$
for a `1' input.
Whichever right child has its guess validated
by its left sibling is the one that carries forth the
corresponding branch of the original machine $M$.
For every state $q$ along the path, there is a detour
through two new states, so the running time is tripled.
The new machine $M'$ needs no additional space.
If $M$ runs under convention (2), then this construction
only needs to be applied to state $q_{?}$.%\qed
\end{proof}
\bigskip
Now recall the definition of $\Sigma_k^{\lin}$ as the class
of languages accepted by linear-time ATMs with the property
that every computation path on every input $x$
begins with an existential state, and alternates at most
$k-1$ times from existential to universal states or vice-versa.
We can make the same stipulation on an ATM which runs
in logarithmic time, and this defines the class
$\Sigma_k^{\log}$.
However, the question of which input convention is used
needs to be addressed anew, because the above proof
can introduce {\em many\/} new alternations.
Happily, there is the following modification,
which I've seen one-sentence allusions to, but have not
seen worked out in detail in any sources I have:
\begin{lemma}\label{altconvs}
An ATM $M$ which runs under convention (1) or (2)
in time $t(n)$ and space $s(n)$ and has the
$\Sigma_k$ alternation property
can be simulated by an ATM $M'$ which runs under convention (3)
in time $3t(n)$ and space $2s(n)+t(n)$ and has the
$\Sigma_{k+1}$ alternation property.
\end{lemma}
\begin{proof}
Here is how to modify the construction of the preceding lemma:
If $q$ is an existential state, then make $q_e$
branch to two more existential states which simulate $q$,
and have $M'$ record along each branch the sequence of
guessed input bits
which it needs to check later.
As soon as the original computation by $M$ reaches
a universal state $q'$ of $M$, {\em or\/} reaches
a halting state $q'$, $M'$ goes into a routine which
retrieves all the guesses and enters universal nodes
whose left children check them in the manner of $q_0$ or $q_1$ above.
To do this only requires adding finitely many states in
a loop whose formal construction I leave to the reader.
On exit from this loop, $M'$ proceeds to $q'$.
If $q$ is a universal state, $M'$ has a state $q_a$
which branches to two more universal states $q_0$ and $q_1$;
$q_0$ simulates the transitions on input bit 0 for $q$,
and $q_1$ simulates those for $1$.
$M'$ records the bits assumed along each individual branch
until $M$ reaches an existential (or halting) state $q'$.
In place of $q'$, the branch by $M'$ goes to a
``master existential state'' $q_e$.
The left child of $q_e$ goes to a routine in existential states
which fans out to poll
each assumed input bit in some leaf, and the leaf accepts
iff the tested bit was {\em wrong\/}.
The right child of $q_e$ goes to $q'$ and proceeds with the
computation, {\em even though this computation path may be
invalid\/}.
The reasoning is that the path through the right child of
$q_e$ is invalid only if the left child has a leaf which accepts---this
makes $q_e$ automatically return ``accept'' to its parent and
renders the left child of $q_e$ immaterial.
Put another way, every node $q_a$ in the universal phase
expects both its children to accept.
The child for the wrong input bit has the property that
all branches below it have {\em some\/} wrong bit that
the left child of their $q_e$ can guess and propagate
upward the required ``accept.''
The child for the correct input bit, however, has
one critical path along which all the assumed bits are
correct.
The $q_e$ node for this critical path {\em cannot\/}
accept via its left child, and thus the responsibility
falls on the right child of $q_e$ to accept.
Since precisely this path carries on a valid computation path
of $M$, the construction is correct.
Because an extra level of like quantifiers is tacked on
in the case where $q'$ is a halting state of the original
machine $M$, the new machine has $k+1$ ``like-quantifier phases''
instead of $k$ along each path.
The extra additive term of $s(n)+t(n)$ on space comes from
storing a spare copy of the configuration at the beginning of a phase
and the sequence of guesses along the branch in that phase.
\end{proof}
\begin{corollary}
The definition of $\LOGH := \bigcup_{k=1}^{\infty} \Sigma_k^{\log}$
in unaffected by the choice of input-tape convention,
even though the individual $\Sigma_k^{\log}$ levels
might be shifted by one.\qed
\end{corollary}
Consensus is that for $k \geq 1$, one should use
convention (3) to define $\Sigma_k^{\log}$, while for
$k = 0$, i.e.\ $\Sigma_0^{\log} \eqdef \DLOGTIME$,
convention (1) is used.
The languages $0^* 1^*$ and $A$ above both belong
to $\Sigma_2^{\log}$, since the machine sketched in class
first guesses the break and then verifies the segments.
The proof in the next section uses the most
liberal convention (1) even for the case $k = 1$; i.e.,
in simulating a nondeterministic $O(\log n)$-time ATM.
\section{Log-Bounded Rudimentary Relations}\label{intro}
[Part of Lecture 39, prepared by Regan.]
\bigskip
The {\em log-bounded rudimentary relations\/} (LBR) \cite{Jon75}
are the closure of the following basic relations
\begin{eqnarray}
\sigma(x,j,a) &\equiv & \mbox{bit $j$ of $x$ equals $a$}\\
P_C(x,u,v,w) &\equiv & |w| \leq C\log_2|x| \AND uv=w
\quad(C \in \Nat^+)
\end{eqnarray}
under (1)~Boolean operations, (2)~explicit transformations, and
(3)~{\em log-bounded\/} existential quantification, viz. if
$\rho \in \LBR$, then for any $C > 0$,
the relation $\tau$ (of the same arity $k$)
defined by
\begin{equation}
\tau(x_1,x_2,\dots,x_{k-1},z) := (\exists y: |y| \leq C\log_2|z|)
\rho(x_1,x_2,\dots,x_{k-1},y)
\end{equation}
also belongs to LBR. Here, think of ``$x_1$'' as the input string $x$,
and recall that explicit transformation from $\tau$ gives us
$\rho'(x,x_2,\dots,x_{k-1}) := \tau(x,x_2,\dots,x_{k-1},x)$,
which is usually what we are interested in.
LBR is just like the (linear-bounded) rudimentary relations
except for the log-bound on concatenation, and more notably, the
extra predicate $\sigma(x,j,a)$. This plays the role of both
the input-indexing FOL predicate $Z(j)$, and Immerman's
predicate $\BIT(i,j) \equiv$ bit number $j$ of the number $i$
in standard binary notation is a 1. Thus LBR lets one
write $\sigma(i,j,a)$ and not worry about the lack of type
distinction between $i$ and $x$. (Well, {\em I'm\/} bothered by it!
But I haven't been able to pull off a ``unary trick'' like with my
proof of $\FOL \subseteq \SF$.) Note also the following convention
on semantics: if the index $j$ is ``out of range''; i.e., if
$j > |x|-1$ (recall we number from 0), then for all alphabet
characters $a$, $\sigma(x,j,a)$ is false, and likewise
$j > |i|-1 \implies \AND_a \neg\sigma(i,j,a)$. The gist of how
LBR simulates FOL+BIT is conveyed by two examples. First,
\[
Z(i) = a \AND \BIT(i,j) \AND i=k
\]
\[
\iff\\
\]
\[
\sigma(x,i,a) \AND \sigma(i,j,1) \AND \forall j: [\sigma(i,j,1) \eqv
\sigma(k,j,1)] \AND [\sigma(i,j,0) \eqv \sigma(k,j,0)].
\]
Note that the ``$\eqv$'' is needed for both 1 and 0, because
of the semantic convention. Allender and Gore \cite{AlGo91b}
do essentially the same thing in their definition of
``the constant $n$'' at the bottom of p93.
(Yes, this bugs me too, and for another thing, I don't see the
``few simplifications that result.'')
Also conventionally, $i$ and $k$ are regarded as numbers in standard
binary notation, with a leading `1' except for zero, and to
justify the above enforcing that $i$ and $k$ are equal as
bit-strings, we have to disallow leading 0s, {\em or\/} (and better,
I think) change the convention to $i$ and $k$ being written in
dyadic notation. More peculiar (in the British,
not-necessarily pejorative, sense of the word) is the definition
of `$<$' with some $x$cess baggage carried along:
\[
i < k \iff (\exists u: |u| \leq C\log_2|x|)(\exists v: |v|\leq C\log_2|x|)
(\exists v': |v'|\leq C\log_2|x|)
\]
\[
[P_C(x,u,v,i) \AND P_C(x,u,v',k) \AND \sigma(v,0,0) \sigma(v',0,1)].
\]
This works because numbers are written most-significant-bit
first. If FOL variables are restricted to the range
$[0\dots N]$ ($N = |x|$), and we change the definition of
$P_C$ to read ``$\dots |w| \leq C(1+\floor{\log_2|x|})$,''
then we can take $C = 1$ as Allender and Gore do.
(More ``literary criticism'': Their reference to ``$j+1$'' on p93
is one reason I didn't restrict indices to $[0\dots N-1]$.)
Also with this restriction, all quantifications
of FOL variables are automatically log-bounded, and that
completes the simulation of FOL+BIT by LBR.
The direct simulation of LBR by FOL is more problematic.
The predicates $Z(i)$ and $\BIT(i,j)$ handle the two types
of uses of $\sigma$ well enough, but the problem is
how to represent $P_C(x,u,v,w)$.
% Leaning a little on the
% convention that binary numbers have a leading `1', we can define
% \[
% k = |u| \equiv (\exists j): k=j+1 \AND \BIT(x,j) \AND
% (\forall i)[i > j \imp \neg\BIT(x,i)
% \[
% k = |u| \equiv (\exists j): k=j+1 \AND (\BIT(x,j)=0 \OR \BIT(x,j)=1))
% \AND \neg\BIT(x,k),0) \AND \neg\sigma(x,k,1)
If FOL variables are regarded as having values in standard
binary notation, then one can only represent instances of
concatenation in which both $u$ and $v$ begin with $1$.
This can be fixed either by using dyadic notation, or
by coding a string $u$ by an FOL variable with value $1u$.
The {\em intent\/} is first to define the relation
$k = |u|$,\footnote{Even here, if $\BIT(u,j)$ is defined to fail
either when bit $j$ of $u$ is 0 or when $j$ is out of range,
opposite to the convention on $\sigma$, there are annoying
technical problems in defining $k = |u|$. \cite{BIS90} get away
with their equation for ``$L$'' on p291 because they
(evidently) write binary numbers with the {\em least\/}
significant bit first.
}
and then using the predicate $\PLUS(i,j,k)$ defined in terms
of $\BIT$ and $>$ in \cite{BIS90}, to write
\[
uv=w \eqdef (\exists j)(\forall i,k)\,[j = |u| \AND
(i < j \imp (\BIT(u,i) \eqv \BIT(w,i)) \AND
\]
\[
((k \geq j \AND \PLUS(i,j,k)) \imp (\BIT(v,i) \eqv \BIT(w,k))).
\]
I'll leave further discussion of details to later, in conjunction
with asking exactly where $\PLUS$ and $\BSUM$ are needed in the
proofs.
There's also the problem of what to do if $C > 1$.
Implicitly, \cite{BIS90} encode a string of length $C\log_2|x|$
by a vector of $C$-many variables $\pair{v_1,\dots,v_C}$.
This isn't necessary in $\LBR$, and involves one
technical point worth discussing.
To maximize clarity in the next section, I shall
show $\DLOGTIME \subseteq \LBR$ instead of
$\DLOGTIME \subseteq \FO$ (recall $\FO$ stands for
languages definable in FOL+BIT).
Later I will explore what technicalities need to be plowed
in order to make this work in FOL+BIT.
For now, let us recall Jones' trick for getting a rudimentary
definition of
\[
\EQ(u) \equiv \#0(u) = \#1(u),
\]
where we will consider $u$ to be over the alphabet
$\set{0,1,2}$.
Namely, define homomorphisms $h_0$ and $h_1$ which
respectively erase 0s and 1s. Then define
\[
\EQ(u) \eqdef (\exists v_0)(\exists v_1): h_0(u) = v_0 \AND h_1(u) = v_1
\AND |v_0| = |v_1|.
\]
When applying this, we will have $|u| \leq C\log_2|x|$ for some
fixed constant $C$, and since $|v_0|,|v_1| \leq |u|$, the quantifications
are log-bounded. The three conjuncts are all rational relations,
and by extension of problem 6.1 on homework, definable
via $P_C$. This is the only place where $P_C$ is needed in the
proof in the next section, and I leave it to you to examine
which {\em instances\/} of $P_C$ are needed to set up those
three conjuncts.
\section{LOGH is contained in LBR}
[Lectures 39--40, prepared by Regan.]
Let $M$ be a Turing machine which runs in space $s(n)$ and time $t(n)$,
and which has some fixed number $k$ of work-tapes.
The description below is intended for deterministic or
nondeterministic TMs with ``random-access'' to input which run
in time and space $O(\log n)$, but it can be modified
for linear-time bounded TMs as well. Indeed, the theorem
$\DLIN \subseteq \RUD$ could have been proved this way,
instead of using intersections of CFLs as before.
Previously we have analyzed a TM computation in the form
of a {\em tableau\/} or {\em time-space diagram\/}, namely
a sequence of IDs. The problem is that this representation
can have length $s(n)t(n)$, which is too long to
quantify within linear length bounds (for $\RUD$), or
within logarithmic length bounds (for $\LBR$).
Instead, we can use the {\em trace\/} of a computation,
which is nothing but the sequence of transitions or ``dominoes''
\[
[q_0,i_{00},c_{10},\dots,c_{k0};d_{10},\dots,d_{k0},D_{10},\dots,D_{k0},q_1]
\]
\[
[q_{r-1},i_{0r},c_{1r},\dots,c_{kr};d_{1r},\dots,
d_{kr},D_{1r},\dots,D_{kr},q_r]
\]
\[
[q_{t-1},i_{0t},c_{1t},\dots,c_{kt};d_{1t},\dots,
d_{kt},D_{1t},\dots,D_{kt},q_t]
\]
Here $i_{0r}$ stands for the input character read at step $r$.
For standard TMs, there would also be a direction $D_{0r}$ for the
movement of the input head in step $r$.
For RAM-TMs, I am using the convention that they can read an
input character at any step (the initially blank address tape,
which is tape 1, holds zero and references bit $x_0$).
Note that each ``domino'' has length depending only on $M$,
not on $t$ or $x$, and we can let $\Delta$ be the finite
alphabet of dominoes as before (really, $\Delta$ is just $\delta_M$).
Let $\vec{d}$ stand for computations in this trace format.
The letter $e$ will be used for individual dominoes.
A helpful abbreviation is that $\AND_{e : c_j = c}$
denotes conjunction over all dominoes whose ``$c_j$ component''
equals $c$, and similarly for the written characters $d_j$
and head movements $D_j$.
\begin{theorem}
$\LOGH \subseteq \LBR$.
\end{theorem}
\begin{proof}
Suppose $M$ runs in time $t(n) \leq C\log_2 n$, where $C$ is a constant.
We may put $M$ in a normal form with a unique accepting
state $\qacc$, and add transitions which keep $M$ in state
$qacc$ forever. Also $M$ is not allowed to {\em write\/}
the blank $B$. For generality, I'll make $M$
{\it non\/}deterministic, and for cosmetic reasons,
I'll build into $M$ the following peculiar idea:
At the first step, $M$ marks the leftmost cell of each
worktape with a $\wedge$, and moves every worktape head right.
$M$ continues moving the heads right until it nondeterministically
chooses to stop them after some number $s$ of steps,
each writing a \$ in cell number $s$ on its tape. Then the
computation begins for real.
$M$ itself is coded so that no head can move rightward of \$
or left of $\wedge$, so that $M$
has initially guessed how much space it will use.
Moreover, all disposable cells hold non-blank characters,
and since $M$ never writes $B$, the blank need not be considered
from here on.
Once this is done, every valid trace $\vec{d}$ begins with
$s$-many $R$s in each ``$D_j$'' component.
This will be a convenience in using Jones'
$\EQ$ predicate from \cite{Jon69} in place of $\BSUM$ from \cite{BIS90}.
The basic idea is to write: For all $x$,
\[
x \in L(M) \iff (\exists \vec{d}: |\vec{d}| \leq C\log_2|x|)
(\exists s: |s| \leq |\vec{d}|):
\]
\[
\mbox{[the elements of $\vec{d}$ ``match like dominoes,''
and state $q_t$ is $\qacc$]},
\]
\[
\And \mbox{ the first $s$ steps are as described above},
\]
\& for each step $r \geq s$,
the characters $i_{0r},c_{1r},\dots,c_{kr}$ listed as being read
in the $r$th domino are the ones $M$ really sees on the tape.
\bigskip
The first predicate is easy to do once we fix a way to
reference individual components of a domino
$e \in \Delta$, as exemplified by:
\[
q_t = \qacc \eqdef \bigOR_{e = [\dots,\qacc]} \sigma(\vec{d},t-1,e).
\]
The first predicate then becomes:
\[
q_t = \qacc \AND (\forall r,r'): (0 \leq r \AND r' < t \AND r' = r+1) \imp
\]
\[
\bigOR_{\mbox{$e,e'$ which match}}
\sigma(\vec{d},r,e) \AND \sigma(\vec{d},r',e').
\]
For the second, we state right out that
the first domino, next $s-1$ dominoes, and the one after that
have the following respective forms,
in which only the input symbol $c$ scanned is unspecified,
and the states $q_0,p_1,p_2$ are taken verbatim from the code of $M$:
\begin{eqnarray*}
e_{0c} &= &[q_0,c,B,\dots,B,\wedge,\dots,\wedge,R,\dots,R,q_1]\\
e_{1c} &= &[q_1,c,B,\dots,B,0,\dots,0,R,\dots,R,q_1]\\
e_{2c} &= &[q_1,c,B,\dots,B,\$,\dots,\$,L,\dots,L,q_2]
\end{eqnarray*}
(Under the convention in which tape $1$ initially holds $n$ or $n-1$
in binary, where $n$ is the length of the input, one can
``hard-wire'' a different routine, left to the reader.)
The second predicate is:
\[
(\bigOR_{c \in \Sigma}\sigma(\hat{d},0,e_{0c})) \AND
(\bigOR_{c \in \Sigma}\sigma(\hat{d},s,e_{2c})) \AND
\]
\[
(\forall r)[(0 < r \AND r < s) \imp
\bigOR_{c \in \Sigma}\sigma(\hat{d},r,e_{1c})).
\]
The rest of the proof is how to represent the third condition that
enforces the ``consistency'' of $\hat{d}$.
In top-down fashion, with suggestive names for the
intermediate predicates, we define:
\bigskip
$\mbox{\it Valid\/}(\hat{d}) \eqdef (\forall r: 0 \leq r < t)
\mbox{\it InputOK\/}(\hat{d},r) \bigwedge \bigAND_{1 \leq j \leq k}
\mbox{\it TapeOK\/}_j(\hat{d},r).$
\bigskip
$\mbox{\it InputOK\/}(\hat{d},r) \eqdef (\forall I)[\bigAND_{c \in \Sigma}
\bigAND_{e: c_0 = c} (\sigma(\hat{d},r,e) \AND
\mbox{\it IsAddress\/}(\hat{d},r,I)) \imp \sigma(x,I,c)].$
\bigskip
$\mbox{\it TapeOK\/}_j(\hat{d},r) \eqdef (\forall I)(\forall p):$
\[
\left(\bigAND_{c \in \Sigma} \bigAND_{e: c_j = c}
(\sigma(\hat{d},r,e) \AND \mbox{\it IsString\/}_j(\hat{d},r,I)
\AND \Pos_j(r,p)\right) \imp \sigma(I,p,c).
\]
\bigskip
$\mbox{\it IsString\/}_j(r,I) \eqdef (\forall p)[\bigAND_{c \in \Gamma}
(\mbox{\it IsChar\/}_{jc}(\hat{d},r,p) \eqv \sigma(I,p,c))].$
\bigskip
$\mbox{\it IsAddress\/}(r,I) \eqdef (\forall p,p'): p' = p+1 \imp$
\[
\left( (\sigma(I,p,0) \AND \mbox{\it IsChar\/}_{10}(\hat{d},r,p') \OR
(\sigma(I,p,1) \AND \mbox{\it IsChar\/}_{11}(\hat{d},r,p')\right).
\]
The last definition can be modified to suit one's taste
about how addresses are represented; this one allows any
string in $\set{0,1}^{s-1}$ to be considered an address.
One can also consider the format of addresses
to be ``hard-wired'' by restrictions on the code of $M$.
The only reason to define {\it IsAddress\/} separately
from {\it IsString\/} is to surmount the left endmarker $\wedge$
on tape~1.
Similarly, it is not necessary to build into the formula
that $M$ never moves left of $\wedge$ not right of $\$$;
this is already taken care of by restricting ``dominoes'' to $\Delta$.
Now $\Pos_j(r,p)$ means ``at step $r$, the head on tape $j$
is reading the symbol in cell $p$ on that tape,''
and $\mbox{\it IsChar\/}_{jc}(\hat{d},r,p)$ means ``at step $r$,
cell $p$ on tape $j$ holds $c$.''
The strings $I$ quantified over have length $O(\log n)$,
which is acceptable in $\LBR$, while $p$ and $r$ are even tinier
objects of length $\loglog n + O(1)$.
It remains to write {\it IsChar\/} in terms of $\Pos$ and then
write $\Pos$. Owing to our hard-wiring of the initial stage,
it suffices to define {\it IsChar\/}$_{jc}(\hat{d},r,p)$
for characters $c \neq B$ in a way that need only be correct for
$r > s$ and $p \leq s$.
% \[
% \mbox{\it IsChar\/}_{jB}(\hat{d},r,p) \eqdef
% (\forall r')(r' < r \imp \neg\Pos(r',p)),\quad\mbox{and for $c \neq B$,}
% \]
\[
\mbox{\it IsChar\/}_{jc}(\hat{d},r,p) \eqdef
(\exists r')[r' < r \AND \Pos_j(r',p) \AND
(\forall r'' \neg(r' < r'' \AND r'' < r \AND \Pos_j(r'',p))]
\]
\[
\AND \bigOR_{e: d_j = c}\sigma(\hat{d},r,e).
\]
The second predicate asserts that there was a last time cell $p$
on tape $j$ was visited, and that the character written then was $c$.
Now to write $\Pos$, we focus on the entries $D_j$ giving the
direction the head moves at step $r$.
We identify a left move with $0$, a right move with $1$, and
use $2$ for ``filler'' in defining:
\bigskip
$\mbox{\it IsSlice\/}_j(\hat{d},p,r,w) \eqdef |w|=|\hat{d}| \AND (\forall i):$
\begin{eqnarray*}
[(i < p \OR i \geq r) &\imp &\sigma(w,i,2)] \AND\\
(p \leq i \AND i < r) &\imp &
(\sigma(w,i,0) \AND \bigOR_{e: D_j = L}\sigma(\hat{d},i,e))\\
&\OR & (\sigma(w,i,1) \AND \bigOR_{e: D_j = R}\sigma(\hat{d},i,e)).
\end{eqnarray*}
The final idea is to assert that the head on tape $j$
is in position $p$ at time $r$ iff either $r = p$ (as during the startup)
or $r > p$ and the movements in the $D_j$ column from
step $p$ to step $r-1$ have exactly as many $L$s as $R$s, which
becomes the following:
\bigskip
$\Pos_j(r,p) \eqdef $r = p$ \OR [$r > p$ \AND
(\exists w)(\mbox{\it IsSlice\/}_j(\hat{d},p,r,w) \AND \EQ(w))].$
\bigskip
That turns the trick, and leaves only the requirement of finding
a definition, in $\LBR$ or in FO+BIT, of $\EQ(w)$.
First express the condition $J(w,v_0,v_1)$ that
$v_0,v_1 \in \set{0,1}^*$, $|v_0| = |v_1| = |w|$,
$v_0$ has a `1' precisely where $w$ has a `0',
and $v_1$ has a `1' precisely where $w$ has a `1'.
Barrington, Immerman, and Straubing \cite{BIS90}
essentially define:
\[
\EQ(w) \eqdef (\exists v_0)(\exists v_1)(\exists i)
[J(w,v_0,v_1) \AND \BSUM(v_0,i) \AND \BSUM(v_1,i)].
\]
Alternatively, let $\eta$ be the rational relation which
defines the graph of the erasing homomorphism
$h(0) = \epsilon$, $h(1) = 1$; i.e., $\eta = ((0,\epsilon) \cup (1,1))^*$.
Then we can define:
\[
\EQ(w) \eqdef (\exists v_0)(\exists v_1)(\exists y)
[J(w,v_0,v_1) \AND \eta(v_0,y) \AND \eta(v_1,y)].
\]
Jones \cite{Jon69} gives a definition of $\eta$ which,
since the strings $v_0$ and $v_1$ have length $O(\log |x|)$,
is formalizable in $\LBR$.
However, his proof does so via an inductive definition of
counting, and contains essentially the same details as
the definition of $\BSUM$ in \cite{BIS90}.
This was the ulterior motive of problem 6.1 and its timing,
and the class remains challenged to fix the ``handwave'' I've noted
and to determine whether one can represent the simple
rational relation $\eta$ in LBR without such sophisticated
counting.
Absent this final detail, that completes the proof that
nondeterministic log-time RAM-TMs accept languages in $\LBR$.
The conclusion that $\LOGH \subseteq \LBR$ is obtained by
exactly the same means as in the earlier
deduction of $\LINH \subseteq \RUD$ from the lemma
$\NLIN \subseteq \RUD$. %\qed
\end{proof}
\section{Summary of Remaining Notes}
Going from $\LBR$ to FO+BIT was treated in the last section,
and going from $\LBR$ or FO+BIT to $\LOGH$ is straightforward
and similar to $\RUD \subseteq \LINH$.
Hence all three classes are equal.
A sketch of the remaining originally-planned lectures,
which I may be able to type up in January:
\begin{itemize}
\item
While doing $\LBR \subseteq \LOGH$ and FO+BIT$\mbox{} \subseteq \LOGH$,
show also how the {\em matrices\/} of the quantifier-free formulas
have depth-2 unbounded fan-in circuits, and then how
each $\exists$ quantifier adds a big OR gate, each $\forall$
quantifier adds an AND gate.
(Do this while defining circuits in general, plus the lemma
that negations can always be pushed up to the inputs.)
Thus every language $L \in \LBR$ has a family
$[C_n]_{n=1}^{\infty}$ of constant-depth, unbounded
fan-in circuits, one for each input length $n$.
Give the definitions of the classes $\NC^k$ [respectively, $\AC^k$]
of languages which have
families $[C_n]$ of circuits of bounded [resp.\ unbounded] fan-in,
such that the circuits $C_n$ have polynomial size and
$O(\log^k n)$-depth.
Thus $\LBR \subseteq \AC^0$.
Moreover, there is a {\em uniform\/} way of describing
each individual $C_n$, in terms of the single FOL+BIT
formula $\phi$ that defines $L$ for all input length.
\item
Discuss the problem of non-uniform vs.\ uniform circuits
in general. Give an example of a non-uniform family of
depth-1 circuits which
decide a non-r.e. set---the non-r.e.-ness is all in the
selection of which circuit for which $n$.
{\em Briefly\/} review the major competing criteria
of uniformity, and without going into too much unrewarding
detail, explain the theorem that FOL+BIT =
$\DLOGTIME$-uniform $\AC^0$.
Then prove the theorem (from \cite{Bar89,BIS90}) that
{\em non-uniform\/} $\AC^0$
is equivalent to FOL plus {\em arbitrary numerical predicates\/}
in place of BIT.
(A ``numerical predicate'' is one which doesn't involve
the input $x$, i.e. has no $Z(i)$ terms.
$\PLUS(i,j,k)$, and the graphs of multiplication and
$i^j = k$, with ad-hoc conventions for handling values-out-of-bounds,
are examples of numerical predicates.)
\item
Mention the theorem of Furst, Saxe, and Sipser \cite{FSS84}
that the regular language
{\it Parity\/} $\eqdef \set{x \in \set{0,1}^* : \#1(x) \mbox{ is odd}}$
is not in $\AC^0$; indeed, Yao \cite{Yao85} and Hastad
\cite{Has86,Has89} obtained exponential lower bounds on the
size of constant-depth circuits for {\it Parity\/}.
Then define the class $\ACC^0$ of languages with constant-depth,
polynomial size circuits of unbounded fan-in AND, OR, and
``Mod $k$'' gates, where $k$ belongs to
some finite set of numbers fixed independent of $n$.
(Negation gates are taken for granted.)
Clearly {\it Parity\/} is in $\ACC^0$.
% Also define the class $\TC^0$ given by constant-depth
% circuits of unbounded fan-in AND, OR, and
% MAJORITY gates.
Thus $\AC^0 \subset \ACC^0 \subseteq \NC^1$.
It is also known that $\ACC^0 \subset \PP$ \cite{AlGo91}, but
it is still consistent with current knowledge that
$\ACC^0 = \NP$.
Discuss the problem of separating $\ACC^0$ from $\NC^1$, and how
there are regular languages which are ``$\NC^1$-complete''
under ``constant-depth reducibility.''
\item
State and prove translation theorems, some of them original
to Allender and Gore, which tie open questions about
these classes to the longer-standing open questions about
$\RUD$ and $\ATIME[O(n)]$ and $\DSPACE[O(n)]$ and the
DLBA vs.\ NLBA problem.
Doing so would tie the whole course subject matter neatly together.
\item
Finally describe some of my own work, including a new
machine characterization of uniform $\NC^1$ (and $\NC^k$ for all $k > 1$),
and interesting research problems which arise when one tries
to extend my model for the classes $\AC^k$.
\end{itemize}
\bibliography{newpapers}
\end{document}
SHAR_EOF
fi # end of overwriting check
if test -f 'LNall.aux'
then
echo shar: will not over-write existing file "'LNall.aux'"
else
cat << \SHAR_EOF > 'LNall.aux'
\relax
\bibstyle{alpha}
\citation{Rose84}
\citation{Gre81}
\citation{FSS81,FSS84}
\citation{Imm87,Bar89,BIS90}
\citation{Jon69,Jon75,Wra78}
\citation{MP71}
\citation{Lin92b}
\citation{AlGo91b}
\citation{BIS90}
\citation{Wra78}
\citation{BoGr70}
\citation{GrHo69}
\citation{BIS90}
\citation{Jon69}
\citation{Lip78}
\citation{Mey69,MP71,Lad77,Tho82,PePi86,Bar89}
\@writefile{toc}{\string\contentsline\space {section}{\string\numberline\space {1}Preface}{1}}
\citation{HU79}
\citation{HU79}
\citation{HU79}
\@writefile{toc}{\string\contentsline\space {section}{\string\numberline\space {2}Review of Formal Language Theory and Preview of Course}{3}}
\citation{Wra75}
\citation{Wra78}
\citation{Jon69}
\citation{PPST83}
\citation{Jon75,AlGo91b}
\citation{Smu61}
\@writefile{toc}{\string\contentsline\space {subsection}{\string\numberline\space {2.1}Generalized Homomorphisms}{7}}
\newlabel{TM-to-gh}{{2.1}{7}}
\@writefile{toc}{\string\contentsline\space {section}{\string\numberline\space {3}The Chomsky Hierarchy}{8}}
\@writefile{lot}{\string\contentsline\space {table}{\string\numberline\space {1}{\ignorespaces The Chomsky Hierarchy}}{9}}
\newlabel{tbl:ch}{{1}{9}}
\@writefile{toc}{\string\contentsline\space {section}{\string\numberline\space {4}Known Results and Open Problems}{10}}
\@writefile{toc}{\string\contentsline\space {subsection}{\string\numberline\space {4.1}Determinism and Non-determinism}{10}}
\@writefile{toc}{\string\contentsline\space {subsection}{\string\numberline\space {4.2}Machine Definitions}{10}}
\citation{HU79}
\@writefile{toc}{\string\contentsline\space {section}{\string\numberline\space {5}Deterministic Pushdown Automata}{11}}
\@writefile{toc}{\string\contentsline\space {paragraph}{Normal Forms and Acceptance conditions of ${\string\prm\space DPDA}$s}{12}}
\@writefile{toc}{\string\contentsline\space {subsection}{\string\numberline\space {5.1}Normal Forms of ${\string\prm\space DPDA}$s}{12}}
\@writefile{toc}{\string\contentsline\space {subsection}{\string\numberline\space {5.2}Digression: discussion of problem about reducibility relations}{14}}
\@writefile{toc}{\string\contentsline\space {section}{\string\numberline\space {6}Closure properties of CFLs}{14}}
\@writefile{toc}{\string\contentsline\space {subsection}{\string\numberline\space {6.1}Monoid of transformations}{15}}
\@writefile{lof}{\string\contentsline\space {figure}{\string\numberline\space {1}{\ignorespaces Inclusion diagram}}{17}}
\newlabel{MinL}{{6.1}{17}}
\citation{HU79}
\@writefile{lof}{\string\contentsline\space {figure}{\string\numberline\space {2}{\ignorespaces Motivation}}{18}}
\newlabel{MinLregular}{{6.4}{18}}
\@writefile{toc}{\string\contentsline\space {section}{\string\numberline\space {7}Predicting Machine Construction}{18}}
\@writefile{toc}{\string\contentsline\space {section}{\string\numberline\space {8}LR$(k)$ Grammars}{20}}
\newlabel{LRkitem}{{8.1}{20}}
\newlabel{validity}{{8.2}{20}}
\newlabel{Ikgamma}{{1}{20}}
\newlabel{DFA}{{8.1}{21}}
\newlabel{iproof}{{8}{21}}
\newlabel{Ikgamma0}{{2}{21}}
\newlabel{Ikgamma2}{{3}{22}}
\newlabel{compare}{{4}{22}}
\newlabel{LRk}{{8.3}{23}}
\@writefile{toc}{\string\contentsline\space {section}{\string\numberline\space {9}Proof of the equivalence to DPDAs}{23}}
\newlabel{DPDA}{{9.1}{23}}
\newlabel{niceNF}{{9.3}{26}}
\@writefile{toc}{\string\contentsline\space {subsection}{\string\numberline\space {9.1}Some final remarks about LR($k$) grammars}{31}}
\@writefile{toc}{\string\contentsline\space {section}{\string\numberline\space {10}Rational Relations}{31}}
\citation{Reg88}
\newlabel{freeregular}{{10.1}{33}}
\newlabel{ratrelnf}{{10.2}{34}}
\newlabel{specialtgo}{{10.3}{34}}
\newlabel{tgotoratrel}{{10.4}{34}}
\newlabel{ratreltotgo}{{10.5}{35}}
\newlabel{inverseredn}{{10.6}{37}}
\@writefile{toc}{\string\contentsline\space {section}{\string\numberline\space {11}The Chomsky-Sch{\accent "7F u}tzenberger Representation Theorem}{38}}
\@writefile{toc}{\string\contentsline\space {paragraph}{Question:}{38}}
\@writefile{toc}{\string\contentsline\space {paragraph}{Note:}{39}}
\@writefile{toc}{\string\contentsline\space {paragraph}{{\string\prm\space L(G)} $ \subseteq t(h^{-1}(D_n) \cap L(G_R))$ part:}{39}}
\@writefile{toc}{\string\contentsline\space {paragraph}{Basis (m=1):}{39}}
\@writefile{toc}{\string\contentsline\space {paragraph}{Induction (m $\ge $ 2):}{39}}
\@writefile{toc}{\string\contentsline\space {paragraph}{{\string\prm\space L(G)} $ \supseteq t(h^{-1}(D_n) \cap L(G_R))$ part}{39}}
\@writefile{toc}{\string\contentsline\space {paragraph}{Basis (m=1) :}{40}}
\@writefile{toc}{\string\contentsline\space {paragraph}{Induction (m $\ge $ 2) :}{40}}
\@writefile{toc}{\string\contentsline\space {subsection}{\string\numberline\space {11.1}Restating and Refining Chomsky-Sch{\accent "7F u}tzenberger}{40}}
\@writefile{toc}{\string\contentsline\space {paragraph}{Fact:}{40}}
\@writefile{toc}{\string\contentsline\space {paragraph}{Refinement 1: }{40}}
\@writefile{toc}{\string\contentsline\space {paragraph}{Refinement 2: }{40}}
\@writefile{toc}{\string\contentsline\space {paragraph}{Research questions:}{40}}
\@writefile{toc}{\string\contentsline\space {paragraph}{Refinement 3: }{41}}
\@writefile{toc}{\string\contentsline\space {paragraph}{Challenge questions:}{41}}
\@writefile{toc}{\string\contentsline\space {section}{\string\numberline\space {12}Rational Relations Versus Regular Languages}{41}}
\@writefile{toc}{\string\contentsline\space {paragraph}{$\Rightarrow $ is false:}{41}}
\@writefile{toc}{\string\contentsline\space {paragraph}{But $\Leftarrow $ is true!}{42}}
\@writefile{toc}{\string\contentsline\space {paragraph}{Note:}{42}}
\@writefile{toc}{\string\contentsline\space {paragraph}{Research question:}{42}}
\@writefile{toc}{\string\contentsline\space {paragraph}{Note:}{42}}
\@writefile{toc}{\string\contentsline\space {subsection}{\string\numberline\space {12.1}A Pumping Lemma for Rational Relations}{42}}
\@writefile{toc}{\string\contentsline\space {paragraph}{Example:}{43}}
\@writefile{toc}{\string\contentsline\space {paragraph}{Question:}{43}}
\@writefile{toc}{\string\contentsline\space {paragraph}{Answer:}{43}}
\@writefile{toc}{\string\contentsline\space {paragraph}{Exercises:}{43}}
\@writefile{toc}{\string\contentsline\space {paragraph}{Footnote to the Pumping Lemma proof :}{43}}
\@writefile{toc}{\string\contentsline\space {section}{\string\numberline\space {13}Descriptive Complexity}{44}}
\@writefile{toc}{\string\contentsline\space {section}{\string\numberline\space {14}Operations on Rational Relations}{46}}
\@writefile{toc}{\string\contentsline\space {subsection}{\string\numberline\space {14.1}Set operations}{46}}
\@writefile{toc}{\string\contentsline\space {subsection}{\string\numberline\space {14.2}Explicit Transformations}{46}}
\newlabel{ssec:xt}{{14.2}{46}}
\@writefile{toc}{\string\contentsline\space {subsubsection}{\string\numberline\space {14.2.1}Substitution}{46}}
\@writefile{toc}{\string\contentsline\space {subsubsection}{\string\numberline\space {14.2.2}Instantiation}{46}}
\@writefile{toc}{\string\contentsline\space {subsubsection}{\string\numberline\space {14.2.3}A Taxonomy of Explicit Transformations}{47}}
\newlabel{sssec:taxonomy}{{14.2.3}{47}}
\newlabel{perm}{{1}{47}}
\newlabel{addvar}{{2}{47}}
\newlabel{instance}{{3}{47}}
\newlabel{ident}{{4}{47}}
\@writefile{toc}{\string\contentsline\space {subsection}{\string\numberline\space {14.3}Unbounded Existential Quantification}{48}}
\newlabel{sec:uboundq}{{14.3}{48}}
\@writefile{toc}{\string\contentsline\space {subsection}{\string\numberline\space {14.4}Bounded Existential Quantification}{48}}
\newlabel{sec:bquant}{{14.4}{48}}
\@writefile{toc}{\string\contentsline\space {section}{\string\numberline\space {15}Aside}{48}}
\newlabel{sec:regs}{{15}{48}}
\citation{HaKl93}
\citation{HaKl93}
\@writefile{toc}{\string\contentsline\space {section}{\string\numberline\space {16}Examples of Rudimentary Languages}{49}}
\@writefile{toc}{\string\contentsline\space {section}{\string\numberline\space {17}RUD and CFL}{51}}
\@writefile{toc}{\string\contentsline\space {section}{\string\numberline\space {18}RUD and the Arithmetic Hierarchy}{52}}
\@writefile{toc}{\string\contentsline\space {section}{\string\numberline\space {19}The Linear Time Hierarchy}{53}}
\@writefile{toc}{\string\contentsline\space {section}{\string\numberline\space {20}Alternating Turing Machines}{55}}
\citation{GrHo69}
\@writefile{toc}{\string\contentsline\space {section}{\string\numberline\space {21}Star-free Regular Languages}{58}}
\newlabel{starfree}{{21.2}{59}}
\@writefile{toc}{\string\contentsline\space {section}{\string\numberline\space {22}Closure properties of Star-free Languages}{61}}
\@writefile{toc}{\string\contentsline\space {subsection}{\string\numberline\space {22.1}An Instructive Example}{62}}
\@writefile{toc}{\string\contentsline\space {paragraph}{Idea behind proof:}{62}}
\@writefile{lot}{\string\contentsline\space {table}{\string\numberline\space {2}{\ignorespaces Multiplication table of the equivalence classes under $\sim _2$}}{63}}
\newlabel{tbl:mult}{{2}{63}}
\@writefile{toc}{\string\contentsline\space {paragraph}{Eilenberg's condition:}{63}}
\@writefile{toc}{\string\contentsline\space {paragraph}{Research Problems:}{63}}
\@writefile{toc}{\string\contentsline\space {section}{\string\numberline\space {23}The Equivalence of SF and FOL}{64}}
\@writefile{toc}{\string\contentsline\space {paragraph}{Notes:}{64}}
\@writefile{toc}{\string\contentsline\space {paragraph}{Note for purists:}{64}}
\@writefile{toc}{\string\contentsline\space {paragraph}{Note:}{65}}
\@writefile{toc}{\string\contentsline\space {paragraph}{Question:}{65}}
\@writefile{toc}{\string\contentsline\space {paragraph}{Note from KWR:}{65}}
\citation{AlGo91b}
\citation{CKS81}
\@writefile{toc}{\string\contentsline\space {section}{\string\numberline\space {24}``Random-Access'' TMs and Sub-Linear Time}{66}}
\newlabel{0*1*}{{24.1}{67}}
\newlabel{niceATM}{{24.1}{67}}
\newlabel{altconvs}{{24.2}{68}}
\citation{Jon75}
\@writefile{toc}{\string\contentsline\space {section}{\string\numberline\space {25}Log-Bounded Rudimentary Relations}{69}}
\newlabel{intro}{{25}{69}}
\citation{AlGo91b}
\citation{BIS90}
\citation{BIS90}
\citation{BIS90}
\@writefile{toc}{\string\contentsline\space {section}{\string\numberline\space {26}LOGH is contained in LBR}{71}}
\citation{Jon69}
\citation{BIS90}
\citation{BIS90}
\citation{Jon69}
\citation{BIS90}
\citation{Bar89,BIS90}
\citation{FSS84}
\citation{Yao85}
\citation{Has86,Has89}
\citation{AlGo91}
\@writefile{toc}{\string\contentsline\space {section}{\string\numberline\space {27}Summary of Remaining Notes}{75}}
\bibdata{newpapers}
\bibcite{AlGo91}{AG91a}
\bibcite{AlGo91b}{AG91b}
\bibcite{Bar89}{Bar89}
\bibcite{BoGr70}{BG70}
\bibcite{BIS90}{BIS90}
\bibcite{CKS81}{CKS81}
\bibcite{FSS81}{FSS81}
\bibcite{FSS84}{FSS84}
\bibcite{GrHo69}{GH69}
\bibcite{Gre81}{Gre81}
\bibcite{Has86}{Has86}
\bibcite{Has89}{Has89}
\bibcite{HaKl93}{HK93}
\bibcite{HU79}{HU79}
\bibcite{Imm87}{Imm87}
\bibcite{Jon69}{Jon69}
\bibcite{Jon75}{Jon75}
\bibcite{Lad77}{Lad77}
\bibcite{Lin92b}{Lin92}
\bibcite{Lip78}{Lip78}
\bibcite{Mey69}{Mey69}
\bibcite{MP71}{MP71}
\bibcite{PePi86}{PP86}
\bibcite{PPST83}{PPST83}
\bibcite{Reg88}{Reg88}
\bibcite{Rose84}{Ros84}
\bibcite{Smu61}{Smu61}
\bibcite{Tho82}{Tho82}
\bibcite{Wra75}{Wra75}
\bibcite{Wra78}{Wra78}
\bibcite{Yao85}{Yao85}
SHAR_EOF
fi # end of overwriting check
if test -f 'LNall.bbl'
then
echo shar: will not over-write existing file "'LNall.bbl'"
else
cat << \SHAR_EOF > 'LNall.bbl'
\begin{thebibliography}{PPST83}
\bibitem[AG91a]{AlGo91}
E.~Allender and V.~Gore.
\newblock On strong separations from {$AC^0$}.
\newblock In {\em Proc. 8th FCT}, volume 529 of {\em LNCS}, pages 1--15.
Springer Verlag, 1991.
\newblock To appear in the {DIMACS} Special Year volume, ed.\ J.-Y. Cai, {AMS}
Publications.
\bibitem[AG91b]{AlGo91b}
E.~Allender and V.~Gore.
\newblock Rudimentary reductions revisited.
\newblock {\em Inf. Proc. Lett.}, 40:89--95, 1991.
\bibitem[Bar89]{Bar89}
D.~Mix Barrington.
\newblock Bounded-width polynomial-size branching programs recognize exactly
those languages in {NC$^1$}.
\newblock {\em J. Comp. Sys. Sci.}, 38:150--164, 1989.
\bibitem[BG70]{BoGr70}
R.~Book and S.~Greibach.
\newblock Quasi-realtime languages.
\newblock {\em Math. Sys. Thy.}, 4:97--111, 1970.
\bibitem[BIS90]{BIS90}
D.~Mix Barrington, N.~Immerman, and H.~Straubing.
\newblock On uniformity within {$\NC^1$}.
\newblock {\em J. Comp. Sys. Sci.}, 41:274--306, 1990.
\bibitem[CKS81]{CKS81}
A.~Chandra, D.~Kozen, and L.~Stockmeyer.
\newblock Alternation.
\newblock {\em J. ACM}, 28:114--133, 1981.
\bibitem[FSS81]{FSS81}
M.~Furst, J.~Saxe, and M.~Sipser.
\newblock Parity, circuits, and the polynomial-time hierarchy.
\newblock In {\em Proc. 22nd FOCS}, pages 260--270, 1981.
\bibitem[FSS84]{FSS84}
M.~Furst, J.~Saxe, and M.~Sipser.
\newblock Parity, circuits, and the polynomial-time hierarchy.
\newblock {\em Math. Sys. Thy.}, 17:13--27, 1984.
\bibitem[GH69]{GrHo69}
S.~Greibach and J.~Hopcroft.
\newblock Scattered context grammars.
\newblock {\em J. Comp. Sys. Sci.}, 3:233--247, 1969.
\bibitem[Gre81]{Gre81}
S.~Greibach.
\newblock Formal languages: Origins and directions.
\newblock {\em Ann. Hist. Comp.}, 3:14--41, 1981.
\bibitem[Has86]{Has86}
J.~Hastad.
\newblock Almost optimal lower bounds for small-depth circuits.
\newblock In {\em Proc. 18th STOC}, pages 6--20, 1986.
\bibitem[Has89]{Has89}
J.~Hastad.
\newblock Almost optimal lower bounds for small-depth circuits.
\newblock In S.~Micali, editor, {\em Randomness and Computation}, volume~5 of
{\em Advances in Computing Research}, pages 143--170. JAI Press, Greenwich,
CT, USA, 1989.
\bibitem[HK93]{HaKl93}
T.~Harju and H.C.M. Klein.
\newblock Morphisms and rational transducers.
\newblock {\em Bull. EATCS}, 51:168--180, October 1993.
\newblock Guest column, A. Salomaa ed., Formal Language Theory Column.
\bibitem[HU79]{HU79}
J.~Hopcroft and J.~Ullman.
\newblock {\em Introduction to Automata Theory, Languages, and Computation}.
\newblock Addison--Wesley, Reading, MA, 1979.
\bibitem[Imm87]{Imm87}
N.~Immerman.
\newblock Languages which capture complexity classes.
\newblock {\em SIAM J. Comp.}, 16:760--778, 1987.
\bibitem[Jon69]{Jon69}
N.~Jones.
\newblock Context-free languages and rudimentary attributes.
\newblock {\em Math. Sys. Thy.}, 2:102--380, 1969.
\newblock Corrigendum {\it MST\/} {\bf 11} (1978), 379--380.
\bibitem[Jon75]{Jon75}
N.~Jones.
\newblock Space-bounded reducibility among combinatorial problems.
\newblock {\em J. Comp. Sys. Sci.}, 11:68--85, 1975.
\newblock Corrigendum {\it JCSS\/} {\bf 15} (1977), 241.
\bibitem[Lad77]{Lad77}
R.~Ladner.
\newblock The computational complexity of provability in systems of modal
propositional logic.
\newblock {\em SIAM J. Comp.}, 6:467--480, 1977.
\bibitem[Lin92]{Lin92b}
S.~Lindell.
\newblock A purely logical characterization of circuit uniformity.
\newblock In {\em Proc. 7th Structures}, pages 185--192, 1992.
\bibitem[Lip78]{Lip78}
R.~Lipton.
\newblock Model-theoretic aspects of computational complexity.
\newblock In {\em Proc. 19th FOCS}, pages 191--200, 1978.
\bibitem[Mey69]{Mey69}
A.~Meyer.
\newblock A note on star-free events.
\newblock {\em J. ACM}, 16:220--225, 1969.
\bibitem[MP71]{MP71}
R.~McNaughton and S.~Papert.
\newblock {\em Counter-Free Automata}.
\newblock MIT Press, Cambridge, MA, 1971.
\bibitem[PP86]{PePi86}
D.~Perrin and J.~Pin.
\newblock First-order logic and star-free sets.
\newblock {\em J. Comp. Sys. Sci.}, 32:393--406, 1986.
\bibitem[PPST83]{PPST83}
W.~Paul, N.~Pippenger, E.~Szemer{\'e}di, and W.~Trotter.
\newblock On determinism versus nondeterminism and related problems.
\newblock In {\em Proc. 24th FOCS}, pages 429--438, 1983.
\bibitem[Reg88]{Reg88}
K.~Regan.
\newblock The topology of provability in complexity theory.
\newblock {\em J. Comp. Sys. Sci.}, 3:384--432, 1988.
\bibitem[Ros84]{Rose84}
H.~Rose.
\newblock {\em Subrecursion: Functions and Hierarchies}.
\newblock Oxford Logic Guides. Oxford University Press, 1984.
\bibitem[Smu61]{Smu61}
R.~Smullyan.
\newblock {\em Theory of Formal Systems}, volume~47 of {\em Annals of
Mathematics Studies}.
\newblock Princeton University Press, Princeton, NJ, 1961.
\bibitem[Tho82]{Tho82}
W.~Thomas.
\newblock Classifying regular events in symbolic logic.
\newblock {\em J. Comp. Sys. Sci.}, 25:360--376, 1982.
\bibitem[Wra75]{Wra75}
C.~Wrathall.
\newblock {\em Subrecursive predicates and automata}.
\newblock PhD thesis, Harvard University, 1975.
\newblock Reprinted and available via the Department of Mathematics, Univ. of
CA at Santa Barbara.
\bibitem[Wra78]{Wra78}
C.~Wrathall.
\newblock Rudimentary predicates and relative computation.
\newblock {\em SIAM J. Comp.}, 7:194--209, 1978.
\bibitem[Yao85]{Yao85}
A.~Yao.
\newblock Separating the polynomial-time hierarchy by oracles.
\newblock In {\em Proc. 26th FOCS}, pages 1--10, 1985.
\end{thebibliography}
SHAR_EOF
fi # end of overwriting check
if test -f 'LNall.blg'
then
echo shar: will not over-write existing file "'LNall.blg'"
else
cat << \SHAR_EOF > 'LNall.blg'
This is BibTeX, C Version 0.99c
The top-level auxiliary file: LNall.aux
The style file: alpha.bst
Database file #1: newpapers.bib
SHAR_EOF
fi # end of overwriting check
# End of shell archive
exit 0