{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,5,19]],"date-time":"2022-05-19T03:12:21Z","timestamp":1652929941789},"reference-count":11,"publisher":"World Scientific Pub Co Pte Ltd","issue":"03n04","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2022,4]]},"abstract":"<jats:p> Unary self-verifying symmetric difference automata have a known tight bound of [Formula: see text] for their state complexity. We now consider the non-unary case and show that, for every [Formula: see text], there is a regular language [Formula: see text] accepted by a non-unary self-verifying symmetric difference nondeterministic automaton with [Formula: see text] states, such that its equivalent minimal deterministic finite automaton has [Formula: see text] states. Furthermore, given any SV-XNFA with [Formula: see text] states, it is possible, up to isomorphism, to find at most another [Formula: see text] equivalent SV-XNFA. Finally, we show that for a certain set of non-unary SV-XNFA, [Formula: see text] is a tight bound on the state complexity. <\/jats:p>","DOI":"10.1142\/s0129054122410076","type":"journal-article","created":{"date-parts":[[2022,5,15]],"date-time":"2022-05-15T03:40:05Z","timestamp":1652586005000},"page":"313-333","source":"Crossref","is-referenced-by-count":0,"title":["Descriptional Complexity of Non-Unary Self-Verifying Symmetric Difference Automata"],"prefix":"10.1142","volume":"33","author":[{"given":"Laurette","family":"Marais","sequence":"first","affiliation":[{"name":"Meraka Institute, CSIR, Pretoria, South Africa"},{"name":"Department of Computer Science, Stellenbosch University, Stellenbosch, South Africa"}]},{"given":"Lynette","family":"van Zijl","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Stellenbosch University, Stellenbosch, South Africa"}]}],"member":"219","published-online":{"date-parts":[[2022,5,12]]},"reference":[{"key":"S0129054122410076BIB001","doi-asserted-by":"publisher","DOI":"10.1051\/ita:2007017"},{"key":"S0129054122410076BIB002","volume-title":"Applied Modern Algebra","author":"Dornhoff L. L.","year":"1978"},{"key":"S0129054122410076BIB003","volume-title":"Introduction to Automata Theory, Languages, and Computation","author":"Hopcroft J. E.","year":"2013","edition":"3"},{"key":"S0129054122410076BIB004","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-48523-6_40"},{"key":"S0129054122410076BIB005","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2010.11.017"},{"key":"S0129054122410076BIB006","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-41114-9_14"},{"key":"S0129054122410076BIB007","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-60252-3_20"},{"key":"S0129054122410076BIB008","volume-title":"Discrete Mathematical Structures and their Applications","author":"Stone H. S.","year":"1973"},{"key":"S0129054122410076BIB009","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31623-4_24"},{"key":"S0129054122410076BIB010","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.07.012"},{"key":"S0129054122410076BIB011","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02979-0_6"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054122410076","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,5,19]],"date-time":"2022-05-19T02:57:31Z","timestamp":1652929051000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/10.1142\/S0129054122410076"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,4]]},"references-count":11,"journal-issue":{"issue":"03n04","published-print":{"date-parts":[[2022,4]]}},"alternative-id":["10.1142\/S0129054122410076"],"URL":"https:\/\/doi.org\/10.1142\/s0129054122410076","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,4]]}}}