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

Aus International Center for Computational Logic
Wechseln zu:Navigation, Suche

Toggle side column

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

Galina JiráskováGalina Jirásková,  Tomáš MasopustTomáš Masopust
On a structural property in the state complexity of projected regular languages


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