{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,24]],"date-time":"2025-09-24T10:17:53Z","timestamp":1758709073112},"reference-count":13,"publisher":"World Scientific Pub Co Pte Lt","issue":"04","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2006,8]]},"abstract":"<jats:p> We introduce and study three notions of typeness for automata on infinite words. For an acceptance-condition class \u03b3 (that is, \u03b3 is weak, B\u00fcchi, co-B\u00fcchi, Rabin, or Streett), deterministic \u03b3-typeness asks for the existence of an equivalent \u03b3-automaton on the same deterministic structure, nondeterministic \u03b3-typeness asks for the existence of an equivalent \u03b3-automaton on the same structure, and \u03b3-powerset-typeness asks for the existence of an equivalent \u03b3-automaton on the (deterministic) powerset structure \u2013 one obtained by applying the subset construction. The notions are helpful in studying the complexity and complication of translations between the various classes of automata. For example, we prove that deterministic B\u00fcchi automata are co-B\u00fcchi type; it follows that a translation from deterministic B\u00fcchi to deterministic co-B\u00fcchi automata, when exists, involves no blow up. On the other hand, we prove that nondeterministic B\u00fcchi automata are not co-B\u00fcchi type; it follows that a translation from a nondeterministic B\u00fcchi to nondeterministic co-B\u00fcchi automata, when exists, should be more complicated than just redefining the acceptance condition. As a third example, by proving that nondeterministic co-B\u00fcchi automata are B\u00fcchi-powerset type, we show that a translation of nondeterministic co-B\u00fcchi to deterministic B\u00fcchi automata, when exists, can be done applying the subset construction. We give a complete picture of typeness for the weak, B\u00fcchi, co-B\u00fcchi, Rabin, and Streett acceptance conditions, and discuss its usefulness. <\/jats:p>","DOI":"10.1142\/s0129054106004157","type":"journal-article","created":{"date-parts":[[2006,8,4]],"date-time":"2006-08-04T22:37:04Z","timestamp":1154731024000},"page":"869-883","source":"Crossref","is-referenced-by-count":12,"title":["TYPENESS FOR \u03c9-REGULAR AUTOMATA"],"prefix":"10.1142","volume":"17","author":[{"given":"ORNA","family":"KUPFERMAN","sequence":"first","affiliation":[{"name":"School of Engineering and Computer Science, Hebrew University, Jerusalem 91904, Israel"}]},{"given":"GILA","family":"MORGENSTERN","sequence":"additional","affiliation":[{"name":"School of Engineering and Computer Science, Hebrew University, Jerusalem 91904, Israel"}]},{"given":"ANIELLO","family":"MURANO","sequence":"additional","affiliation":[{"name":"Dipartimento di Informatica ed Applicazioni, Universit\u00e0 degli Studi di Salerno, 84081 Baronissi, Italy"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(85)90043-X"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-58325-4_202"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1145\/1055686.1055689"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1145\/333979.333987"},{"key":"rf10","volume-title":"Computer Aided Verification of Coordinating Processes","author":"Kurshan R. P.","year":"1994"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1007\/BF01691063"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(96)00312-X"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(66)80013-X"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(84)90049-5"},{"key":"rf18","first-page":"1","volume":"141","author":"Rabin M. O.","journal-title":"Transaction of the AMS"},{"key":"rf19","first-page":"115","volume":"3","author":"Rabin M. O.","journal-title":"IBM Journal of Research and Development"},{"key":"rf22","unstructured":"W.\u00a0Thomas, Handbook of Theoretical Computer Science (1990)\u00a0pp. 165\u2013191."},{"key":"rf24","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1994.1092"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054106004157","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T00:40:30Z","timestamp":1565138430000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054106004157"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,8]]},"references-count":13,"journal-issue":{"issue":"04","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2006,8]]}},"alternative-id":["10.1142\/S0129054106004157"],"URL":"https:\/\/doi.org\/10.1142\/s0129054106004157","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,8]]}}}