Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/22105
Title: Reducibilities between Regular Languages
Authors: TAN WAI YEAN
Keywords: automata, transducer, reducible, injective, regular, languages
Issue Date: 22-Jul-2010
Source: TAN WAI YEAN (2010-07-22). Reducibilities between Regular Languages. ScholarBank@NUS Repository.
Abstract: The topic of this masters thesis is to investigate when a regular set A is reducible to a regular set B in the following sense: A is automaton reducible to B if there is an automatic and injective function f mapping A to B. A is transducer reducible to B if there is a function f mapping A to B where f can computed by a finite nondeterministic transducer. One of the central questions investigated is whether it holds for every two regular languages that they are comparable under the given reduction. For the first reducibility, it is shown that any two polynomial sized regular sets are comparable and every polynomial sized regular set is reducible to every exponential sized regular set. Comparability between two exponential sized regular sets remains an open problem. For the second reducibility, it is shown that any two regular sets are comparable and exponential sized regular sets form a single equivalence class under this reducibility.
URI: http://scholarbank.nus.edu.sg/handle/10635/22105
Appears in Collections:Master's Theses (Open)

Show full item record
Files in This Item:
File Description SizeFormatAccess SettingsVersion 
TanWY.pdf490.46 kBAdobe PDF

OPEN

NoneView/Download

Page view(s)

240
checked on Dec 11, 2017

Download(s)

224
checked on Dec 11, 2017

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.