{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:09:34Z","timestamp":1760202574921},"reference-count":16,"publisher":"World Scientific Pub Co Pte Lt","issue":"03","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2008,6]]},"abstract":"<jats:p> Bideterministic automata are deterministic automata with the property of their reversal automata also being deterministic. Bideterministic automata have previously been shown to be unique (up to an isomorphism) minimal NFAs with respect to the number of states. In this paper, we show that in addition to state minimality, bideterministic automata are also transition-minimal NFAs. However, as this transition minimality is not necessarily unique, we also present the necessary and sufficient conditions for a bideterministic automaton to be uniquely transition-minimal among NFAs. These results are obtained using the notion of the universal automaton. We also present some properties of the universal automaton. Furthermore, we show that bideterministic automata are transition-minimal \u220a-NFAs. <\/jats:p>","DOI":"10.1142\/s0129054108005887","type":"journal-article","created":{"date-parts":[[2008,6,3]],"date-time":"2008-06-03T10:27:20Z","timestamp":1212488840000},"page":"677-690","source":"Crossref","is-referenced-by-count":3,"title":["ON TRANSITION MINIMALITY OF BIDETERMINISTIC AUTOMATA"],"prefix":"10.1142","volume":"19","author":[{"given":"HELLIS","family":"TAMM","sequence":"first","affiliation":[{"name":"Institute of Cybernetics, Akadeemia tee 21, 12618 Tallinn, Estonia"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf1","first-page":"741","volume":"3","author":"Angluin D.","journal-title":"Journal of the Association for Computing Machinery"},{"key":"rf2","first-page":"166","volume":"47","author":"Arnold A.","journal-title":"Bull. EATCS"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(70)80025-3"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.07.035"},{"key":"rf7","volume-title":"Introduction to Automata Theory, Languages, and Computation","author":"Hopcroft J. E.","year":"1979"},{"key":"rf8","first-page":"519","volume":"7","author":"Hromkovic J.","journal-title":"Journal of Automata, Languages and Combinatorics"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1137\/0222067"},{"key":"rf13","first-page":"617","volume":"19","author":"Kameda T.","journal-title":"IEEE Trans. Comput. C"},{"key":"rf17","unstructured":"S.\u00a0Lombardy and J.\u00a0Sakarovitch, Logic and Automata: History and Perspectives. Volume 2 of Texts in Logic and Games, eds. J.\u00a0Flum, E.\u00a0Gradel and T.\u00a0Wilke (Amsterdam University Press, 2007)\u00a0pp. 457\u2013504."},{"key":"rf18","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(67)90481-0"},{"key":"rf19","first-page":"1211","volume":"20","author":"Moore F.","journal-title":"IEEE Trans. Comput. C"},{"key":"rf21","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054105003431"},{"key":"rf22","doi-asserted-by":"crossref","volume-title":"Elements of Automata Theory","author":"Sakarovitch J.","DOI":"10.1017\/CBO9781139195218"},{"key":"rf23","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00083-X"},{"key":"rf26","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.07.010"},{"key":"rf27","first-page":"471","volume":"64","author":"Yu S.","journal-title":"Fundamenta Informaticae"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054108005887","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T00:33:33Z","timestamp":1565138013000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054108005887"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,6]]},"references-count":16,"journal-issue":{"issue":"03","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2008,6]]}},"alternative-id":["10.1142\/S0129054108005887"],"URL":"https:\/\/doi.org\/10.1142\/s0129054108005887","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,6]]}}}