Circuit Complexity of Regular Languages

DOI10.1007/978-3-540-73001-9_44MaRDI QIDQ5425344zbMATH OpenOpenAlexFDO

Authors Michal Koucký

Publication date 13 November 2007

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-73001-9_44

zbMATH Keywords

circuit complexityregular languages

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Formal languages and automata (68Q45)

Recommendations

• Circuit complexity of regular languages
• Regular languages in \(NC\)
• Complete classifications for the communication complexity of regular languages
• Circuit complexity of regular languages
• scientific article; zbMATH DE number 1860666

Cited in

(10)

• Regular languages in \(NC\)
• Formulas, regular languages and Boolean circuits
• The regular languages of wire linear \(\mathrm{AC}^0\)
• A note on some languages in uniform \(ACC^ 0\)
• Using duality in circuit complexity
• A circuit complexity approach to transductions
• Visibly counter languages and constant depth circuits
• Circuit complexity of regular languages
• Circuit complexity of regular languages
• On the acceptance power of regular languages

This page was built for publication: Circuit Complexity of Regular Languages

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5425344)