A circuit complexity approach to transductions

DOI10.1007/978-3-662-48057-1_11MaRDI QIDQ2946331zbMATH OpenOpenAlexFDO

Authors Michaël Cadilhac, A. Krebs, Michael Ludwig, Charles Paperman

Publication date 16 September 2015

Published in Mathematical Foundations of Computer Science 2015 (Search for Journal in Brave)

Full work available at URL https://zenodo.org/record/376304

Mathematics Subject Classification ID

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

Recommendations

• Circuit Complexity of Regular Languages
• Circuit complexity of regular languages
• Circuit complexity and the expressive power of generalized first-order formulas
• Regular languages in \(NC\)
• scientific article; zbMATH DE number 618821

Cites work

• scientific article; zbMATH DE number 2086254 (Why is no real title available?)
• scientific article; zbMATH DE number 3653575 (Why is no real title available?)
• scientific article; zbMATH DE number 3660804 (Why is no real title available?)
• scientific article; zbMATH DE number 618821 (Why is no real title available?)
• scientific article; zbMATH DE number 2016845 (Why is no real title available?)
• Bounded-depth circuits
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Counting with rational functions
• First-order definable string transformations
• Parity, circuits, and the polynomial-time hierarchy
• Regular languages in \(NC\)
• Some results onC-varieties
• The descriptive complexity approach to LOGCFL
• Transducers with Origin Information
• Varieties and rational functions
• Verifying proofs in constant depth

Cited in

(7)

• scientific article; zbMATH DE number 7559499 (Why is no real title available?)
• An application of the matrix representation of transductions
• Continuity of functional transducers: a profinite study of rational functions
• Circuit complexity of regular languages
• Synthesis of computable regular functions of infinite words
• A circuit-preserving mapping from multilevel to Boolean dynamics
• A note on detecting sneak paths in transistor networks

This page was built for publication: A circuit complexity approach to transductions

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