Circuit complexity of regular languages

DOI10.4171/AUTOMATA-1/14MaRDI QIDQ5918477zbMATH OpenFDO

Authors Michal Koucký

Publication date 4 February 2022

Published in Handbook of Automata Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.4171/AUTOMATA-1/14

Mathematics Subject Classification ID

Networks and circuits as models of computation; circuit complexity (68Q06) Formal languages and automata (68Q45) Algebraic theory of languages and automata (68Q70)

Recommendations

• Formulas, regular languages and Boolean circuits
• Circuit Complexity of Regular Languages
• scientific article; zbMATH DE number 618821
• Regular languages in \(NC\)
• scientific article; zbMATH DE number 459361

Cites work

• \(\Sigma_ 1^ 1\)-formulae on finite structures
• A generalization of the Schützenberger product of finite monoids
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Branching Programs and Binary Decision Diagrams
• Circuit complexity of regular languages
• Classification of finite monoids: the language approach
• CONSTANT-DEPTH PERIODIC CIRCUITS
• Families of recognizable sets corresponding to certain varieties of finite monoids
• Finite monoids and the fine structure of NC ¹
• Finite semigroup varieties of the form V*D
• scientific article; zbMATH DE number 5605078 (Why is no real title available?)
• scientific article; zbMATH DE number 3497806 (Why is no real title available?)
• scientific article; zbMATH DE number 3519903 (Why is no real title available?)
• scientific article; zbMATH DE number 1254648 (Why is no real title available?)
• scientific article; zbMATH DE number 618821 (Why is no real title available?)
• scientific article; zbMATH DE number 2087227 (Why is no real title available?)
• Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
• On uniform circuit complexity
• On uniformity within \(NC^ 1\)
• Parity, circuits, and the polynomial-time hierarchy
• Regular languages defined with generalized quantifiers
• Regular languages in \(NC\)
• The dot-depth hierarchy of star-free languages is infinite
• Unbounded fan-in circuits and associative functions

Cited in

(10)

• Regular languages in \(NC\)
• Formulas, regular languages and Boolean circuits
• scientific article; zbMATH DE number 1809724 (Why is no real title available?)
• Extensions of an idea of McNaughton
• scientific article; zbMATH DE number 459361 (Why is no real title available?)
• scientific article; zbMATH DE number 2102759 (Why is no real title available?)
• The power of diversity
• Circuit Complexity of Regular Languages
• FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
• Circuit complexity 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 Q5918477)