State complexity of projected languages
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F11%3A00362730" target="_blank" >RIV/67985840:_____/11:00362730 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.1007/978-3-642-22600-7_16" target="_blank" >http://dx.doi.org/10.1007/978-3-642-22600-7_16</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/978-3-642-22600-7_16" target="_blank" >10.1007/978-3-642-22600-7_16</a>
Alternative languages
Result language
angličtina
Original language name
State complexity of projected languages
Original language description
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 transitionlabeled 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.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
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)
Others
Publication year
2011
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
Article name in the collection
Descriptional complexity of formal systems
ISBN
978-3-642-22599-4
ISSN
—
e-ISSN
—
Number of pages
14
Pages from-to
198-211
Publisher name
Springer
Place of publication
Berlin
Event location
Giessen/Limburg
Event date
Jul 25, 2011
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—