{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,11,14]],"date-time":"2023-11-14T03:15:41Z","timestamp":1699931741022},"reference-count":6,"publisher":"World Scientific Pub Co Pte Lt","issue":"05","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2005,10]]},"abstract":"<jats:p> We study a novel representation of semiautomata, which is motivated by the method of trace-assertion specifications of software modules. Each state of the semiautomaton is represented by an arbitrary word leading to that state, the canonical word. The transitions of the semiautomaton give rise to a right congruence, the state-equivalence, on the set of input words of the semiautomaton: two words are state-equivalent if and only if they lead to the same state. We present a simple algorithm for finding a set of generators for state-equivalence. Directly from this set of generators, we construct a confluent prefix-rewriting system which permits us to transform any word to its canonical representative. In general, the rewriting system may allow infinite derivations. To address this issue, we impose the condition of prefix-continuity on the set of canonical words. A set is prefix-continuous if, whenever a word w and a prefix u of w are in the set, then all the prefixes of w longer than u are also in the set. Prefix-continuous sets include prefix-free and prefix-closed sets as special cases. We prove that the rewriting system is Noetherian if and only if the set of canonical words is prefix-continuous. Furthermore, if the set of canonical words is prefix-continuous, then the set of rewriting rules is irredundant. We show that each prefix-continuous canonical set corresponds to a spanning forest of the semiautomaton. <\/jats:p>","DOI":"10.1142\/s0129054105003327","type":"journal-article","created":{"date-parts":[[2005,10,13]],"date-time":"2005-10-13T11:41:41Z","timestamp":1129203701000},"page":"831-850","source":"Crossref","is-referenced-by-count":8,"title":["REPRESENTATION OF SEMIAUTOMATA BY CANONICAL WORDS AND EQUIVALENCES"],"prefix":"10.1142","volume":"16","author":[{"given":"JANUSZ","family":"BRZOZOWSKI","sequence":"first","affiliation":[{"name":"School of Computer  Science, University of Waterloo, Waterloo, Ontario,  Canada N2L 3G1, Canada"}]},{"given":"HELMUT","family":"J\u00dcRGENSEN","sequence":"additional","affiliation":[{"name":"Department of Computer Science,  The University of Western Ontario, London, Ontario,  Canada, N6A 5B7, Canada"},{"name":"Institut f\u00fcr Informatik,  Universit\u00e4t Potsdam, August-Bebel-Str. 89,  14482 Potsdam, Germany"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-9771-7"},{"key":"rf4","first-page":"91","volume":"6","author":"B\u00fcchi J. R.","journal-title":"Archiv f\u00fcr Math. Logik und Grundlagen-forschung"},{"key":"rf5","volume-title":"Finite Automata, Their Algebras and Grammars","author":"B\u00fcchi J. R.","year":"1988"},{"key":"rf6","volume-title":"Algebraic Theory of Automata","author":"G\u00e9cseg F.","year":"1972"},{"key":"rf7","volume-title":"Algebraic Theory of Automata","author":"Ginzburg A.","year":"1968"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1109\/32.328996"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054105003327","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T00:41:08Z","timestamp":1565138468000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054105003327"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,10]]},"references-count":6,"journal-issue":{"issue":"05","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2005,10]]}},"alternative-id":["10.1142\/S0129054105003327"],"URL":"https:\/\/doi.org\/10.1142\/s0129054105003327","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,10]]}}}