Circuit complexity of regular languages
| العنوان: | Circuit complexity of regular languages |
|---|---|
| المؤلفون: | Michal Koucký |
| المصدر: | Lecture Notes in Computer Science ISBN: 9783540730002 CiE |
| بيانات النشر: | European Mathematical Society Publishing House, 2021. |
| سنة النشر: | 2021 |
| مصطلحات موضوعية: | Discrete mathematics, Current (mathematics), Regular language, Abstract family of languages, Pumping lemma for context-free languages, Generalized star height problem, Circuit complexity, Cone (formal languages), Pumping lemma for regular languages, Mathematics |
| الوصف: | 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 AC0and ACC0are all computable by almost linear size circuits, extending the result of Chandra et al.[5]. |
| ردمك: | 978-3-540-73000-2 |
| URL الوصول: | https://explore.openaire.eu/search/publication?articleId=doi_dedup___::efa523a95c1b3a92d0a4f34c5d83a295 https://doi.org/10.4171/automata-1/14 |
| حقوق: | CLOSED |
| رقم الأكسشن: | edsair.doi.dedup.....efa523a95c1b3a92d0a4f34c5d83a295 |
| قاعدة البيانات: | OpenAIRE |
| ردمك: | 9783540730002 |
|---|