Publication details
On a structural property in the state complexity of projected regular languages
| Authors | |
|---|---|
| Year of publication | 2012 |
| Type | Article in Periodical |
| Magazine / Source | Theoretical Computer Science |
| MU Faculty or unit | |
| Citation | |
| Web | http://dx.doi.org/10.1016/j.tcs.2012.04.009 |
| Doi | http://dx.doi.org/10.1016/j.tcs.2012.04.009 |
| Field | Informatics |
| Description | A transition is unobservable if it is labeled by a symbol removed by a projection. The present paper investigates a new structural property of incomplete deterministic finite automata - a number of states incident with an unobservable transition - and its effect on the state complexity of projected regular languages. We show that the known upper bound can be met only by automata with one unobservable transition (up to unobservable multi-transitions). We improve this upper bound by taking into consideration the structural property of minimal incomplete automata, and prove the tightness of new upper bounds. Special attention is focused on the case of finite languages. The paper also presents and discusses several fundamental problems which are still open. |