On the public citation graph

Function-algebraic characterizations of log and polylog parallel time

https://doi.org/10.1007/bf01202288

0 signed · 39 inferred · view as graph

Inferred edges come from two machine sources: sweeps of open repository metadata (mostly SSRN and Zenodo), and a bulk OpenAlex citation snapshot. Every row below is labelled with the one it came from. Neither is a complete citation index — absence here is not evidence of absence.

Is this your work? Sign in with ORCID and put your name on the claims that are yours.

Claim with ORCID

Reference health. See whether every reference in this work resolves to a known work and none has been retracted — and get a dated CiteStamped badge you can embed.

See reference health

What this work says

Outgoing claims: the papers this work cites, builds on, or argues with.

inferredcites →https://doi.org/10.1007/978-1-4612-3466-1_16openalex-snapshot

Subrecursion and lambda representation over free algebras

inferredcites →https://doi.org/10.1007/978-1-4612-3466-1_4openalex-snapshot

Sequential, machine-independent characterizations of the parallel complexity classes AlogTIME, AC k , NC k and NC

inferredcites →https://doi.org/10.1007/bf01201998openalex-snapshot

A new recursion-theoretic characterization of the polytime functions

inferredcites →https://doi.org/10.1016/0022-0000(81)90038-6openalex-snapshot

On uniform circuit complexity

inferredcites →https://doi.org/10.1016/0022-0000(89)90037-8openalex-snapshot

Bounded-width polynomial-size branching programs recognize exactly those languages in NC1

inferredcites →https://doi.org/10.1016/0168-0072(91)90057-sopenalex-snapshot

Arithmetizing Uniform NC

inferredcites →https://doi.org/10.1016/0168-0072(92)90068-bopenalex-snapshot

Bounded arithmetic for NC, ALogTIME, L and NL

inferredcites →https://doi.org/10.1016/0890-5401(90)90063-nopenalex-snapshot

An algebra and a logic for NC1

inferredcites →https://doi.org/10.1093/oso/9780198536901.003.0007openalex-snapshot

On polynomial size Frege proofs of certain combinatorial principles

inferredcites →https://doi.org/10.1109/lics.1991.151625openalex-snapshot

A foundational delineation of computational feasibility

inferredcites →https://doi.org/10.1109/sct.1992.215383openalex-snapshot

Quasipolynomial size circuit classes

inferredcites →https://doi.org/10.1145/12130.12131openalex-snapshot

Bounded-width polynomial-size branching programs recognize exactly those languages in NC 1

inferredcites →https://doi.org/10.1145/22145.22177openalex-snapshot

The polynomial hierarchy and fragments of bounded arithmetic

inferredcites →https://doi.org/10.1145/28395.28409openalex-snapshot

The Boolean formula value problem is in ALOGTIME

inferredcites →https://doi.org/10.1145/322234.322243openalex-snapshot

Alternation

inferredcites →https://doi.org/10.2307/2270886openalex-snapshot

Alan Cobham. The intrinsic computational difficulty of functions. Logic, methodology and philosophy of science, Proceedings of the 1964 International Congress, edited by Yehoshua Bar-Hillel, Studies in logic and the foundations of mathematics, North-Holland Publishing Company, Amsterdam 1965, pp.…

What points at this work

Incoming claims: where this work appears in other papers’ reference lists and arguments.

inferred← citeshttps://doi.org/10.1007/11874683_14openalex-snapshot

Towards an Implicit Characterization of NC k

inferred← citeshttps://doi.org/10.1007/11916277_7openalex-snapshot

A Characterization of Alternating Log Time by First Order Functional Programs

inferred← citeshttps://doi.org/10.1007/3-540-45504-3_1openalex-snapshot

Linear Ramified Higher Type Recursion and Parallel Complexity

inferred← citeshttps://doi.org/10.1007/3-540-60178-3_79openalex-snapshot

On parallel hierarchies and R ki

inferred← citeshttps://doi.org/10.1007/3-540-60178-3_81openalex-snapshot

Computation models and function algebras

inferred← citeshttps://doi.org/10.1007/3-540-63045-7_5openalex-snapshot

A safe recursion scheme for exponential time

inferred← citeshttps://doi.org/10.1007/978-3-540-79228-4openalex-snapshot

Theory and Applications of Models of Computation

inferred← citeshttps://doi.org/10.1007/978-3-540-79228-4_12openalex-snapshot

A Characterization of NC k by First Order Functional Programs

inferred← citeshttps://doi.org/10.1007/978-3-540-87531-4_6openalex-snapshot

Recursion Schemata for NC k

inferred← citeshttps://doi.org/10.1007/s00037-004-0184-4openalex-snapshot

Recursion Schemata for Slowly Growing Depth Circuit Classes

inferred← citeshttps://doi.org/10.1007/s002240000085openalex-snapshot

Sharply Bounded Alternation and Quasilinear Time

inferred← citeshttps://doi.org/10.1016/j.apal.2004.10.011openalex-snapshot

Control structures in programs and computational complexity

inferred← citeshttps://doi.org/10.1016/j.ic.2015.12.009openalex-snapshot

Two function algebras defining functions in NCk boolean circuits

inferred← citeshttps://doi.org/10.1016/j.jlap.2009.02.005openalex-snapshot

Implicit characterizations of FPTIME and NC revisited

inferred← citeshttps://doi.org/10.1016/j.tcs.2003.10.016openalex-snapshot

On the computational complexity of imperative programming languages

inferred← citeshttps://doi.org/10.1016/s0049-237x(99)80033-0openalex-snapshot

Computation Models and Function Algebras

inferred← citeshttps://doi.org/10.1016/s0168-0072(97)00035-3openalex-snapshot

On parallel hierarchies and Rki

inferred← citeshttps://doi.org/10.1016/s0304-3975(99)00209-1openalex-snapshot

A characterization of alternating log time by ramified recurrence

inferred← citeshttps://doi.org/10.1109/sfcs.1998.743522openalex-snapshot

A characterization of NC by tree recurrence

inferred← citeshttps://doi.org/10.1137/s009753979528175xopenalex-snapshot

Ranking Primitive Recursions: The Low Grzegorczyk Classes Revisited

inferred← citeshttps://doi.org/10.4204/eptcs.298.3openalex-snapshot

Pointers in Recursion: Exploring the Tropics

inferred← citeshttps://doi.org/10.48550/arxiv.cs/0702160openalex-snapshot

A Quantifier-Free String Theory for ALOGTIME Reasoning

inferred← citeshttps://doi.org/10.70675/f1838cb3zfc72z4859z92fezc8cec6a04a5eopenalex-snapshot

Analyse de la complexité des programmes par interprétation sémantique

Editorial review for independent work. ICSAC — the Institute for Complexity Science and Advanced Computing — runs a structured editorial panel for researchers publishing outside journals, and publishes on CiteStamp rails. Submission is free and goes through ORCID: icsacinstitute.org/submit.