Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Minimal and Monotone Minimal Perfect Hash Functions Kapitel lesen Erstes Kapitel lesen

2015 | OriginalPaper | Buchkapitel

A Circuit Complexity Approach to Transductions

verfasst von : Michaël Cadilhac, Andreas Krebs, Michael Ludwig, Charles Paperman

Erschienen in: Mathematical Foundations of Computer Science 2015

Verlag: Springer Berlin Heidelberg

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Low circuit complexity classes and regular languages exhibit very tight interactions that shade light on their respective expressiveness. We propose to study these interactions at a functional level, by investigating the deterministic rational transductions computable by constant-depth, polysize circuits. To this end, a circuit framework of independent interest that allows variable output length is introduced. Relying on it, there is a general characterization of the set of transductions realizable by circuits. It is then decidable whether a transduction is definable in \(\mathrm{AC}^0\) and, assuming a well-established conjecture, the same for \(\mathrm{ACC}^0\).

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Vorheriges Kapitel Exponential-Size Model Property for PDL with Separating Parallel Composition
Nächstes Kapitel Locally Chain-Parsable Languages
Literatur
1.
Barrington, D.A.M.: Bounded-width polynomial size branching programs recognize exactly those languages in NC\(^1\). J. Comp. Syst. Sc. 38, 150–164 (1989)MathSciNetCrossRefMATH
2.
Barrington, D.A.M., Compton, K., Straubing, H., Thérien, D.: Regular languages in NC\(^1\). J. Comput. Syst. Sci. 44(3), 478–499 (1992)CrossRefMATH
3.
Berstel, J.: Transductions and Context-Free Languages, Leitfäden der Angewandten Mathematik und Mechanik LAMM. Teubner, Stuttgart (1979) CrossRef
4.
Beyersdorff, O., Datta, S., Krebs, A., Mahajan, M., Scharfenberger-Fabian, G., Sreenivasaiah, K., Thomas, M., Vollmer, H.: Verifying proofs in constant depth. TOCT 5(1), 2 (2013)MathSciNetCrossRef
5.
Bojańczyk, M.: Transducers with Origin Information. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) ICALP 2014, Part II. LNCS, vol. 8573, pp. 26–37. Springer, Heidelberg (2014)
6.
Chaubard, L., Pin, J.É., Straubing, H.: First-order formulas with modular predicates. In: LICS, pp. 211–220. IEEE (2006)
7.
Choffrut, C., Schützenberger, M.P.: Counting with rational functions. Theor. Comput. Sci. 58(1–3), 81–101 (1988)CrossRefMATH
8.
Choffrut, C.: A generalization of Ginsburg and Rose’s characterization of G-S-M mappings. In: Maurer, H.A. (ed.) ICALP 1979. LNCS, vol. 71, pp. 88–103. Springer, Heidelberg (1979) CrossRef
9.
Esik, Z., Ito, M.: Temporal logic with cyclic counting and the degree of aperiodicity of finite automata. Acta Cybern. 16(1), 1–28 (2003)MathSciNetMATH
10.
Filiot, E., Krishna, S.N., Trivedi, A.: First-order definable string transformations. In: Raman, V., Suresh, S.P. (eds.) FSTTCS. LIPIcs, vol. 29, pp. 147–159 (2014)
11.
Furst, M., Saxe, J.B., Sipser, M.: Parity, circuits, and the polynomial-time hierarchy. Theor. Comput. Syst. 17, 13–27 (1984)MathSciNetMATH
12.
Koucký, M., Pudlák, P., Thérien, D.: Bounded-depth circuits: separating wires from gates. In: STOC, pp. 257–265. ACM (2005)
13.
Lange, K.-J., McKenzie, P.: On the complexity of free monoid morphisms. In: Chwa, K.-Y., Ibarra, O.H. (eds.) ISAAC 1998. LNCS, vol. 1533, pp. 247–255. Springer, Heidelberg (1998) CrossRef
14.
Lautemann, C., McKenzie, P., Schwentick, T., Vollmer, H.: The descriptive complexity approach to LOGCFL. J. Comput. Syst. Sci. 62(4), 629–652 (2001)MathSciNetCrossRefMATH
15.
16.
Reutenauer, C., Schützenberger, M.P.: Variétés et fonctions rationnelles. Theor. Comput. Sci. 145(1–2), 229–240 (1995)CrossRefMATH
17.
Straubing, H.: Finite Automata, Formal Logic, and Circuit Complexity. Birkhäuser, Boston (1994)CrossRefMATH
18.
Straubing, H.: On logical descriptions of regular languages. In: Rajsbaum, S. (ed.) LATIN 2002. LNCS, vol. 2286, pp. 528–538. Springer, Heidelberg (2002) CrossRef
19.
Vollmer, H.: Introduction to Circuit Complexity. Springer-Verlag, Berlin (1999) CrossRef
Metadaten
Titel
A Circuit Complexity Approach to Transductions
verfasst von
Michaël Cadilhac
Andreas Krebs
Michael Ludwig
Charles Paperman
Copyright-Jahr
2015
Verlag
Springer Berlin Heidelberg
Buch
Mathematical Foundations of Computer Science 2015

Print ISBN: 978-3-662-48056-4

Electronic ISBN: 978-3-662-48057-1

Copyright-Jahr: 2015

DOI
https://doi.org/10.1007/978-3-662-48057-1_11