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

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

ISSN: 0304-3975
Download
DOI Link

Galina Jirásková, Tomáš Masopust
On a structural property in the state complexity of projected regular languages
Theoretical Computer Science, 449:93–105, 2012

Details
Bibtex

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 SystemeKnowledge-Based Systems

@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}
}