Feasible set functions have small circuits

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F19%3A00499289" target="_blank" >RIV/67985840:_____/19:00499289 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.3233/COM-180096" target="_blank" >http://dx.doi.org/10.3233/COM-180096</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.3233/COM-180096" target="_blank" >10.3233/COM-180096</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Feasible set functions have small circuits

Popis výsledku v původním jazyce

The Cobham Recursive Set Functions (CRSF) provide an analogue of polynomial time computation which applies to arbitrary sets. We give three new equivalent characterizations of CRSF. The first is algebraic, using subset-bounded recursion and a form of Mostowski collapse. The second is our main result: the CRSF functions are shown to be precisely the functions computed by a class of uniform, infinitary, Boolean circuits. The third is in terms of a simple extension of the rudimentary functions by transitive closure and subset-bounded recursion.

Název v anglickém jazyce

Feasible set functions have small circuits

Popis výsledku anglicky

The Cobham Recursive Set Functions (CRSF) provide an analogue of polynomial time computation which applies to arbitrary sets. We give three new equivalent characterizations of CRSF. The first is algebraic, using subset-bounded recursion and a form of Mostowski collapse. The second is our main result: the CRSF functions are shown to be precisely the functions computed by a class of uniform, infinitary, Boolean circuits. The third is in terms of a simple extension of the rudimentary functions by transitive closure and subset-bounded recursion.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2019

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Computability

ISSN

2211-3568

e-ISSN

—

Svazek periodika

8

Číslo periodika v rámci svazku

1

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

32

Strana od-do

67-98

Kód UT WoS článku

000472084400004

EID výsledku v databázi Scopus

2-s2.0-85058974478