On a structural property in the state complexity of projected regular languages

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

On a structural property in the state complexity of projected regular languages

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

On a structural property in the state complexity of projected regular languages

Popis výsledku anglicky

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.

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

<a href="/cs/project/GPP202%2F11%2FP028" target="_blank" >GPP202/11/P028: Decentralizované a koordinační supervizní řízení</a><br>

Návaznosti

Z - Vyzkumny zamer (s odkazem do CEZ)<br>I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2012

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Theoretical Computer Science

ISSN

0304-3975

e-ISSN

—

Svazek periodika

449

Číslo periodika v rámci svazku

Aug 31

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

13

Strana od-do

93-105

Kód UT WoS článku

000306771300009

EID výsledku v databázi Scopus

—