Subclasses of \textsc{Ptime} interpreted by programming languages

DOI10.1007/s00224-022-10074-zOpenAlexW4293059963MaRDI QIDQ6109064

Siddharth Bhaskar, Cynthia Kop, Jakob Grue Simonsen

Publication date: 26 July 2023

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-022-10074-z

zbMATH Keywords

lower boundscomplexity theoryauxiliary pushdown automataabstract complexity theorycons-free programs

Mathematics Subject Classification ID

Theory of computing (68Qxx) Theory of software (68Nxx) Computability and recursion theory (03Dxx)

Related Items (1)

Read/write factorizable programs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Implicit characterizations of FPTIME and NC revisited
• Tree-size bounded alternation
• On uniform circuit complexity
• Properties that characterize LOGCFL
• LOGSPACE and PTIME characterized by programming languages
• On two-way multihead automata
• The expressive power of higher-order types or, life without CONS
• The Power of Non-determinism in Higher-Order Implicit Complexity
• P-uniform circuit complexity
• Towards an Implicit Characterization of NC k
• Alternation
• Computational Complexity
• A Machine-Independent Theory of the Complexity of Recursive Functions

This page was built for publication: Subclasses of \textsc{Ptime} interpreted by programming languages