Результаты исследований: Глава в книге, отчете, сборнике статей › Материалы конференции › Рецензирование
Результаты исследований: Глава в книге, отчете, сборнике статей › Материалы конференции › Рецензирование
}
TY - GEN
T1 - The mortality threshold for partially monotonic automata
T2 - book chapter
AU - Ananichev, D. S.
PY - 2005
Y1 - 2005
N2 - A deterministic incomplete automaton A = < Q, Sigma, delta > is partially monotonic if its state set Q admits a linear order such that each partial transformation delta(_, a) with a is an element of delta preserves the restriction of the order to the domain of the transformation. We show that if A possesses a 'killer' word w is an element of Sigma(*) whose action is nowhere defined, then A is 'killed' by a word of length vertical bar Q vertical bar + [(vertical bar Q vertical bar - 1)/(2)].
AB - A deterministic incomplete automaton A = < Q, Sigma, delta > is partially monotonic if its state set Q admits a linear order such that each partial transformation delta(_, a) with a is an element of delta preserves the restriction of the order to the domain of the transformation. We show that if A possesses a 'killer' word w is an element of Sigma(*) whose action is nowhere defined, then A is 'killed' by a word of length vertical bar Q vertical bar + [(vertical bar Q vertical bar - 1)/(2)].
UR - https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=tsmetrics&SrcApp=tsm_test&DestApp=WOS_CPL&DestLinkType=FullRecord&KeyUT=000230874600010
UR - http://www.scopus.com/inward/record.url?partnerID=8YFLogxK&scp=26444537478
M3 - Conference contribution
SN - 3-540-26546-5
VL - 3572
T3 - LECTURE NOTES IN COMPUTER SCIENCE
SP - 112
EP - 121
BT - 9th International Conference on Developments in Language Theory, DLT 2005, Proceedings
PB - Springer Verlag
ER -
ID: 41355429