Circuit complexity of regular languages

Result code in 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>

Result on the web

—

DOI - Digital Object Identifier

—

Result language

angličtina

Original language name

Circuit complexity of regular languages

Original language description

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.

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

BA - General mathematics

OECD FORD branch

—

Project

Result was created during the realization of more than one project. More information in the Projects tab.

Continuities

Z - Vyzkumny zamer (s odkazem do CEZ)

Publication year

2007

Confidentiality

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

Article name in the collection

proceedings of the 3rd Conference on Computability in Europe, CiE 2007

ISBN

978-3-540-73000-2

ISSN

—

e-ISSN

—

Number of pages

10

Pages from-to

—

Publisher name

Springer-Verlag

Place of publication

Heidelberg

Event location

Siena

Event date

Jun 18, 2007

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

000247797600044