State Complexity of Projected Languages

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

Toggle side column

State Complexity of Projected Languages

Galina JiráskováGalina Jirásková,  Tomáš MasopustTomáš Masopust
State Complexity of Projected Languages


Galina Jirásková, Tomáš Masopust
State Complexity of Projected Languages
In M. Holzer, M. Kutrib, G. Pighizzini, eds., Proc. of 13th International Workshop on Descriptional Complexity of Formal Systems (DCFS), volume 6808 of LNCS, 198-211, 2011. Springer
  • KurzfassungAbstract
    This paper discusses the state complexity of projected regular languages represented by incomplete deterministic finite automata. It is shown that the known upper bound is reachable only by automata with one unobservable transition, that is, a transition labeled with a symbol removed by the projection. The present paper improves this upper bound by considering the structure of the automaton. It also proves that the new bounds are tight, considers the case of finite languages, and presents several open problems.
  • Forschungsgruppe:Research Group: Wissensbasierte SystemeKnowledge-Based Systems
The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-642-22600-7_16.
@inproceedings{JM2011,
  author    = {Galina Jir{\'{a}}skov{\'{a}} and Tom{\'{a}}{\v{s}} Masopust},
  title     = {State Complexity of Projected Languages},
  editor    = {M. Holzer and M. Kutrib and G. Pighizzini},
  booktitle = {Proc. of 13th International Workshop on Descriptional Complexity
               of Formal Systems (DCFS)},
  series    = {LNCS},
  volume    = {6808},
  publisher = {Springer},
  year      = {2011},
  pages     = {198-211},
  doi       = {10.1007/978-3-642-22600-7_16}
}