# On a structural property in the state complexity of projected regular languages

##### Galina JiráskováGalina Jirásková,  Tomáš MasopustTomáš Masopust

Galina Jirásková, Tomáš Masopust
On a structural property in the state complexity of projected regular languages
Theoretical Computer Science, 449:93–105, 2012
• KurzfassungAbstract
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.
• Forschungsgruppe:Research Group: Wissensbasierte Systeme
```@article{JM2012,
author  = {Galina Jir{\'{a}}skov{\'{a}} and Tom{\'{a}}{\v{s}} Masopust},
title   = {On a structural property in the state complexity of projected
regular languages},
journal = {Theoretical Computer Science},
volume  = {449},
year    = {2012},
pages   = {93{\textendash}105},
doi     = {10.1016/j.tcs.2012.04.009}
}
```