1 Search Results for "Kuroda, Satoru"

Document
DOI: 10.4230/LIPIcs.CSL.2012.440
Axiomatizing proof tree concepts in Bounded Arithmetic

Authors: Satoru Kuroda

Published in: LIPIcs, Volume 16, Computer Science Logic (CSL'12) - 26th International Workshop/21st Annual Conference of the EACSL (2012)

Abstract
We construct theories of Cook-Nguyen style two-sort bounded arithmetic whose provably total functions are exactly those in LOGCFL and LOGDCFL. Axiomatizations of both theories are based on the proof tree size characterizations of these classes. We also show that our theory for LOGCFL proves a certain formulation of the pumping lemma for context-free languages.
Cite as

Satoru Kuroda. Axiomatizing proof tree concepts in Bounded Arithmetic. In Computer Science Logic (CSL'12) - 26th International Workshop/21st Annual Conference of the EACSL. Leibniz International Proceedings in Informatics (LIPIcs), Volume 16, pp. 440-454, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{kuroda:LIPIcs.CSL.2012.440,
  author =	{Kuroda, Satoru},
  title =	{{Axiomatizing proof tree concepts in Bounded Arithmetic}},
  booktitle =	{Computer Science Logic (CSL'12) - 26th International Workshop/21st Annual Conference of the EACSL},
  pages =	{440--454},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-42-2},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{16},
  editor =	{C\'{e}gielski, Patrick and Durand, Arnaud},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2012.440},
  URN =		{urn:nbn:de:0030-drops-36893},
  doi =		{10.4230/LIPIcs.CSL.2012.440},
  annote =	{Keywords: Bounded Arithmetic, LOGCFL, LOGDCFL, Proof tree}
}
  • Refine by Author
  • 1 Kuroda, Satoru

  • Refine by Classification

  • Refine by Keyword
  • 1 Bounded Arithmetic
  • 1 LOGCFL
  • 1 LOGDCFL
  • 1 Proof tree

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2012

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact