3 Search Results for "Facchini, Alessandro"

Document
DOI: 10.4230/LIPIcs.CALCO.2019.10
A Coalgebraic Perspective on Probabilistic Logic Programming

Authors: Tao Gu and Fabio Zanasi

Published in: LIPIcs, Volume 139, 8th Conference on Algebra and Coalgebra in Computer Science (CALCO 2019)

Abstract
Probabilistic logic programming is increasingly important in artificial intelligence and related fields as a formalism to reason about uncertainty. It generalises logic programming with the possibility of annotating clauses with probabilities. This paper proposes a coalgebraic perspective on probabilistic logic programming. Programs are modelled as coalgebras for a certain functor F, and two semantics are given in terms of cofree coalgebras. First, the cofree F-coalgebra yields a semantics in terms of derivation trees. Second, by embedding F into another type G, as cofree G-coalgebra we obtain a "possible worlds" interpretation of programs, from which one may recover the usual distribution semantics of probabilistic logic programming.
Cite as

Tao Gu and Fabio Zanasi. A Coalgebraic Perspective on Probabilistic Logic Programming. In 8th Conference on Algebra and Coalgebra in Computer Science (CALCO 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 139, pp. 10:1-10:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{gu_et_al:LIPIcs.CALCO.2019.10,
  author =	{Gu, Tao and Zanasi, Fabio},
  title =	{{A Coalgebraic Perspective on Probabilistic Logic Programming}},
  booktitle =	{8th Conference on Algebra and Coalgebra in Computer Science (CALCO 2019)},
  pages =	{10:1--10:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-120-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{139},
  editor =	{Roggenbach, Markus and Sokolova, Ana},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CALCO.2019.10},
  URN =		{urn:nbn:de:0030-drops-114387},
  doi =		{10.4230/LIPIcs.CALCO.2019.10},
  annote =	{Keywords: probabilistic logic programming, coalgebraic semantics, distribution semantics}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2011.363
Definable Operations On Weakly Recognizable Sets of Trees

Authors: Jacques Duparc, Alessandro Facchini, and Filip Murlak

Published in: LIPIcs, Volume 13, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)

Abstract
Alternating automata on infinite trees induce operations on languages which do not preserve natural equivalence relations, like having the same Mostowski--Rabin index, the same Borel rank, or being continuously reducible to each other (Wadge equivalence). In order to prevent this, alternation needs to be restricted to the choice of direction in the tree. For weak alternating automata with restricted alternation a small set of computable operations generates all definable operations, which implies that the Wadge degree of a given automaton is computable. The weak index and the Borel rank coincide, and are computable. An equivalent automaton of minimal index can be computed in polynomial time (if the productive states of the automaton are given).
Cite as

Jacques Duparc, Alessandro Facchini, and Filip Murlak. Definable Operations On Weakly Recognizable Sets of Trees. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 13, pp. 363-374, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{duparc_et_al:LIPIcs.FSTTCS.2011.363,
  author =	{Duparc, Jacques and Facchini, Alessandro and Murlak, Filip},
  title =	{{Definable Operations On Weakly Recognizable Sets of Trees}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)},
  pages =	{363--374},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-34-7},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{13},
  editor =	{Chakraborty, Supratik and Kumar, Amit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2011.363},
  URN =		{urn:nbn:de:0030-drops-33361},
  doi =		{10.4230/LIPIcs.FSTTCS.2011.363},
  annote =	{Keywords: alternating automata, Wadge hierarchy, index hierarchy}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2009.2312
The Wadge Hierarchy of Max-Regular Languages

Authors: Jérémie Cabessa, Jacques Duparc, Alessandro Facchini, and Filip Murlak

Published in: LIPIcs, Volume 4, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2009)

Abstract
Recently, Miko{\l}aj Boja{\'n}czyk introduced a class of max-regular languages, an extension of regular languages of infinite words preserving manyof its usual properties. This new class can be seen as a different way of generalising the notion of regularity from finite to infinite words. This paper compares regular and max-regular languages in terms of topological complexity.It is proved that up to Wadge equivalence the classes coincide. Moreover, when restricted to $\mathbf{\Delta}^0_2$-languages, the classes contain virtually the same languages. On the other hand, separating examples of arbitrary complexity exceeding $\mathbf{\Delta}^0_2$ are constructed.
Cite as

Jérémie Cabessa, Jacques Duparc, Alessandro Facchini, and Filip Murlak. The Wadge Hierarchy of Max-Regular Languages. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 4, pp. 121-132, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{cabessa_et_al:LIPIcs.FSTTCS.2009.2312,
  author =	{Cabessa, J\'{e}r\'{e}mie and Duparc, Jacques and Facchini, Alessandro and Murlak, Filip},
  title =	{{The Wadge Hierarchy of Max-Regular Languages}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science},
  pages =	{121--132},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-13-2},
  ISSN =	{1868-8969},
  year =	{2009},
  volume =	{4},
  editor =	{Kannan, Ravi and Narayan Kumar, K.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2009.2312},
  URN =		{urn:nbn:de:0030-drops-23122},
  doi =		{10.4230/LIPIcs.FSTTCS.2009.2312},
  annote =	{Keywords: Max-regular languages, Wadge hierarchy, Wagner hierarchy}
}
  • Refine by Author
  • 2 Duparc, Jacques
  • 2 Facchini, Alessandro
  • 2 Murlak, Filip
  • 1 Cabessa, Jérémie
  • 1 Gu, Tao
  • Show More...

  • Refine by Classification
  • 1 Theory of computation
  • 1 Theory of computation → Logic

  • Refine by Keyword
  • 2 Wadge hierarchy
  • 1 Max-regular languages
  • 1 Wagner hierarchy
  • 1 alternating automata
  • 1 coalgebraic semantics
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 1 2009
  • 1 2011
  • 1 2019

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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact