{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,5]],"date-time":"2022-04-05T07:49:24Z","timestamp":1649144964294},"reference-count":0,"publisher":"World Scientific Pub Co Pte Lt","issue":"01","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Algebra Comput."],"published-print":{"date-parts":[[1992,3]]},"abstract":"<jats:p> In this paper, we study the complexity of deciding code and monoid properties for regular sets specified by deterministic or nondeterministic finite automata. The results are as follows. The code problem for regular sets specified by deterministic or nondeterministic finite automata is NL-complete under NC<jats:sup>(1)<\/jats:sup> reducibilities. The problems of determining whether a regular set given by a deterministic finite automaton is a monoid or a free monoid or a finitely generated monoid are all NL-complete under NC<jats:sup>(1)<\/jats:sup> reducibilities. These monoid problems become PSPACE-complete if the regular sets are specified by nondeterministic finite automata instead. The maximal code problem for deterministic finite automata is shown to be in DET and NL-hard, while a PSPACE upper bound and NP-hardness lower bound hold for the case of nondeterministic finite automata. <\/jats:p>","DOI":"10.1142\/s0218196792000050","type":"journal-article","created":{"date-parts":[[2004,11,24]],"date-time":"2004-11-24T19:50:24Z","timestamp":1101325824000},"page":"39-55","source":"Crossref","is-referenced-by-count":0,"title":["THE COMPLEXITY OF DECIDING CODE AND MONOID PROPERTIES FOR REGULAR SETS"],"prefix":"10.1142","volume":"02","author":[{"given":"DUNG T.","family":"HUYNH","sequence":"first","affiliation":[{"name":"Computer Science Program, University of Texas at Dallas, Richardson, Texas 75083, USA"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"container-title":["International Journal of Algebra and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218196792000050","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T17:58:21Z","timestamp":1565114301000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218196792000050"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992,3]]},"references-count":0,"journal-issue":{"issue":"01","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[1992,3]]}},"alternative-id":["10.1142\/S0218196792000050"],"URL":"https:\/\/doi.org\/10.1142\/s0218196792000050","relation":{},"ISSN":["0218-1967","1793-6500"],"issn-type":[{"value":"0218-1967","type":"print"},{"value":"1793-6500","type":"electronic"}],"subject":[],"published":{"date-parts":[[1992,3]]}}}