<?xml version="1.0" encoding="UTF-8"?><?xml-stylesheet type="text/xsl" href="static/style.xsl"?><OAI-PMH xmlns="http://www.openarchives.org/OAI/2.0/" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.openarchives.org/OAI/2.0/ http://www.openarchives.org/OAI/2.0/OAI-PMH.xsd"><responseDate>2026-11-22T16:56:49Z</responseDate><request verb="GetRecord" identifier="oai:uwspace.uwaterloo.ca:10012/6838" metadataPrefix="dim">https://dspacemainprd01.lib.uwaterloo.ca/server/oai/request</request><GetRecord><record><header><identifier>oai:uwspace.uwaterloo.ca:10012/6838</identifier><datestamp>2017-03-21T18:23:51Z</datestamp><setSpec>com_10012_9924</setSpec><setSpec>com_10012_1</setSpec><setSpec>col_10012_9930</setSpec><setSpec>col_10012_6</setSpec></header><metadata><dim:dim xmlns:dim="http://www.dspace.org/xmlns/dspace/dim" xmlns:doc="http://www.lyncode.com/xoai" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.dspace.org/xmlns/dspace/dim http://www.dspace.org/schema/dim.xsd">
   <dim:field mdschema="dc" element="contributor" qualifier="author" authority="e8d86e9d-d197-46d4-b577-9c1c0deeb214" confidence="600">Li, Baiyu</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="accessioned">2012-07-31T19:07:45Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="available">2012-07-31T19:07:45Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="issued">2012-07-31T19:07:45Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="submitted">2012</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="uri">http://hdl.handle.net/10012/6838</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="abstract" lang="en">The syntactic complexity of a regular language is the cardinality of its syntactic semigroup. The syntactic complexity of a subclass of the class of regular languages is the maximal syntactic complexity of languages in that class, taken as a function of the state complexity n of these languages.&#xd;
We study the syntactic complexity of suffix-, bifix-, and factor-free regular languages, star-free languages including three subclasses, and R- and J-trivial regular languages. &#xd;
&#xd;
We found upper bounds on the syntactic complexities of these classes of languages. For R- and J-trivial regular languages, the upper bounds are n! and ⌊e(n-1)!⌋, respectively, and they are tight for n &amp;gt;= 1. Let C^n_k be the binomial coefficient ``n choose k&amp;apos;&amp;apos;. For monotonic languages, the tight upper bound is C^{2n-1}_n. We also found tight upper bounds for partially monotonic and nearly monotonic languages. For the other classes of languages, we found tight upper bounds for languages with small state complexities, and we exhibited languages with maximal known syntactic complexities. We conjecture these lower bounds to be tight upper bounds for these languages. &#xd;
&#xd;
We also observed that, for some subclasses C of regular languages, the upper bound on state complexity of the reversal operation on languages in C can be met by languages in C with maximal syntactic complexity. For R- and J-trivial regular languages, we also determined tight upper bounds on the state complexity of the reversal operation.</dim:field>
   <dim:field mdschema="dc" element="language" qualifier="iso" lang="en">en</dim:field>
   <dim:field mdschema="dc" element="publisher" lang="en">University of Waterloo</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">finite automaton</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">monoid</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">regular language</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">semigroup</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">state complexity</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">syntactic complexity</dim:field>
   <dim:field mdschema="dc" element="subject" qualifier="program" lang="en">Computer Science</dim:field>
   <dim:field mdschema="dc" element="title" lang="en">Syntactic Complexities of Nine Subclasses of Regular Languages</dim:field>
   <dim:field mdschema="dc" element="type" lang="en">Master Thesis</dim:field>
   <dim:field mdschema="dc" element="comment" qualifier="hidden" lang="en">Part of the work presented in this thesis has appeared in the following papers: &#xd;
&#xd;
Brzozowski, J., Li, B., Ye, Y.: Syntactic complexity of prefix-, suffix-, bifix-, and&#xd;
factor-free regular languages. Theoret. Comput. Sci. 449 (2012) 37 – 53&#xd;
&#xd;
Brzozowski, J., Li, B.: Syntactic complexities of some classes of star-free languages. In&#xd;
Kutrib, M., Moreira, N., Reis, R., eds.: 14th International Workshop on Descriptional&#xd;
Complexity of Formal Systems (DCFS). Volume 7386 of LNCS, Springer (2012) 117–&#xd;
129&#xd;
&#xd;
I have obtained licenses from Elsevier and Springer for reuse of the above publications in my thesis.</dim:field>
   <dim:field mdschema="dc" element="pending" lang="en">false</dim:field>
   <dim:field mdschema="uws-etd" element="degree" qualifier="department" lang="en">School of Computer Science</dim:field>
   <dim:field mdschema="uws-etd" element="degree" lang="en">Master of Mathematics</dim:field>
   <dim:field mdschema="uws" element="typeOfResource" lang="en">Text</dim:field>
   <dim:field mdschema="uws" element="peerReviewStatus" lang="en">Unreviewed</dim:field>
   <dim:field mdschema="uws" element="scholarLevel" lang="en">Graduate</dim:field>
   <dim:field mdschema="others" element="access-status">open.access</dim:field>
</dim:dim>
</metadata></record></GetRecord></OAI-PMH>