3 Search Results for "Dries, Anton"

Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2025.163
Verification of Linear Dynamical Systems via O-Minimality of the Real Numbers

Authors: Toghrul Karimov

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
A discrete-time linear dynamical system (LDS) is given by an update matrix M ∈ ℝ^{d× d}, and has the trajectories ⟨s, Ms, M²s, …⟩ for s ∈ ℝ^d. Reachability-type decision problems of linear dynamical systems, most notably the Skolem Problem, lie at the forefront of decidability: typically, sound and complete algorithms are known only in low dimensions, and these rely on sophisticated tools from number theory and Diophantine approximation. Recently, however, o-minimality has emerged as a counterpoint to these number-theoretic tools that allows us to decide certain modifications of the classical problems of LDS without any dimension restrictions. In this paper, we first introduce the Decomposition Method, a framework that captures all applications of o-minimality to decision problems of LDS that are currently known to us. We then use the Decomposition Method to show decidability of the Robust Safety Problem (restricted to bounded initial sets) in arbitrary dimension: given a matrix M, a bounded semialgebraic set S of initial points, and a semialgebraic set T of unsafe points, it is decidable whether there exists ε > 0 such that all orbits that begin in the ε-ball around S avoid T.
Cite as

Toghrul Karimov. Verification of Linear Dynamical Systems via O-Minimality of the Real Numbers. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 163:1-163:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{karimov:LIPIcs.ICALP.2025.163,
  author =	{Karimov, Toghrul},
  title =	{{Verification of Linear Dynamical Systems via O-Minimality of the Real Numbers}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{163:1--163:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.163},
  URN =		{urn:nbn:de:0030-drops-235401},
  doi =		{10.4230/LIPIcs.ICALP.2025.163},
  annote =	{Keywords: Linear dynamical systems, reachability problems, o-minimality}
}
Document
DOI: 10.4230/OASIcs.Gabbrielli.11
Derivation of Constraints from Machine Learning Models and Applications to Security and Privacy

Authors: Moreno Falaschi, Catuscia Palamidessi, and Marco Romanelli

Published in: OASIcs, Volume 86, Recent Developments in the Design and Implementation of Programming Languages (2020)

Abstract
This paper shows how we can combine the power of machine learning with the flexibility of constraints. More specifically, we show how machine learning models can be represented by first-order logic theories, and how to derive these theories. The advantage of this representation is that it can be augmented with additional formulae, representing constraints of some kind on the data domain. For instance, new knowledge, or potential attackers, or fairness desiderata. We consider various kinds of learning algorithms (neural networks, k-nearest-neighbours, decision trees, support vector machines) and for each of them we show how to infer the FOL formulae. Then we focus on one particular application domain, namely the field of security and privacy. The idea is to represent the potentialities and goals of the attacker as a set of constraints, then use a constraint solver (more precisely, a solver modulo theories) to verify the satisfiability. If a solution exists, then it means that an attack is possible, otherwise, the system is safe. We show various examples from different areas of security and privacy; specifically, we consider a side-channel attack on a password checker, a malware attack on smart health systems, and a model-inversion attack on a neural network.
Cite as

Moreno Falaschi, Catuscia Palamidessi, and Marco Romanelli. Derivation of Constraints from Machine Learning Models and Applications to Security and Privacy. In Recent Developments in the Design and Implementation of Programming Languages. Open Access Series in Informatics (OASIcs), Volume 86, pp. 11:1-11:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{falaschi_et_al:OASIcs.Gabbrielli.11,
  author =	{Falaschi, Moreno and Palamidessi, Catuscia and Romanelli, Marco},
  title =	{{Derivation of Constraints from Machine Learning Models and Applications to Security and Privacy}},
  booktitle =	{Recent Developments in the Design and Implementation of Programming Languages},
  pages =	{11:1--11:20},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-171-9},
  ISSN =	{2190-6807},
  year =	{2020},
  volume =	{86},
  editor =	{de Boer, Frank S. and Mauro, Jacopo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Gabbrielli.11},
  URN =		{urn:nbn:de:0030-drops-132338},
  doi =		{10.4230/OASIcs.Gabbrielli.11},
  annote =	{Keywords: Constraints, machine learning, privacy, security}
}
Document
DOI: 10.4230/OASIcs.ICLP.2018.6
Improving Candidate Quality of Probabilistic Logic Models

Authors: Joana Côrte-Real, Anton Dries, Inês Dutra, and Ricardo Rocha

Published in: OASIcs, Volume 64, Technical Communications of the 34th International Conference on Logic Programming (ICLP 2018)

Abstract
Many real-world phenomena exhibit both relational structure and uncertainty. Probabilistic Inductive Logic Programming (PILP) uses Inductive Logic Programming (ILP) extended with probabilistic facts to produce meaningful and interpretable models for real-world phenomena. This merge between First Order Logic (FOL) theories and uncertainty makes PILP a very adequate tool for knowledge representation and extraction. However, this flexibility is coupled with a problem (inherited from ILP) of exponential search space growth and so, often, only a subset of all possible models is explored due to limited resources. Furthermore, the probabilistic evaluation of FOL theories, coming from the underlying probabilistic logic language and its solver, is also computationally demanding. This work introduces a prediction-based pruning strategy, which can reduce the search space based on the probabilistic evaluation of models, and a safe pruning criterion, which guarantees that the optimal model is not pruned away, as well as two alternative more aggressive criteria that do not provide this guarantee. Experiments performed using three benchmarks from different areas show that prediction pruning is effective in (i) maintaining predictive accuracy for all criteria and experimental settings; (ii) reducing the execution time when using some of the more aggressive criteria, compared to using no pruning; and (iii) selecting better candidate models in limited resource settings, also when compared to using no pruning.
Cite as

Joana Côrte-Real, Anton Dries, Inês Dutra, and Ricardo Rocha. Improving Candidate Quality of Probabilistic Logic Models. In Technical Communications of the 34th International Conference on Logic Programming (ICLP 2018). Open Access Series in Informatics (OASIcs), Volume 64, pp. 6:1-6:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{cortereal_et_al:OASIcs.ICLP.2018.6,
  author =	{C\^{o}rte-Real, Joana and Dries, Anton and Dutra, In\^{e}s and Rocha, Ricardo},
  title =	{{Improving Candidate Quality of Probabilistic Logic Models}},
  booktitle =	{Technical Communications of the 34th International Conference on Logic Programming (ICLP 2018)},
  pages =	{6:1--6:14},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-090-3},
  ISSN =	{2190-6807},
  year =	{2018},
  volume =	{64},
  editor =	{Dal Palu', Alessandro and Tarau, Paul and Saeedloei, Neda and Fodor, Paul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ICLP.2018.6},
  URN =		{urn:nbn:de:0030-drops-98722},
  doi =		{10.4230/OASIcs.ICLP.2018.6},
  annote =	{Keywords: Relational Machine Learning, Probabilistic Inductive Logic Programming, Search Space Pruning, Model Quality, Experiments}
}
  • Refine by Type
  • 3 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2025
  • 1 2020
  • 1 2018

  • Refine by Author
  • 1 Côrte-Real, Joana
  • 1 Dries, Anton
  • 1 Dutra, Inês
  • 1 Falaschi, Moreno
  • 1 Karimov, Toghrul
  • Show More...

  • Refine by Series/Journal
  • 1 LIPIcs
  • 2 OASIcs

  • Refine by Classification
  • 1 Computing methodologies → Learning paradigms
  • 1 Computing methodologies → Probabilistic reasoning
  • 1 Computing methodologies → Symbolic and algebraic manipulation
  • 1 Security and privacy → Formal security models
  • 1 Security and privacy → Information flow control
  • Show More...

  • Refine by Keyword
  • 1 Constraints
  • 1 Experiments
  • 1 Linear dynamical systems
  • 1 Model Quality
  • 1 Probabilistic Inductive Logic Programming
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact