Semantisches Browsen

Aus International Center for Computational Logic
Wechseln zu:Navigation, Suche
Article3005
Abstract A transition is unobservable if it is labe
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.
fundamental problems which are still open.  +
Author Galina Jirásková + , Tomáš Masopust +
BibTex
@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}
}
Bibtype Article  +
DOI Name 10.1016/j.tcs.2012.04.009  +
Download On a structural property in the state complexity of projected regular languages.pdf  +
ErsterAutorNachname Jirásková  +
ErsterAutorVorname Galina  +
Forschungsgruppe Wissensbasierte Systeme +
ISSN 0304-3975  +
Journal Theoretical Computer Science  +
Pages 93–105  +
Publication text Galina Jirásková, Tomáš Masopust<br/>
Galina Jirásková, Tomáš Masopust<br/> '''[[Article3005|On a structural property in the state complexity of projected regular languages]]''' <br/>__NOTOC__Theoretical Computer Science, 449:93–105, 2012<br/><span class="glyphicon glyphicon-chevron-right" style="font-size: 85%;" ></span> [[Article3005|Details]] <span class="glyphicon glyphicon-chevron-right" style="font-size: 85%; margin-left: 2ex; "></span> [[Media:On a structural property in the state complexity of projected regular languages.pdf|Download]]
projected regular languages.pdf|Download]]  +
Publication text en Galina Jirásková, Tomáš Masopust<br/>
Galina Jirásková, Tomáš Masopust<br/> '''[[Article3005/en|On a structural property in the state complexity of projected regular languages]]''' <br/>__NOTOC__Theoretical Computer Science, 449:93–105, 2012<br/><span class="glyphicon glyphicon-chevron-right" style="font-size: 85%;" ></span> [[Article3005|Details]] <span class="glyphicon glyphicon-chevron-right" style="font-size: 85%; margin-left: 2ex;" ></span> [[Media:On a structural property in the state complexity of projected regular languages.pdf|Download]]
projected regular languages.pdf|Download]]  +
Referiert 1  +
Title On a structural property in the state complexity of projected regular languages  +
To appear 0  +
Type article  +
Volume 449  +
Year 2012  +
Hat Abfrage
Dieses Attribut ist ein Spezialattribut in diesem Wiki.
Article3005 + , Article3005 + , Article3005 + , Article3005 + , Article3005 + , Article3005 +
Kategorien Publikation , Article
Zuletzt geändert
Dieses Attribut ist ein Spezialattribut in diesem Wiki.
24 Mai 2016 16:01:22  +
verstecke Attribute die hierhin verlinken 
Article3005/en + Weiterleitungsseite
 

 

Bitte den Namen einer Seite angeben, um mit dem Browsen zu beginnen.