Circuit complexity of regular languages

Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F07%3A00089749" target="_blank" >RIV/67985840:_____/07:00089749 - isvavai.cz</a>
Výsledek na webu
—
DOI - Digital Object Identifier
—

Jazyk výsledku
angličtina
Název v původním jazyce
Circuit complexity of regular languages
Popis výsledku v původním jazyce
We survey our current knowledge of circuit complexity of regular languages. We show that regular languages are of interest as languages providing understanding of different circuit classes. We also prove that regular languages that are in AC0 ad ACC0 areall computable by almost linear size circuits, extending the result of Chandra et al. 1983.
Název v anglickém jazyce
Circuit complexity of regular languages
Popis výsledku anglicky
We survey our current knowledge of circuit complexity of regular languages. We show that regular languages are of interest as languages providing understanding of different circuit classes. We also prove that regular languages that are in AC0 ad ACC0 areall computable by almost linear size circuits, extending the result of Chandra et al. 1983.

Projekt
Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.
Návaznosti
Z - Vyzkumny zamer (s odkazem do CEZ)

Rok uplatnění
2007
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 statě ve sborníku
proceedings of the 3rd Conference on Computability in Europe, CiE 2007
ISBN
978-3-540-73000-2
ISSN
—
e-ISSN
—
Počet stran výsledku
10
Strana od-do
—
Název nakladatele
Springer-Verlag
Místo vydání
Heidelberg
Místo konání akce
Siena
Datum konání akce
18. 6. 2007
Typ akce podle státní příslušnosti
WRD - Celosvětová akce
Kód UT WoS článku
000247797600044

Podobné výsledky(10)