{"id":{"repo_id":"mit","oai_identifier":"oai:dspace.mit.edu:1721.1/28559"},"canonical_url":"https://search.dev.ndltd.org/etd/mit/oai:dspace.mit.edu:1721.1/28559","repository":{"repo_id":"mit","name":"MIT","base_url":"https://dspace.mit.edu/oai/request"},"display":{"title":"On the power of nondeterminism in small two-way finite automata","abstract":"We examine the conjecture that one-way nondeterministic finite automata (NFAS) can be exponentially more succinct than two-way deterministic ones (2DFAS); equivalently, that no polynomial-size sequence of 2DFAs can recognize B, for B a particular sequence of regular languages that is among the hardest of those recognizable by polynomial-size sequences of 1NFAs. We prove that the most natural single-pass 2DFA algorithm for deciding B fails, \"single-pass\" meaning that the automaton is bound to terminate as soon as it reaches an endmarker for the first time. On the way, we introduce the notion of dilemmas as an interesting general tool for constructing hard inputs for 2DFAS.","abstract_html":"We examine the conjecture that one-way nondeterministic finite automata (NFAS) can be exponentially more succinct than two-way deterministic ones (2DFAS); equivalently, that no polynomial-size sequence of 2DFAs can recognize B, for B a particular sequence of regular languages that is among the hardest of those recognizable by polynomial-size sequences of 1NFAs. We prove that the most natural single-pass 2DFA algorithm for deciding B fails, "single-pass" meaning that the automaton is bound to terminate as soon as it reaches an endmarker for the first time. On the way, we introduce the notion of dilemmas as an interesting general tool for constructing hard inputs for 2DFAS.","abstract_has_math":false,"creators":["Kapoutsis, Christos, 1974-"],"institution":"Massachusetts Institute of Technology","degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":"Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science.","school":null,"contributors":[],"advisors":["Michael Sipser."],"committee_chairs":[],"committee_members":[],"year":2004,"date_issued":"2004","date_published":"2004","updated_at":"2026-07-22T22:22:21Z","subjects":["Electrical Engineering and Computer Science."],"languages":["en_US"],"rights":["M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission."],"rights_urls":["http://dspace.mit.edu/handle/1721.1/7582"],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/1721.1/28559","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Michael Sipser."]},{"key":"dc:contributor.department","label":"Department","values":["Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science."]},{"key":"dc:contributor.other","label":"Dc Contributor Other","values":["Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science."]},{"key":"dc:creator","label":"Author","values":["Kapoutsis, Christos, 1974-"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2005-09-27T17:00:32Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2005-09-27T17:00:32Z"]},{"key":"dc:date.issued","label":"Date","values":["2004"]},{"key":"dc:publisher","label":"Institution","values":["Massachusetts Institute of Technology"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Electrical Engineering and Computer Science."]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["en_US"]},{"key":"dc:rights","label":"Dc Rights","values":["M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission."]},{"key":"dc:rights.uri","label":"Rights URI","values":["http://dspace.mit.edu/handle/1721.1/7582"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["http://hdl.handle.net/1721.1/28559"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2004.","Includes bibliographical references (p. 25-26)."]},{"key":"dc:description.abstract","label":"Abstract","values":["We examine the conjecture that one-way nondeterministic finite automata (NFAS) can be exponentially more succinct than two-way deterministic ones (2DFAS); equivalently, that no polynomial-size sequence of 2DFAs can recognize B, for B a particular sequence of regular languages that is among the hardest of those recognizable by polynomial-size sequences of 1NFAs. We prove that the most natural single-pass 2DFA algorithm for deciding B fails, \"single-pass\" meaning that the automaton is bound to terminate as soon as it reaches an endmarker for the first time. On the way, we introduce the notion of dilemmas as an interesting general tool for constructing hard inputs for 2DFAS."]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["S.M."]},{"key":"dc:format.mimetype","label":"Dc Format Mimetype","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["On the power of nondeterminism in small two-way finite automata"]}]}],"canonical_facts":{"dc:contributor.advisor":["Michael Sipser."],"dc:contributor.department":["Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science."],"dc:contributor.other":["Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science."],"dc:creator":["Kapoutsis, Christos, 1974-"],"dc:date.accessioned":["2005-09-27T17:00:32Z"],"dc:date.available":["2005-09-27T17:00:32Z"],"dc:date.issued":["2004"],"dc:description":["Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2004.","Includes bibliographical references (p. 25-26)."],"dc:description.abstract":["We examine the conjecture that one-way nondeterministic finite automata (NFAS) can be exponentially more succinct than two-way deterministic ones (2DFAS); equivalently, that no polynomial-size sequence of 2DFAs can recognize B, for B a particular sequence of regular languages that is among the hardest of those recognizable by polynomial-size sequences of 1NFAs. We prove that the most natural single-pass 2DFA algorithm for deciding B fails, \"single-pass\" meaning that the automaton is bound to terminate as soon as it reaches an endmarker for the first time. On the way, we introduce the notion of dilemmas as an interesting general tool for constructing hard inputs for 2DFAS."],"dc:description.degree":["S.M."],"dc:format.mimetype":["application/pdf"],"dc:identifier.uri":["http://hdl.handle.net/1721.1/28559"],"dc:language.iso":["en_US"],"dc:publisher":["Massachusetts Institute of Technology"],"dc:rights":["M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission."],"dc:rights.uri":["http://dspace.mit.edu/handle/1721.1/7582"],"dc:subject":["Electrical Engineering and Computer Science."],"dc:title":["On the power of nondeterminism in small two-way finite automata"],"dc:type":["Thesis"]},"updated_at":"2026-07-22T22:22:21Z"}