Characterizing time computational complexity classes with polynomial differential equations. (English) Zbl 1526.68001
Reviewer: Arne Meier (Hannover)
Found 86 Documents (Results 1–86)
Idempotent Turing machines. (English) Zbl 07724252
Bonchi, Filippo (ed.) et al., 46th international symposium on mathematical foundations of computer science, MFCS 2021, August 23–27, 2021, Tallinn, Estonia. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 202, Article 79, 18 p. (2021).
MSC:
68Qxx
Characterizations of ITBM-computability. I. (English. Russian original) Zbl 1515.03188
Algebra Logic 59, No. 6, 423-436 (2021); translation from Algebra Logika 59, No. 6, 627-648 (2020).
Computations on counter machines with summator. (English. Russian original) Zbl 1397.68077
Mosc. Univ. Comput. Math. Cybern. 42, No. 1, 31-38 (2018); translation from Vestn. Mosk. Univ., Ser. XV 2018, No. 1, 31-39 (2018).
Recursion theory. Reprint of the 1993 original. (English) Zbl 1366.03001
Lecture Notes in Logic 1. Cambridge: Cambridge University Press; Ithaca, NY: Association of Symbolic Logic (ASL) (ISBN 978-1-107-16808-4/hbk; 978-1-316-71701-1/ebook). vii, 84 p. (2016).
On elementary word functions obtained by bounded prefix concatenation. (English. Russian original) Zbl 1521.03116
Discrete Math. Appl. 26, No. 3, 155-163 (2016); translation from Diskretn. Mat. 27, No. 3, 44-55 (2015).
Monoids with tests and the algebra of possibly non-halting programs. (English) Zbl 1319.68085
MSC:
68Q05
03B70
Representation theorems for analytic machines and computability of analytic functions. (English) Zbl 1309.03018
Calculation of hypergeometric series with quasi-linear time and linear space complexity. (Russian. English summary) Zbl 1463.68030
How not to use the Church-Turing thesis against Platonism. (English) Zbl 1266.00018
Reviewer: Manuel Bremer (Düsseldorf)
Differential recursion. (English) Zbl 1351.03034
MSC:
03D78
68Q05
A foundation for real recursive function theory. (English) Zbl 1189.03047
Reviewer: Timothy McNicholl (Beaumont)
On finite-time computability preserving conversions. (English) Zbl 1262.03148
Brattka, V. (ed.) et al., Proceedings of the fifth international conference on computability and complexity in analysis (CCA 2008), Hagen, Germany, August 21–24, 2008. Amsterdam: Elsevier. Electronic Notes in Theoretical Computer Science 221, 299-308 (2008).
Characterizing computable analysis with differential equations. (English) Zbl 1262.03078
Brattka, V. (ed.) et al., Proceedings of the fifth international conference on computability and complexity in analysis (CCA 2008), Hagen, Germany, August 21–24, 2008. Amsterdam: Elsevier. Electronic Notes in Theoretical Computer Science 221, 23-35 (2008).
A natural axiomatization of computability and proof of Church’s thesis. (English) Zbl 1167.03027
Reviewer: Leon Harkleroad (Wilton)
The elementary computable functions over the real numbers: applying two new techniques. (English) Zbl 1141.03016
Computability and incomputability. (English) Zbl 1150.03317
Cooper, S. Barry (ed.) et al., Computation and logic in the real world. Third conference on computability in Europe, CiE 2007, Siena, Italy, June 18–23, 2007. Proceedings. Berlin: Springer (ISBN 978-3-540-73000-2/pbk). Lecture Notes in Computer Science 4497, 705-715 (2007).
To \(\lambda\)-define the computable functions without the fixed point operators. (Chinese. English summary) Zbl 1120.03010
Formalizing Church’s thesis. (English) Zbl 1105.03033
Olszewski, Adam (ed.) et al., Church’s thesis after 70 years. Frankfurt: Ontos Verlag (ISBN 3-938793-09-0/hbk). Ontos Mathematical Logic 1, 253-268 (2006).
A new Gödelian argument for hypercomputing minds based on the busy beaver problem. (English) Zbl 1098.03010
Reviewer: Albert A. Mullin (Madison)
Computable calculus. With 1 CD-ROM (Windows 95, 98, 2000, Windows NT). (English) Zbl 1087.26001
San Diego, CA: Academic Press (ISBN 0-12-041752-9/pbk). xiv, 192 p. (2001).
Reviewer: Zheng Xizhong (Cottbus)
Recursion theory. Reprint of the 1993 original. (English) Zbl 0962.03028
Lecture Notes in Logic. 1. Natick, MA: Association for Symbolic Logic. 84 p. (2001).
Computable economics. The Arne Ryde memorial lectures. (English) Zbl 1007.91001
Oxford: Oxford University Press. xi, 222 p. (2000).
Reviewer: Bogdan Choczewski (Kraków)
Proving Church’s thesis. (English) Zbl 0977.03003
Reviewer: Elliott Mendelson (Flushing)
Computable analysis. An introduction. (English) Zbl 0956.68056
Texts in Theoretical Computer Science. An EATCS Series. Berlin: Springer. x, 281 p. (2000).
Reviewer: Zheng Xizhong (Cottbus)
Computation models and function algebras. (English) Zbl 0942.68049
Griffor, Edward R. (ed.), Handbook of computability theory. Amsterdam: Elsevier. Stud. Logic Found. Math. 140, 589-681 (1999).
Reviewer: Heribert Vollmer (Würzburg)
Classical recursion theory. Vol. II. (English) Zbl 0931.03057
Studies in Logic and the Foundations of Mathematics. 143. Amsterdam: Elsevier. xvi, 949 p. (1999).
Reviewer: Cristian S. Calude (Auckland)
Statistic lattice computer. (Russian) Zbl 0930.03043
Reviewer: A.S.Morozov (Novosibirsk)
Real functions defined by transducers. (English. Russian original) Zbl 0919.03047
Cybern. Syst. Anal. 34, No. 1, 69-76 (1998); translation from Kibern. Sist. Anal. 1998, No. 1, 82-93 (1998).
On a theory for \(\text{AC}^0\) and the strength of the induction scheme. (English) Zbl 0905.03039
Reviewer: R.Kossak (New York)
Effectivity and effective continuity of functions between computable metric spaces. (English) Zbl 0911.03020
Bridges, D. S. (ed.) et al., Combinatorics, complexity, and logic. Proceedings of the 1st international conference on discrete mathematics and theoretical computer science, DMTCS ’96, Auckland, New Zealand, December 9–13, 1996. Berlin: Springer. 264-275 (1997).
MSC:
03D45
Intuitionistic formal theories with realizability in subrecursive classes. (English) Zbl 0895.03017
Reviewer: J.S.Ullian (St.Louis)
A foundation for computable analysis. (English) Zbl 0889.03035
Plášil, František (ed.) et al., SOFSEM ’97: Theory and practice of informatics. 24th seminar on current trends in theory and practice of informatics, Milovy, Czech Republic, November 22–29, 1997. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1338, 104-121 (1997).
Reviewer: Zheng Xizhong (Hagen)
A foundation for computable analysis. (English) Zbl 0896.03033
Freksa, Christian (ed.) et al., Foundations of computer science. Potential, theory, cognition. Berlin: Springer. Lect. Notes Comput. Sci. 1337, 185-199 (1997).
Reviewer: Ning Zhong (Batavia/Ohio)
Order-free recursion on the real numbers. (English) Zbl 0876.03022
Reviewer: R.Downey (Wellington)
Disconnectedness of sublevel sets of some Riemannian functionals. (English) Zbl 0872.53030
Reviewer: M.Katz (Vandœuvre)
A note on recursive functions. (English) Zbl 0844.03025
Computable functions on stream algebras. (English) Zbl 0831.08001
Schwichtenberg, Helmut (ed.), Proof and computation. Proceedings of the NATO ASI summer school held in Marktoberdorf, Germany, July 20-August 1, 1993. Berlin: Springer-Verlag. NATO ASI Ser., Ser. F, Comput. Syst. Sci. 139, 397-437 (1995).
Reviewer: C.Meinel (Trier)
Machine learning of higher-order programs. (English) Zbl 0814.03034
Reviewer: P.Jančar (Ostrava)
Computability: a mathematical sketchbook. (English) Zbl 0792.03027
Graduate Texts in Mathematics. 146. New York, NY: Springer-Verlag. ix, 178 p. (1994).
Reviewer: U.Schöning (Ulm)
A construction of typed lambda models related to feasible computability. (English) Zbl 0793.68059
Gottlob, Georg (ed.) et al., Computational logic and proof theory. 3rd Kurt Gödel Colloquium, KGC ’93, Brno, Czech Republic, August 24-27, 1993. Proceedings. Berlin: Springer-Verlag. Lect. Notes Comput. Sci. 713, 301-312 (1993).
Recursion theory. (English) Zbl 0789.03039
Lecture Notes in Logic. 1. Berlin: Springer-Verlag. vii, 84 p. (1993).
Reviewer: L.Harkleroad (Ithaca)
Algorithms: Main ideas and applications. Transl. from the Russian by A. Shen. (English) Zbl 0786.68032
Mathematics and its Applications (Dordrecht). 251. Dordrecht: Kluwer Academic Publishers. xii, 269 p. (1993).
Reviewer: A.V.Anisimov (Kiev)
Structure of computative tree for computable function. (English) Zbl 0792.68039
MSC:
68Q05
03D10
Diagonals and semihyperhypersimple sets. (English) Zbl 0747.03019
Reviewer: M.Zimand (Bucureşti)
Hardly realizable Boolean functions and hardly computable real numbers. (English. Russian original) Zbl 0800.68428
Discrete Math. Appl. 2, No. 4, 381-394 (1992); translation from Diskretn. Mat. 3, No. 1, 48-60 (1991).
MSC:
68Q05
94C10
Classes of functions defined by transducers. (English. Russian original) Zbl 0752.03031
Cybernetics 26, No. 6, 781-788 (1990); translation from Kibernetika 1990, No. 6, 1-7, 34 (1990).
Stability and computability in coherent domains. (English) Zbl 0716.03042
Reviewer: S.P.Yukna
Some applications of computable one-one numberings. (English) Zbl 0714.03038
Reviewer: C.Calude
MSC:
03D45
Rationality, computability, and complexity. (English) Zbl 0708.90001
Reviewer: E.Melis
On a theory of computation over the real numbers; NP completeness, recursive functions and universal machines. (English) Zbl 0691.68034
Workshop on dynamical systems, Proc. Conf., Trieste/Italy 1988, Pitman Res. Notes Math. Ser. 221, 23-52 (1990).
On functions computable in nondeterministic polynomial time: Some characterizations. (English) Zbl 0681.68072
Computer science logic, 1st Workshop, CSL ’87, Karlsruhe/FRG 1987, Lect. Notes Comput. Sci. 329, 289-303 (1988).
Turing projectability. (English) Zbl 0645.03038
Reviewer: M.Beeson
Computability and logic. (English) Zbl 0631.03001
Mathematics and its applications. Chichester: Ellis Horwood Limited; New York etc.: Halsted Press: a division of John Wiley & Sons. 243 p.; £36.50 (1987).
Reviewer: A.A.Mullin
Brains, machines, and mathematics. 2nd ed. (Brains, machines, and mathematics.) (English) Zbl 0645.68001
New York etc.: Springer-Verlag. XVI, 202 p.; DM 55.00 (1987).
Reviewer: St.Bloom
Pessimization is unsolvable. (English) Zbl 0653.68038
SIGACT News 18, No. 3, 37 (1986).
Characterization of polynomially computable word functions by modified loop-programs. (English) Zbl 0615.03026
Algebra, combinatorics and logic in computer science, Colloq. Györ/Hung. 1983, Vol. 2, Colloq. Math. Soc. János Bolyai 42, 787-802 (1986).
Reviewer: S.P.Yukna
A syntactical definition of the \({\mathcal P}=?{\mathcal N}{\mathcal P}\) problem. (English) Zbl 0604.68052
Computability, complexity, and languages. Fundamentals of theoretical computer science. (English) Zbl 0569.68042
Computer Science and Applied Mathematics. Orlando etc.: Academic Press (Harcourt Brace Jovanovich, Publishers). XIX, 425 p., $ 35.00 (1983).
Reviewer: Gh.Păun
Church’s thesis without tears. (English) Zbl 0527.03036
Complexity theory on real numbers and functions. (English) Zbl 0501.03025
Theoretical computer science, 6th GI-Conf., Dortmund 1983, Lect. Notes Comput. Sci. 145, 165-174 (1982).
Church’s thesis and principles for mechanisms. (English) Zbl 0465.03022
The Kleene Symp., Proc., Madison/Wis. 1978, Stud. Logic Found. Math., Vol. 101, 123-148 (1980).
Computing in algebraic systems. (English) Zbl 0415.03035
Math. Cent., Amst., Afd. Inf. IW130/80, 21 p. (1980).
Introduction to mathematical logic. Set theory, computable functions, model theory. (English) Zbl 0407.03001
Undergraduate Texts in Mathematics. New York, Heidelberg, Berlin: Springer-Verlag XII, 198 p. DM 28.00; $ 15.40 (1979).
Studies in the theory of computational complexity and formal languages. (Issledovanie po teorii sloznosti vycislenii i formal’nym jazykam.). (Russian) Zbl 0408.03035
Akademija Nauk Ukrainskoi SSR, Institut Prikladnoi Matematiki i Mehaniki. Kiev: Izdatel’stvo ”Naukova Dumka”. 173 p. R. 1.40 (1978).
An uncompletable function. (English) Zbl 0186.01002
Filter Results by …
Document Type
- Journal Articles (55)
- Collection Articles (16)
- Books (15)
all
top 5
Author
- Weihrauch, Klaus (5)
- Tucker, John V. (4)
- Brattka, Vasco (3)
- Shönfield, Joseph R. (3)
- Campagnolo, Manuel Lameiras (2)
- Dunham, Charles B. (2)
- Lewis, Alain A. (2)
- Lisovik, Leonid P. (2)
- Marchenkov, Sergeĭ Serafimovich (2)
- Moldestad, Johan (2)
- Ojakian, Kerry (2)
- Pakhomov, S. V. (2)
- Stoltenberg-Hansen, Viggo (2)
- Velupillai, Kumaraswamy (Vela) (2)
- Aberth, Oliver George (1)
- Amir, Amihood (1)
- Arbib, Michael A. (1)
- Asperti, Andrea (1)
- Baliga, Ganesh R. (1)
- Barashko, A. S. (1)
- Bard, Vittorio (1)
- Baumes, Jeffrey (1)
- Bel’tyukov, Anatoliĭ Petrovich (1)
- Bienvenu, Laurent (1)
- Black, Robert (1)
- Blum, Lenore (1)
- Bridges, Douglas Suth (1)
- Bringsjord, Selmer (1)
- Case, John (1)
- Chinchilla, Eugenio (1)
- Choueka, Yaacov (1)
- Clote, Peter G. (1)
- Cohen, Daniel E. (1)
- Colombo, João Guilherme Fritsche (1)
- Cook, Stephen Arthur (1)
- Costa, José Félix (1)
- Dai, Jingan (1)
- Davie, George (1)
- Davis, Martin David (1)
- De Brecht, Matthew (1)
- Dershowitz, Nachum (1)
- Gandy, Robin O. (1)
- Gärtner, Tobias (1)
- Gashkov, Sergey B. (1)
- Gherardi, Guido (1)
- Gomaa, Walid E. (1)
- Gozzi, Riccardo (1)
- Graça, Daniel Silva (1)
- Gurevich, Yuri (1)
- Hertling, Peter H. (1)
- Hölzl, Rupert (1)
- Hoover, H. James (1)
- Horsten, Leon (1)
- Hotz, Günter (1)
- Jackson, Marcel G. (1)
- Jacopini, Giuseppe (1)
- Jain, Sanjay (1)
- Kapron, Bruce M. (1)
- Kawamura, Akitoshi (1)
- Kellett, Owen (1)
- Koepke, Peter (1)
- Kreitz, Christoph (1)
- Kuroda, Satoru (1)
- Latkin, E. I. (1)
- Li, Chuanxiang (1)
- Lipskaya, V. A. (1)
- Loff, Bruno (1)
- Malitz, Jerome I. (1)
- Marchi, Jerusa (1)
- Mazzanti, Stefano (1)
- McCarthy, Timothy G. (1)
- Monniaux, David P. (1)
- Morozov, Andreĭ Sergeevich (1)
- Mycka, Jerzy (1)
- Nabutovsky, Alexander (1)
- Nakano, Keisuke (1)
- Odifreddi, Piergiorgio (1)
- Patey, Ludovic (1)
- Pauly, Arno M. (1)
- Richman, Fred (1)
- Rojzen, S. I. (1)
- Ross, Kyle (1)
- Rustem, Berc (1)
- Sabadini, Nicoletta (1)
- Savitskiĭ, Igor Vladimirovich (1)
- Sazonov, Vladimir Yu. (1)
- Semënov, Alekseĭ L’vovich (1)
- Shapiro, Stewart (1)
- Shilliday, Andrew (1)
- Shkaravskaya, O. Yu. (1)
- Shub, Michael (1)
- Smale, Stephen (1)
- Soare, Robert I. (1)
- Song, Fangmin (1)
- Sontacchi, Giovanna (1)
- Spreen, Dieter (1)
- Stokes, Timothy E. (1)
- Suraj, Mandayam (1)
- Szabó, Zsolt (1)
- Taylor, Joshua A. (1)
- and 13 more Authors
all
top 5
Serial
- Inf. Comput. (4)
- J. Symb. Log. (3)
- Ann. Pure Appl. Logic (3)
- Arch. Math. Logic (3)
- Lect. Notes Log. (3)
- Math. Scand. (2)
- Notre Dame J. Formal Logic (2)
- SIAM J. Comput. (2)
- Theor. Comput. Sci. (2)
- Math. Soc. Sci. (2)
- Discrete Math. Appl. (2)
- Math. Log. Q. (2)
- Philos. Math. (3) (2)
- Am. Math. Mon. (1)
- Algebra Logic (1)
- Appl. Math. Comput. (1)
- J. Sov. Math. (1)
- Proc. Am. Math. Soc. (1)
- Mosc. Univ. Comput. Math. Cybern. (1)
- Cybernetics (1)
- J. Nanjing Univ., Nat. Sci. (1)
- J. Econ. Dyn. Control (1)
- Math. Struct. Comput. Sci. (1)
- Geom. Funct. Anal. (1)
- Int. J. Comput. Math. (1)
- Acta Math. Sci. (1)
- Cybern. Syst. Anal. (1)
- Vychisl. Sist. (1)
- Bull. Symb. Log. (1)
- Quadrature (1)
- Theory Comput. Syst. (1)
- J. ACM (1)
- Nat. Comput. (1)
- ACM Trans. Comput. Log. (1)
- Grad. Texts Math. (1)
- Math. Appl., Dordr. (1)
- Stud. Logic Found. Math. (1)
- Zap. Nauchn. Semin. Leningr. Otd. Mat. Inst. Steklova (1)
- Vestn. Samar. Gos. Tekh. Univ., Ser. Fiz.-Mat. Nauki (1)
- Computability (1)
- J. Log. Algebr. Methods Program. (1)
- Undergraduate Texts Math. (1)
all
top 5
Year of Publication
- 2023 (1)
- 2022 (1)
- 2021 (2)
- 2020 (1)
- 2018 (1)
- 2017 (1)
- 2016 (3)
- 2015 (2)
- 2012 (4)
- 2011 (2)
- 2009 (2)
- 2008 (4)
- 2007 (1)
- 2006 (3)
- 2003 (1)
- 2001 (3)
- 2000 (3)
- 1999 (2)
- 1998 (4)
- 1997 (5)
- 1996 (3)
- 1995 (1)
- 1994 (2)
- 1993 (3)
- 1992 (1)
- 1991 (2)
- 1990 (7)
- 1988 (2)
- 1987 (3)
- 1986 (2)
- 1985 (2)
- 1983 (2)
- 1982 (2)
- 1980 (4)
- 1979 (2)
- 1978 (1)
- 1968 (1)
Biographic Reference
- Ryde, Arne (1)
Software
- VAMPIRE (1)
