{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,29]],"date-time":"2022-03-29T03:01:46Z","timestamp":1648522906257},"reference-count":14,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2006,12,1]],"date-time":"2006-12-01T00:00:00Z","timestamp":1164931200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Form. Asp. Comput."],"published-print":{"date-parts":[[2006,12]]},"abstract":"Abstract<\/jats:title>\n \n In this paper, we analyze the problem of state minimization in a class of Finite State Automata called Two Start State Deterministic Finite State Automata (2-MDFAs). A 2-MDFA is similar to a deterministic finite state automaton (DFA), in that on a given input, each state has precisely one destination state; however, it differs from a DFA in that there are two start states.\n A string is accepted by a 2-MDFA if and only if there exists a transitional path from either start state to a finish state, on that string<\/jats:italic>\n . Observe that 2-MDFAs provide a limited amount of non-determinism and hence investigating their properties from the perspective of state minimization is a worthwhile pursuit. In case of unbounded non-determinism, i.e., Non-deterministic finite state automata (NFAs), it is well-known that the state minimization problem is PSPACE-complete [Jiang and Ravikumar in Proceedings of the 18th International Colloquium on Automata, Languages and Programming, ICALP\u201991, Madrid, Spain, July 8\u201312, 1991] and further that such automata can be exponentially more succinct than DFAs [Meyer and Fischer in Proceedings of the 12th SWAT(Annual Symposium on switching and automata theory), pp 188-191, 1971]. Even in the case of 2-MDFAs, the minimization problem remains non-trivial; indeed, Malcher in Theor Comput Sci 327(3):375\u2013390, 2004 shows that the corresponding decision problem is NP-complete. We focus on deriving approximability bounds for the state minimization problem in 2-MDFAs. Our main contribution in the current paper, is the design of an\n n<\/jats:italic>\n -approximation algorithm for state minimization in 2-MDFAs, where\n n<\/jats:italic>\n denotes the minimum number of states required to represent the input language as a 2-MDFA. We also present a proof that this bound is tight for our algorithm.\n <\/jats:p>","DOI":"10.1007\/s00165-006-0005-4","type":"journal-article","created":{"date-parts":[[2006,8,7]],"date-time":"2006-08-07T11:56:59Z","timestamp":1154951819000},"page":"421-431","source":"Crossref","is-referenced-by-count":0,"title":["An approximation algorithm for state minimization in 2-MDFAs"],"prefix":"10.1145","volume":"18","author":[{"given":"K.","family":"Subramani","sequence":"first","affiliation":[{"name":"Lane Department of Computer Science and Electrical Engineering, West Virginia University, 26506, Morgantown, WV, USA"}]},{"given":"C.","family":"Tauras","sequence":"additional","affiliation":[{"name":"Lane Department of Computer Science and Electrical Engineering, West Virginia University, 26506, Morgantown, WV, USA"}]}],"member":"320","reference":[{"key":"e_1_2_1_2_1_2","unstructured":"Crescenzi P Kann V. Approximation compendium. http:\/\/www.nada.kth.se\/\u02dcviggo\/wwwcompendium\/node242.html."},{"key":"e_1_2_1_2_2_2","volume-title":"Introduction to algorithms","author":"Cormen TH","year":"1992","edition":"2"},{"key":"e_1_2_1_2_3_2","volume-title":"Introduction to automata theory, language, and computation","author":"Hopcroft JE","year":"2001","edition":"2"},{"key":"e_1_2_1_2_4_2","doi-asserted-by":"publisher","DOI":"10.5555\/241938.241941"},{"key":"e_1_2_1_2_5_2","first-page":"186","volume-title":"Theory of Machines and Computations.","author":"Hopcroft JE","year":"1971"},{"key":"e_1_2_1_2_6_2","doi-asserted-by":"crossref","unstructured":"Jiang T Ravikumar B (1991) Minimal NFA problems are hard. In: Javier Leach Albert Mario Rodr\u00edguez Artalejo (eds) Proceedings of the 18th International Colloquium on Automata Languages and Programming ICALP\u201991 (Madrid Spain July 8\u201312 1991) vol 510 of LNCS pp 629\u2013640. Springer Berlin-G\u00f6ttingen-Heidelberg-New York","DOI":"10.1007\/3-540-54233-7_169"},{"key":"e_1_2_1_2_7_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(81)80005-9"},{"key":"e_1_2_1_2_8_2","unstructured":"Kennenth C. Louden (2002) Programming languages : principles and practice. Brooks\/Cole"},{"key":"e_1_2_1_2_9_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.03.070"},{"key":"e_1_2_1_2_10_2","doi-asserted-by":"crossref","unstructured":"Meyer and Fischer (1971) Economy of description by automata grammars and formal systems . In: FOCS: IEEE Symposium on Foundations of Computer Science (FOCS)","DOI":"10.1109\/SWAT.1971.11"},{"key":"e_1_2_1_2_11_2","doi-asserted-by":"crossref","unstructured":"Meyer A Fischer M (1971) Economies of description by automata grammars and formal systems. In: Proceedings of the 12th SWAT (Annual Symposium on Switching and Automata Theory) pp 188\u2013191","DOI":"10.1109\/SWAT.1971.11"},{"key":"e_1_2_1_2_12_2","doi-asserted-by":"publisher","DOI":"10.1137\/0218083"},{"key":"e_1_2_1_2_13_2","doi-asserted-by":"publisher","DOI":"10.1137\/0403025"},{"issue":"2","key":"e_1_2_1_2_14_2","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1016\/0304-3975(92)00011-F","article-title":"The state complexities of some basic operations on regular languages","volume":"125","author":"Sheng Yu","year":"1994","journal-title":"Theor Comput Sci"}],"container-title":["Formal Aspects of Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00165-006-0005-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00165-006-0005-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1007\/s00165-006-0005-4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,1,6]],"date-time":"2022-01-06T15:44:25Z","timestamp":1641483865000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1007\/s00165-006-0005-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,12]]},"references-count":14,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2006,12]]}},"alternative-id":["10.1007\/s00165-006-0005-4"],"URL":"http:\/\/dx.doi.org\/10.1007\/s00165-006-0005-4","relation":{},"ISSN":["0934-5043","1433-299X"],"issn-type":[{"value":"0934-5043","type":"print"},{"value":"1433-299X","type":"electronic"}],"subject":["Theoretical Computer Science","Software"],"published":{"date-parts":[[2006,12]]}}}