4 Search Results for "Kov�r, Martin Maria"


Document
Randomness and Effective Dimension of Continued Fractions

Authors: Satyadev Nandakumar and Prateek Vishnoi

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)


Abstract
Recently, Scheerer [Adrian-Maria Scheerer, 2017] and Vandehey [Vandehey, 2016] showed that normality for continued fraction expansions and base-b expansions are incomparable notions. This shows that at some level, randomness for continued fractions and binary expansion are different statistical concepts. In contrast, we show that the continued fraction expansion of a real is computably random if and only if its binary expansion is computably random. To quantify the degree to which a continued fraction fails to be effectively random, we define the effective Hausdorff dimension of individual continued fractions, explicitly constructing continued fractions with dimension 0 and 1.

Cite as

Satyadev Nandakumar and Prateek Vishnoi. Randomness and Effective Dimension of Continued Fractions. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 73:1-73:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{nandakumar_et_al:LIPIcs.MFCS.2020.73,
  author =	{Nandakumar, Satyadev and Vishnoi, Prateek},
  title =	{{Randomness and Effective Dimension of Continued Fractions}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{73:1--73:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Esparza, Javier and Kr\'{a}l', Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.73},
  URN =		{urn:nbn:de:0030-drops-127424},
  doi =		{10.4230/LIPIcs.MFCS.2020.73},
  annote =	{Keywords: Continued fractions, Martin-L\"{o}f randomness, Computable randomness, effective Fractal dimension}
}
Document
Normalization by Evaluation for Typed Weak lambda-Reduction

Authors: Filippo Sestini

Published in: LIPIcs, Volume 130, 24th International Conference on Types for Proofs and Programs (TYPES 2018)


Abstract
Weak reduction relations in the lambda-calculus are characterized by the rejection of the so-called xi-rule, which allows arbitrary reductions under abstractions. A notable instance of weak reduction can be found in the literature under the name restricted reduction or weak lambda-reduction. In this work, we attack the problem of algorithmically computing normal forms for lambda-wk, the lambda-calculus with weak lambda-reduction. We do so by first contrasting it with other weak systems, arguing that their notion of reduction is not strong enough to compute lambda-wk-normal forms. We observe that some aspects of weak lambda-reduction prevent us from normalizing lambda-wk directly, thus devise a new, better-behaved weak calculus lambda-ex, and reduce the normalization problem for lambda-w to that of lambda-ex. We finally define type systems for both calculi and apply Normalization by Evaluation to lambda-ex, obtaining a normalization proof for lambda-wk as a corollary. We formalize all our results in Agda, a proof-assistant based on intensional Martin-Löf Type Theory.

Cite as

Filippo Sestini. Normalization by Evaluation for Typed Weak lambda-Reduction. In 24th International Conference on Types for Proofs and Programs (TYPES 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 130, pp. 6:1-6:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{sestini:LIPIcs.TYPES.2018.6,
  author =	{Sestini, Filippo},
  title =	{{Normalization by Evaluation for Typed Weak lambda-Reduction}},
  booktitle =	{24th International Conference on Types for Proofs and Programs (TYPES 2018)},
  pages =	{6:1--6:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-106-1},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{130},
  editor =	{Dybjer, Peter and Esp{\'\i}rito Santo, Jos\'{e} and Pinto, Lu{\'\i}s},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TYPES.2018.6},
  URN =		{urn:nbn:de:0030-drops-114101},
  doi =		{10.4230/LIPIcs.TYPES.2018.6},
  annote =	{Keywords: normalization, lambda-calculus, reduction, term-rewriting, Agda}
}
Document
An Extensional Kleene Realizability Semantics for the Minimalist Foundation

Authors: Maria Emilia Maietti and Samuele Maschio

Published in: LIPIcs, Volume 39, 20th International Conference on Types for Proofs and Programs (TYPES 2014)


Abstract
We build a Kleene realizability semantics for the two-level Minimalist Foundation MF, ideated by Maietti and Sambin in 2005 and completed by Maietti in 2009. Thanks to this semantics we prove that both levels of MF are consistent with the formal Church Thesis CT. Since MF consists of two levels, an intensional one, called mtt, and an extensional one, called emtt, linked by an interpretation, it is enough to build a realizability semantics for the intensional level mtt to get one for the extensional one emtt, too. Moreover, both levels consists of type theories based on versions of Martin-Löf's type theory. Our realizability semantics for mtt is a modification of the realizability semantics by Beeson in 1985 for extensional first order Martin-Löf's type theory with one universe. So it is formalized in Feferman's classical arithmetic theory of inductive definitions, called ID1^. It is called extensional Kleene realizability semantics since it validates extensional equality of type-theoretic functions extFun, as in Beeson's one. The main modification we perform on Beeson's semantics is to interpret propositions, which are defined primitively in MF, in a proof-irrelevant way. As a consequence, we gain the validity of CT. Recalling that extFun+CT+AC are inconsistent over arithmetics with finite types, we conclude that our semantics does not validate the Axiom of Choice AC on generic types. On the contrary, Beeson's semantics does validate AC, being this a theorem of Martin-Löf's theory, but it does not validate CT. The semantics we present here seems to be the best approximation of Kleene realizability for the extensional level emtt. Indeed Beeson's semantics is not an option for emtt since AC on generic sets added to it entails the excluded middle.

Cite as

Maria Emilia Maietti and Samuele Maschio. An Extensional Kleene Realizability Semantics for the Minimalist Foundation. In 20th International Conference on Types for Proofs and Programs (TYPES 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 39, pp. 162-186, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@InProceedings{maietti_et_al:LIPIcs.TYPES.2014.162,
  author =	{Maietti, Maria Emilia and Maschio, Samuele},
  title =	{{An Extensional Kleene Realizability Semantics for the Minimalist Foundation}},
  booktitle =	{20th International Conference on Types for Proofs and Programs (TYPES 2014)},
  pages =	{162--186},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-88-0},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{39},
  editor =	{Herbelin, Hugo and Letouzey, Pierre and Sozeau, Matthieu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TYPES.2014.162},
  URN =		{urn:nbn:de:0030-drops-54966},
  doi =		{10.4230/LIPIcs.TYPES.2014.162},
  annote =	{Keywords: Realizability, Type Theory, formal Church Thesis}
}
Document
Instant topological relationships hidden in the reality

Authors: Martin Maria Kovár

Published in: Dagstuhl Seminar Proceedings, Volume 6341, Computational Structures for Modelling Space, Time and Causality (2007)


Abstract
In most applications of general topology, topology usually is not the first, primary structure, but the information which finally leads to the construction of the certain, for some purpose required topology, is filtered by more or less thick filter of the other mathematical structures. This fact has two main consequences: (1) Most important applied constructions may be done in the primary structure, bypassing the topology. (2) Some topologically important information from the reality may be lost (filtered out by the other, front-end mathematical structures). Thus some natural and direct connection between topology and the reality could be useful. In this contribution we will discuss a pointless topological structure which directly reflects relationship between various locations which are glued together by possible presence of a physical object or a virtual ``observer".

Cite as

Martin Maria Kovár. Instant topological relationships hidden in the reality. In Computational Structures for Modelling Space, Time and Causality. Dagstuhl Seminar Proceedings, Volume 6341, pp. 1-2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)


Copy BibTex To Clipboard

@InProceedings{kovar:DagSemProc.06341.6,
  author =	{Kov\'{a}r, Martin Maria},
  title =	{{Instant topological relationships hidden in the reality}},
  booktitle =	{Computational Structures for Modelling Space, Time and Causality},
  pages =	{1--2},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{6341},
  editor =	{Ralph Kopperman and Prakash Panangaden and Michael B. Smyth and Dieter Spreen},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.06341.6},
  URN =		{urn:nbn:de:0030-drops-8962},
  doi =		{10.4230/DagSemProc.06341.6},
  annote =	{Keywords: Pointless topology, reality}
}
  • Refine by Author
  • 1 Kovár, Martin Maria
  • 1 Maietti, Maria Emilia
  • 1 Maschio, Samuele
  • 1 Nandakumar, Satyadev
  • 1 Sestini, Filippo
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Computability
  • 1 Theory of computation → Constructive mathematics
  • 1 Theory of computation → Lambda calculus

  • Refine by Keyword
  • 1 Agda
  • 1 Computable randomness
  • 1 Continued fractions
  • 1 Martin-Löf randomness
  • 1 Pointless topology
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 1 2007
  • 1 2015
  • 1 2019
  • 1 2020

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail