On a structural property in the state complexity of projected regular languages
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F12%3A00377957" target="_blank" >RIV/67985840:_____/12:00377957 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.1016/j.tcs.2012.04.009" target="_blank" >http://dx.doi.org/10.1016/j.tcs.2012.04.009</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1016/j.tcs.2012.04.009" target="_blank" >10.1016/j.tcs.2012.04.009</a>
Alternative languages
Result language
angličtina
Original language name
On a structural property in the state complexity of projected regular languages
Original language description
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 considerationthe 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.
Czech name
—
Czech description
—
Classification
Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
BA - General mathematics
OECD FORD branch
—
Result continuities
Project
<a href="/en/project/GPP202%2F11%2FP028" target="_blank" >GPP202/11/P028: Decentralized and coordination supervisory control</a><br>
Continuities
Z - Vyzkumny zamer (s odkazem do CEZ)<br>I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Others
Publication year
2012
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
Theoretical Computer Science
ISSN
0304-3975
e-ISSN
—
Volume of the periodical
449
Issue of the periodical within the volume
Aug 31
Country of publishing house
NL - THE KINGDOM OF THE NETHERLANDS
Number of pages
13
Pages from-to
93-105
UT code for WoS article
000306771300009
EID of the result in the Scopus database
—