@inproceedings{10.1007/11916277_7,
    Abstract = {We a give an intrinsic characterization of the class of functions which are computable in NC1 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 NC1. 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.},
    Address = {Berlin, Heidelberg},
    Author = {Bonfante, Guillaume and Marion, Jean-Yves and P{\'e}choux, Romain},
    BookTitle = {Logic for Programming, Artificial Intelligence, and Reasoning},
    Editor = {Hermann, Miki and Voronkov, Andrei},
    File = {A Characterization of Alternating Log Time by First Order Functional Programs - Bonfante2006\_Chapter\_ACharacterizationOfAlternating.pdf},
    ISBN = {978-3-540-48282-6},
    Pages = {90--104},
    Publisher = {Springer Berlin Heidelberg},
    Title = {A Characterization of Alternating Log Time by First Order Functional Programs},
    Year = {2006},
    date-added = {2022-08-10 13:20:14 +0200},
    date-modified = {2022-08-10 13:20:14 +0200},
    doi = {10.1007/11916277_7}
}

@inproceedings{10.1007/11916277_7, Abstract = {We a give an intrinsic characterization of the class of functions which are computable in NC1 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 NC1. 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.}, Address = {Berlin, Heidelberg}, Author = {Bonfante, Guillaume and Marion, Jean-Yves and P{\'e}choux, Romain}, BookTitle = {Logic for Programming, Artificial Intelligence, and Reasoning}, Editor = {Hermann, Miki and Voronkov, Andrei}, File = {A Characterization of Alternating Log Time by First Order Functional Programs - Bonfante2006_Chapter_ACharacterizationOfAlternating.pdf}, ISBN = {978-3-540-48282-6}, Pages = {90--104}, Publisher = {Springer Berlin Heidelberg}, Title = {A Characterization of Alternating Log Time by First Order Functional Programs}, Year = {2006}, date-added = {2022-08-10 13:20:14 +0200}, date-modified = {2022-08-10 13:20:14 +0200}, doi = {10.1007/11916277_7} }