A language-theoretical approach to descriptive complexity

DOI10.1007/978-3-662-53132-7_6MaRDI QIDQ2817376zbMATH OpenOpenAlexFDO

Authors Michaël Cadilhac, A. Krebs, Klaus-Jörn Lange

Publication date 30 August 2016

Published in Developments in Language Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-662-53132-7_6

zbMATH Keywords

circuitsdescriptive complexityformal languageshyperwordslogic

Mathematics Subject Classification ID

Descriptive complexity and finite models (68Q19) Formal languages and automata (68Q45) Switching theory, applications of Boolean algebras to circuits and networks (94C11)

Recommendations

• A logical approach to locality in pictures languages
• A descriptive complexity approach to the linear hierarchy.
• Descriptive complexity for pictures languages
• scientific article; zbMATH DE number 459361
• Formulas, regular languages and Boolean circuits

Cites work

• Characterizing \(\text{TC}^{0}\) in terms of infinite groups
• Expressibility and Parallel Complexity
• scientific article; zbMATH DE number 2086221 (Why is no real title available?)
• scientific article; zbMATH DE number 618821 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• Linear Circuits, Two-Variable Logic and Weakly Blocked Monoids
• Nesting until and since in linear temporal logic
• On uniformity within \(NC^ 1\)
• Regular Languages Definable by Majority Quantifiers with Two Variables
• The descriptive complexity approach to LOGCFL

Cited in

(2)

• scientific article; zbMATH DE number 140381 (Why is no real title available?)
• Language for Description of Worlds. Part 1: Theoretical Foundation

This page was built for publication: A language-theoretical approach to descriptive complexity

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