A circuit complexity approach to transductions

DOI10.1007/978-3-662-48057-1_11zbMATH Open1465.68076OpenAlexW1457388223MaRDI QIDQ2946331FDOQ2946331

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

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

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (7)

• Title not available (Why is that?)
• An application of the matrix representation of transductions
• Title not available (Why is that?)
• Circuit complexity of regular languages
• Title not available (Why is that?)
• 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)