<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html>
<head>
<title>UTas ePrints - Labeled directed graphs and FSA as classifiers of strings</title>
<script type="text/javascript" src="http://eprints.utas.edu.au/javascript/auto.js"><!-- padder --></script>
<style type="text/css" media="screen">@import url(http://eprints.utas.edu.au/style/auto.css);</style>
<style type="text/css" media="print">@import url(http://eprints.utas.edu.au/style/print.css);</style>
<link rel="icon" href="/images/eprints/favicon.ico" type="image/x-icon" />
<link rel="shortcut icon" href="/images/eprints/favicon.ico" type="image/x-icon" />
<link rel="Top" href="http://eprints.utas.edu.au/" />
<link rel="Search" href="http://eprints.utas.edu.au/cgi/search" />
<meta content="Kelarev, Andrei" name="eprints.creators_name" />
<meta content="Kang, Byeong Ho" name="eprints.creators_name" />
<meta content="Sale, Arthur" name="eprints.creators_name" />
<meta content="Williams, Raymond" name="eprints.creators_name" />
<meta content="conference_item" name="eprints.type" />
<meta content="2007-02-08" name="eprints.datestamp" />
<meta content="2008-01-08 15:30:00" name="eprints.lastmod" />
<meta content="show" name="eprints.metadata_visibility" />
<meta content="Labeled directed graphs and FSA as classifiers of strings" name="eprints.title" />
<meta content="pub" name="eprints.ispublished" />
<meta content="280201" name="eprints.subjects" />
<meta content="280207" name="eprints.subjects" />
<meta content="public" name="eprints.full_text_status" />
<meta content="paper" name="eprints.pres_type" />
<meta content="The classical concept of a finite state automaton (FSA) has long been used in computer science to classify formal languages regarded as sets of strings. This paper surveys and unifies recent results on strings recognized by FSA defined by labeled directed graphs, and highlights several interesting open questions. In particular, one of our open questions deals with a new method of applying a related construction to classification" name="eprints.abstract" />
<meta content="2006-07" name="eprints.date" />
<meta content="published" name="eprints.date_type" />
<meta content="17" name="eprints.pages" />
<meta content="17th Australasian Workshop on Combinatorial Algorithms (AWOCA 2006)" name="eprints.event_title" />
<meta content="Uluru, Australia" name="eprints.event_location" />
<meta content="13-16 Jul 2006" name="eprints.event_dates" />
<meta content="workshop" name="eprints.event_type" />
<meta content="UNSPECIFIED" name="eprints.thesis_type" />
<meta content="TRUE" name="eprints.refereed" />
<meta content="Kelarev, Andrei and Kang, Byeong Ho and Sale, Arthur and Williams, Raymond (2006) Labeled directed graphs and FSA as classifiers of strings. In: 17th Australasian Workshop on Combinatorial Algorithms (AWOCA 2006), 13-16 Jul 2006, Uluru, Australia." name="eprints.citation" />
<meta content="http://eprints.utas.edu.au/722/1/AWOCA06-Plant_Science.pdf" name="eprints.document_url" />
<link rel="schema.DC" href="http://purl.org/DC/elements/1.0/" />
<meta content="Labeled directed graphs and FSA as classifiers of strings" name="DC.title" />
<meta content="Kelarev, Andrei" name="DC.creator" />
<meta content="Kang, Byeong Ho" name="DC.creator" />
<meta content="Sale, Arthur" name="DC.creator" />
<meta content="Williams, Raymond" name="DC.creator" />
<meta content="280201 Expert Systems" name="DC.subject" />
<meta content="280207 Pattern Recognition" name="DC.subject" />
<meta content="The classical concept of a finite state automaton (FSA) has long been used in computer science to classify formal languages regarded as sets of strings. This paper surveys and unifies recent results on strings recognized by FSA defined by labeled directed graphs, and highlights several interesting open questions. In particular, one of our open questions deals with a new method of applying a related construction to classification" name="DC.description" />
<meta content="2006-07" name="DC.date" />
<meta content="Conference or Workshop Item" name="DC.type" />
<meta content="PeerReviewed" name="DC.type" />
<meta content="application/pdf" name="DC.format" />
<meta content="http://eprints.utas.edu.au/722/1/AWOCA06-Plant_Science.pdf" name="DC.identifier" />
<meta content="Kelarev, Andrei and Kang, Byeong Ho and Sale, Arthur and Williams, Raymond (2006) Labeled directed graphs and FSA as classifiers of strings. In: 17th Australasian Workshop on Combinatorial Algorithms (AWOCA 2006), 13-16 Jul 2006, Uluru, Australia." name="DC.identifier" />
<meta content="http://eprints.utas.edu.au/722/" name="DC.relation" />
<link rel="alternate" href="http://eprints.utas.edu.au/cgi/export/722/BibTeX/epprod-eprint-722.bib" title="BibTeX" type="text/plain" />
<link rel="alternate" href="http://eprints.utas.edu.au/cgi/export/722/ContextObject/epprod-eprint-722.xml" title="OpenURL ContextObject" type="text/xml" />
<link rel="alternate" href="http://eprints.utas.edu.au/cgi/export/722/ContextObject::Dissertation/epprod-eprint-722.xml" title="OpenURL Dissertation" type="text/xml" />
<link rel="alternate" href="http://eprints.utas.edu.au/cgi/export/722/ContextObject::Journal/epprod-eprint-722.xml" title="OpenURL Journal" type="text/xml" />
<link rel="alternate" href="http://eprints.utas.edu.au/cgi/export/722/DC/epprod-eprint-722.txt" title="Dublin Core" type="text/plain" />
<link rel="alternate" href="http://eprints.utas.edu.au/cgi/export/722/DIDL/epprod-eprint-722.xml" title="DIDL" type="text/xml" />
<link rel="alternate" href="http://eprints.utas.edu.au/cgi/export/722/EndNote/epprod-eprint-722.enw" title="EndNote" type="text/plain" />
<link rel="alternate" href="http://eprints.utas.edu.au/cgi/export/722/HTML/epprod-eprint-722.html" title="HTML Citation" type="text/html; charset=utf-8" />
<link rel="alternate" href="http://eprints.utas.edu.au/cgi/export/722/METS/epprod-eprint-722.xml" title="METS" type="text/xml" />
<link rel="alternate" href="http://eprints.utas.edu.au/cgi/export/722/MODS/epprod-eprint-722.xml" title="MODS" type="text/xml" />
<link rel="alternate" href="http://eprints.utas.edu.au/cgi/export/722/RIS/epprod-eprint-722.ris" title="Reference Manager" type="text/plain" />
<link rel="alternate" href="http://eprints.utas.edu.au/cgi/export/722/Refer/epprod-eprint-722.refer" title="Refer" type="text/plain" />
<link rel="alternate" href="http://eprints.utas.edu.au/cgi/export/722/Simple/epprod-eprint-722text" title="Simple Metadata" type="text/plain" />
<link rel="alternate" href="http://eprints.utas.edu.au/cgi/export/722/Text/epprod-eprint-722.txt" title="ASCII Citation" type="text/plain; charset=utf-8" />
<link rel="alternate" href="http://eprints.utas.edu.au/cgi/export/722/XML/epprod-eprint-722.xml" title="EP3 XML" type="text/xml" />
</head>
<body bgcolor="#ffffff" text="#000000" onLoad="loadRoutine(); MM_preloadImages('images/eprints/ePrints_banner_r5_c5_f2.gif','images/eprints/ePrints_banner_r5_c7_f2.gif','images/eprints/ePrints_banner_r5_c8_f2.gif','images/eprints/ePrints_banner_r5_c9_f2.gif','images/eprints/ePrints_banner_r5_c10_f2.gif','images/eprints/ePrints_banner_r5_c11_f2.gif','images/eprints/ePrints_banner_r6_c4_f2.gif')">
<div class="ep_noprint"><noscript><style type="text/css">@import url(http://eprints.utas.edu.au/style/nojs.css);</style></noscript></div>
<table width="795" border="0" cellspacing="0" cellpadding="0">
<tr>
<td><script language="JavaScript1.2">mmLoadMenus();</script>
<table border="0" cellpadding="0" cellspacing="0" width="795">
<!-- fwtable fwsrc="eprints_banner_final2.png" fwbase="ePrints_banner.gif" fwstyle="Dreamweaver" fwdocid = "1249563342" fwnested="0" -->
<tr>
<td><img src="/images/eprints/spacer.gif" width="32" height="1" border="0" alt="" /></td>
<td><img src="/images/eprints/spacer.gif" width="104" height="1" border="0" alt="" /></td>
<td><img src="/images/eprints/spacer.gif" width="44" height="1" border="0" alt="" /></td>
<td><img src="/images/eprints/spacer.gif" width="105" height="1" border="0" alt="" /></td>
<td><img src="/images/eprints/spacer.gif" width="41" height="1" border="0" alt="" /></td>
<td><img src="/images/eprints/spacer.gif" width="16" height="1" border="0" alt="" /></td>
<td><img src="/images/eprints/spacer.gif" width="68" height="1" border="0" alt="" /></td>
<td><img src="/images/eprints/spacer.gif" width="68" height="1" border="0" alt="" /></td>
<td><img src="/images/eprints/spacer.gif" width="68" height="1" border="0" alt="" /></td>
<td><img src="/images/eprints/spacer.gif" width="82" height="1" border="0" alt="" /></td>
<td><img src="/images/eprints/spacer.gif" width="69" height="1" border="0" alt="" /></td>
<td><img src="/images/eprints/spacer.gif" width="98" height="1" border="0" alt="" /></td>
<td><img src="/images/eprints/spacer.gif" width="1" height="1" border="0" alt="" /></td>
</tr>
<tr>
<td colspan="12"><img name="ePrints_banner_r1_c1" src="/images/eprints/ePrints_banner_r1_c1.gif" width="795" height="10" border="0" alt="" /></td>
<td><img src="/images/eprints/spacer.gif" width="1" height="10" border="0" alt="" /></td>
</tr>
<tr>
<td rowspan="6"><img name="ePrints_banner_r2_c1" src="/images/eprints/ePrints_banner_r2_c1.gif" width="32" height="118" border="0" alt="" /></td>
<td rowspan="5"><a href="http://www.utas.edu.au/"><img name="ePrints_banner_r2_c2" src="/images/eprints/ePrints_banner_r2_c2.gif" width="104" height="103" border="0" alt="" /></a></td>
<td colspan="10"><img name="ePrints_banner_r2_c3" src="/images/eprints/ePrints_banner_r2_c3.gif" width="659" height="41" border="0" alt="" /></td>
<td><img src="/images/eprints/spacer.gif" width="1" height="41" border="0" alt="" /></td>
</tr>
<tr>
<td colspan="3"><a href="http://eprints.utas.edu.au/"><img name="ePrints_banner_r3_c3" src="/images/eprints/ePrints_banner_r3_c3.gif" width="190" height="31" border="0" alt="" /></a></td>
<td rowspan="2" colspan="7"><img name="ePrints_banner_r3_c6" src="/images/eprints/ePrints_banner_r3_c6.gif" width="469" height="37" border="0" alt="" /></td>
<td><img src="/images/eprints/spacer.gif" width="1" height="31" border="0" alt="" /></td>
</tr>
<tr>
<td colspan="3"><img name="ePrints_banner_r4_c3" src="/images/eprints/ePrints_banner_r4_c3.gif" width="190" height="6" border="0" alt="" /></td>
<td><img src="/images/eprints/spacer.gif" width="1" height="6" border="0" alt="" /></td>
</tr>
<tr>
<td colspan="2"><img name="ePrints_banner_r5_c3" src="/images/eprints/ePrints_banner_r5_c3.gif" width="149" height="1" border="0" alt="" /></td>
<td rowspan="2" colspan="2"><a href="/information.html" onMouseOut="MM_swapImgRestore();MM_startTimeout()" onMouseOver="MM_showMenu(window.mm_menu_0821132634_0,0,25,null,'ePrints_banner_r5_c5');MM_swapImage('ePrints_banner_r5_c5','','/images/eprints/ePrints_banner_r5_c5_f2.gif',1);"><img name="ePrints_banner_r5_c5" src="/images/eprints/ePrints_banner_r5_c5.gif" width="57" height="25" border="0" alt="About" /></a></td>
<td rowspan="2"><a href="/view/" onMouseOut="MM_swapImgRestore();MM_startTimeout()" onMouseOver="MM_showMenu(window.mm_menu_0821133021_1,0,25,null,'ePrints_banner_r5_c7');MM_swapImage('ePrints_banner_r5_c7','','/images/eprints/ePrints_banner_r5_c7_f2.gif',1);"><img name="ePrints_banner_r5_c7" src="/images/eprints/ePrints_banner_r5_c7.gif" width="68" height="25" border="0" alt="Browse" /></a></td>
<td rowspan="2"><a href="/perl/search/simple" onMouseOut="MM_swapImgRestore();MM_startTimeout()" onMouseOver="MM_showMenu(window.mm_menu_0821133201_2,0,25,null,'ePrints_banner_r5_c8');MM_swapImage('ePrints_banner_r5_c8','','/images/eprints/ePrints_banner_r5_c8_f2.gif',1);"><img name="ePrints_banner_r5_c8" src="/images/eprints/ePrints_banner_r5_c8.gif" width="68" height="25" border="0" alt="Search" /></a></td>
<td rowspan="2"><a href="/perl/register" onMouseOut="MM_swapImgRestore();MM_startTimeout();" onMouseOver="MM_showMenu(window.mm_menu_1018171924_3,0,25,null,'ePrints_banner_r5_c9');MM_swapImage('ePrints_banner_r5_c9','','/images/eprints/ePrints_banner_r5_c9_f2.gif',1);"><img name="ePrints_banner_r5_c9" src="/images/eprints/ePrints_banner_r5_c9.gif" width="68" height="25" border="0" alt="register" /></a></td>
<td rowspan="2"><a href="/perl/users/home" onMouseOut="MM_swapImgRestore();MM_startTimeout()" onMouseOver="MM_showMenu(window.mm_menu_0821133422_4,0,25,null,'ePrints_banner_r5_c10');MM_swapImage('ePrints_banner_r5_c10','','/images/eprints/ePrints_banner_r5_c10_f2.gif',1);"><img name="ePrints_banner_r5_c10" src="/images/eprints/ePrints_banner_r5_c10.gif" width="82" height="25" border="0" alt="user area" /></a></td>
<td rowspan="2"><a href="/help/" onMouseOut="MM_swapImgRestore();MM_startTimeout()" onMouseOver="MM_showMenu(window.mm_menu_0821133514_5,0,25,null,'ePrints_banner_r5_c11');MM_swapImage('ePrints_banner_r5_c11','','/images/eprints/ePrints_banner_r5_c11_f2.gif',1);"><img name="ePrints_banner_r5_c11" src="/images/eprints/ePrints_banner_r5_c11.gif" width="69" height="25" border="0" alt="Help" /></a></td>
<td rowspan="3" colspan="4"><img name="ePrints_banner_r5_c12" src="/images/eprints/ePrints_banner_r5_c12.gif" width="98" height="40" border="0" alt="" /></td>
<td><img src="/images/eprints/spacer.gif" width="1" height="1" border="0" alt="" /></td>
</tr>
<tr>
<td rowspan="2"><img name="ePrints_banner_r6_c3" src="/images/eprints/ePrints_banner_r6_c3.gif" width="44" height="39" border="0" alt="ePrints home" /></td>
<td><a href="/" onMouseOut="MM_swapImgRestore()" onMouseOver="MM_swapImage('ePrints_banner_r6_c4','','/images/eprints/ePrints_banner_r6_c4_f2.gif',1);"><img name="ePrints_banner_r6_c4" src="/images/eprints/ePrints_banner_r6_c4.gif" width="105" height="24" border="0" alt="ePrints home" /></a></td>
<td><img src="/images/eprints/spacer.gif" width="1" height="24" border="0" alt="" /></td>
</tr>
<tr>
<td><img name="ePrints_banner_r7_c2" src="/images/eprints/ePrints_banner_r7_c2.gif" width="104" height="15" border="0" alt="" /></td>
<td colspan="8"><img name="ePrints_banner_r7_c4" src="/images/eprints/ePrints_banner_r7_c4.gif" width="517" height="15" border="0" alt="" /></td>
<td><img src="/images/eprints/spacer.gif" width="1" height="15" border="0" alt="" /></td>
</tr>
</table></td>
</tr>
<tr><td><table width="100%" style="font-size: 90%; border: solid 1px #ccc; padding: 3px"><tr>
<td align="left"><a href="http://eprints.utas.edu.au/cgi/users/home">Login</a> | <a href="http://eprints.utas.edu.au/cgi/register">Create Account</a></td>
<td align="right" style="white-space: nowrap">
<form method="get" accept-charset="utf-8" action="http://eprints.utas.edu.au/cgi/search" style="display:inline">
<input class="ep_tm_searchbarbox" size="20" type="text" name="q" />
<input class="ep_tm_searchbarbutton" value="Search" type="submit" name="_action_search" />
<input type="hidden" name="_order" value="bytitle" />
<input type="hidden" name="basic_srchtype" value="ALL" />
<input type="hidden" name="_satisfyall" value="ALL" />
</form>
</td>
</tr></table></td></tr>
<tr>
<td class="toplinks"><!-- InstanceBeginEditable name="content" -->
<div align="center">
<table width="720" class="ep_tm_main"><tr><td align="left">
<h1 class="ep_tm_pagetitle">Labeled directed graphs and FSA as classifiers of strings</h1>
<p style="margin-bottom: 1em" class="not_ep_block"><span class="person_name">Kelarev, Andrei</span> and <span class="person_name">Kang, Byeong Ho</span> and <span class="person_name">Sale, Arthur</span> and <span class="person_name">Williams, Raymond</span> (2006) <xhtml:em>Labeled directed graphs and FSA as classifiers of strings.</xhtml:em> In: 17th Australasian Workshop on Combinatorial Algorithms (AWOCA 2006), 13-16 Jul 2006, Uluru, Australia.</p><p style="margin-bottom: 1em" class="not_ep_block"></p><table style="margin-bottom: 1em" class="not_ep_block"><tr><td valign="top" style="text-align:center"><a onmouseover="EPJS_ShowPreview( event, 'doc_preview_732' );" href="http://eprints.utas.edu.au/722/1/AWOCA06-Plant_Science.pdf" onmouseout="EPJS_HidePreview( event, 'doc_preview_732' );"><img alt="[img]" src="http://eprints.utas.edu.au/style/images/fileicons/application_pdf.png" class="ep_doc_icon" border="0" /></a><div class="ep_preview" id="doc_preview_732"><table><tr><td><img alt="" src="http://eprints.utas.edu.au/722/thumbnails/1/preview.png" class="ep_preview_image" border="0" /><div class="ep_preview_title">Preview</div></td></tr></table></div></td><td valign="top"><a href="http://eprints.utas.edu.au/722/1/AWOCA06-Plant_Science.pdf"><span class="ep_document_citation">PDF</span></a> - Requires a PDF viewer<br />204Kb</td></tr></table><div class="not_ep_block"><h2>Abstract</h2><p style="padding-bottom: 16px; text-align: left; margin: 1em auto 0em auto">The classical concept of a finite state automaton (FSA) has long been used in computer science to classify formal languages regarded as sets of strings. This paper surveys and unifies recent results on strings recognized by FSA defined by labeled directed graphs, and highlights several interesting open questions. In particular, one of our open questions deals with a new method of applying a related construction to classification</p></div><table style="margin-bottom: 1em" cellpadding="3" class="not_ep_block" border="0"><tr><th valign="top" class="ep_row">Item Type:</th><td valign="top" class="ep_row">Conference or Workshop Item (Paper)</td></tr><tr><th valign="top" class="ep_row">Subjects:</th><td valign="top" class="ep_row"><a href="http://eprints.utas.edu.au/view/subjects/280201.html">280000 Information, Computing and Communication Sciences > 280200 Artificial Intelligence and Signal and Image Processing > 280201 Expert Systems</a><br /><a href="http://eprints.utas.edu.au/view/subjects/280207.html">280000 Information, Computing and Communication Sciences > 280200 Artificial Intelligence and Signal and Image Processing > 280207 Pattern Recognition</a></td></tr><tr><th valign="top" class="ep_row">ID Code:</th><td valign="top" class="ep_row">722</td></tr><tr><th valign="top" class="ep_row">Deposited By:</th><td valign="top" class="ep_row"><span class="ep_name_citation"><span class="person_name">Dr Byeong Ho Kang</span></span></td></tr><tr><th valign="top" class="ep_row">Deposited On:</th><td valign="top" class="ep_row">08 Feb 2007</td></tr><tr><th valign="top" class="ep_row">Last Modified:</th><td valign="top" class="ep_row">09 Jan 2008 02:30</td></tr><tr><th valign="top" class="ep_row">ePrint Statistics:</th><td valign="top" class="ep_row"><a target="ePrintStats" href="/es/index.php?action=show_detail_eprint;id=722;">View statistics for this ePrint</a></td></tr></table><p align="right">Repository Staff Only: <a href="http://eprints.utas.edu.au/cgi/users/home?screen=EPrint::View&eprintid=722">item control page</a></p>
</td></tr></table>
</div>
<!-- InstanceEndEditable --></td>
</tr>
<tr>
<td><!-- #BeginLibraryItem "/Library/footer_eprints.lbi" -->
<table width="795" border="0" align="left" cellpadding="0" class="footer">
<tr valign="top">
<td colspan="2"><div align="center"><a href="http://www.utas.edu.au">UTAS home</a> | <a href="http://www.utas.edu.au/library/">Library home</a> | <a href="/">ePrints home</a> | <a href="/contact.html">contact</a> | <a href="/information.html">about</a> | <a href="/view/">browse</a> | <a href="/perl/search/simple">search</a> | <a href="/perl/register">register</a> | <a href="/perl/users/home">user area</a> | <a href="/help/">help</a></div><br /></td>
</tr>
<tr><td colspan="2"><p><img src="/images/eprints/footerline.gif" width="100%" height="4" /></p></td></tr>
<tr valign="top">
<td width="68%" class="footer">Authorised by the University Librarian<br />
© University of Tasmania ABN 30 764 374 782<br />
<a href="http://www.utas.edu.au/cricos/">CRICOS Provider Code 00586B</a> | <a href="http://www.utas.edu.au/copyright/copyright_disclaimers.html">Copyright & Disclaimers</a> | <a href="http://www.utas.edu.au/accessibility/index.html">Accessibility</a> | <a href="http://eprints.utas.edu.au/feedback/">Site Feedback</a> </td>
<td width="32%"><div align="right">
<p align="right" class="NoPrint"><a href="http://www.utas.edu.au/"><img src="http://www.utas.edu.au/shared/logos/unioftasstrip.gif" alt="University of Tasmania Home Page" width="260" height="16" border="0" align="right" /></a></p>
<p align="right" class="NoPrint"><a href="http://www.utas.edu.au/"><br />
</a></p>
</div></td>
</tr>
<tr valign="top">
<td><p> </p></td>
<td><div align="right"><span class="NoPrint"><a href="http://www.eprints.org/software/"><img src="/images/eprintslogo.gif" alt="ePrints logo" width="77" height="29" border="0" align="bottom" /></a></span></div></td>
</tr>
</table>
<!-- #EndLibraryItem -->
<div align="center"></div></td>
</tr>
</table>
</body>
</html>
