Advertisement
Published in:
2006 | OriginalPaper | Chapter
A Characterization of Alternating Log Time by First Order Functional Programs
Authors : Guillaume Bonfante, Jean-Yves Marion, Romain Péchoux
Published in: Logic for Programming, Artificial Intelligence, and Reasoning
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We a give an intrinsic characterization of the class of functions which are computable in
NC
1
that is by a uniform, logarithmic depth and polynomial size family circuit. Recall that the class of functions in
ALogTime
, that is in logarithmic time on an Alternating Turing Machine, is
NC
1
. Our characterization is in terms of first order functional programming languages. We define measure-tools called Sup-interpretations, which allow to give space and time bounds and allow also to capture a lot of program schemas. This study is part of a research on static analysis in order to predict program resources. It is related to the notion of Quasi-interpretations and belongs to the implicit computational complexity line of research.