A Circuit Complexity Approach to Transductions

DOI10.1007/978-3-662-48057-1_11zbMath1465.68076OpenAlexW1457388223MaRDI QIDQ2946331

Andreas Krebs, Michael Ludwig, Charles Paperman, Michaël Cadilhac

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)

Related Items (3)

Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Varieties and rational functions
• Counting with rational functions
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Regular languages in \(NC\)
• Verifying proofs in constant depth
• First-order definable string transformations
• Parity, circuits, and the polynomial-time hierarchy
• Bounded-depth circuits
• Some results onC-varieties
• Transducers with Origin Information
• The descriptive complexity approach to LOGCFL

This page was built for publication: A Circuit Complexity Approach to Transductions