Algorithms and lower bounds in finite automata size complexity
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2006.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2007
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/37891 |
| _version_ | 1811086171870068736 |
|---|---|
| author | Kapoutsis, Christos, 1974- |
| author2 | Michael Sipser. |
| author_facet | Michael Sipser. Kapoutsis, Christos, 1974- |
| author_sort | Kapoutsis, Christos, 1974- |
| collection | MIT |
| description | Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2006. |
| first_indexed | 2024-09-23T13:21:57Z |
| format | Thesis |
| id | mit-1721.1/37891 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T13:21:57Z |
| publishDate | 2007 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/378912019-04-10T12:50:29Z Algorithms and lower bounds in finite automata size complexity Kapoutsis, Christos, 1974- Michael Sipser. Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science. Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science. Electrical Engineering and Computer Science. Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2006. Includes bibliographical references (p. 97-99). In this thesis we investigate the relative succinctness of several types of finite automata, focusing mainly on the following four basic models: one-way deterministic (1)FAs), one-way nondeterministic (1NFAs), two-way deterministic (2DFAS), and two-way nondeterministic (2NFAS). First, we establish the exact values of the trade-offs for all conversions from two-way to one-way automata. Specifically, we prove that the functions ... return the exact values of the trade-offs from 2DFAS to 1DFAS, from 2NFAS to 1DFAs, and from 2DFAs or 2NFAS to 1NFAs, respectively. Second, we examine the question whether the trade-offs from NFAs or 2NFAS to 2DiFAs are polynomial or not. We prove two theorems for liveness, the complete problem for the conversion from 1NFAS to 2DFAS. We first focus on moles, a restricted class of 2NFAs that includes the polynomially large 1NFAS which solve liveness. We prove that, in contrast, 2DFA moles cannot solve liveness, irrespective of size. (cont.) We then focus on sweeping 2NFAS, which can change the direction of their input head only on the end-markers. We prove that all sweeping 2NFAs solving the complement of liveness are of exponential size. A simple modification of this argument also proves that the trade-off from 2DFAS to sweeping 2NFAS is exponential. Finally, we examine conversions between two-way automata with more than one head-like devices (e.g., heads, linearly bounded counters, pebbles). We prove that, if the automata of some type A have enough resources to (i) solve problems that no automaton of some other type B can solve, and (ii) simulate any unary 2DFA that has additional access to a linearly-bounded counter, then the trade-off from automata of type A to automata of type B admits no recursive upper bound. by Christos Kapoutsis. Ph.D. 2007-07-18T13:04:56Z 2007-07-18T13:04:56Z 2006 2006 Thesis http://hdl.handle.net/1721.1/37891 131320384 eng 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. http://dspace.mit.edu/handle/1721.1/7582 99 p. application/pdf Massachusetts Institute of Technology |
| spellingShingle | Electrical Engineering and Computer Science. Kapoutsis, Christos, 1974- Algorithms and lower bounds in finite automata size complexity |
| title | Algorithms and lower bounds in finite automata size complexity |
| title_full | Algorithms and lower bounds in finite automata size complexity |
| title_fullStr | Algorithms and lower bounds in finite automata size complexity |
| title_full_unstemmed | Algorithms and lower bounds in finite automata size complexity |
| title_short | Algorithms and lower bounds in finite automata size complexity |
| title_sort | algorithms and lower bounds in finite automata size complexity |
| topic | Electrical Engineering and Computer Science. |
| url | http://hdl.handle.net/1721.1/37891 |
| work_keys_str_mv | AT kapoutsischristos1974 algorithmsandlowerboundsinfiniteautomatasizecomplexity |