4 Search Results for "J��skel�inen, Antti"

Document
DOI: 10.4230/LIPIcs.MFCS.2023.9
Descriptive Complexity for Distributed Computing with Circuits

Authors: Veeti Ahvonen, Damian Heiman, Lauri Hella, and Antti Kuusisto

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

Abstract
We consider distributed algorithms in the realistic scenario where distributed message passing is operated by circuits. We show that within this setting, modal substitution calculus MSC precisely captures the expressive power of circuits. The result is established via constructing translations that are highly efficient in relation to size. We also observe that the coloring algorithm based on Cole-Vishkin can be specified by logarithmic size programs (and thus also logarithmic size circuits) in the bounded-degree scenario.
Cite as

Veeti Ahvonen, Damian Heiman, Lauri Hella, and Antti Kuusisto. Descriptive Complexity for Distributed Computing with Circuits. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 9:1-9:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{ahvonen_et_al:LIPIcs.MFCS.2023.9,
  author =	{Ahvonen, Veeti and Heiman, Damian and Hella, Lauri and Kuusisto, Antti},
  title =	{{Descriptive Complexity for Distributed Computing with Circuits}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{9:1--9:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.9},
  URN =		{urn:nbn:de:0030-drops-185433},
  doi =		{10.4230/LIPIcs.MFCS.2023.9},
  annote =	{Keywords: Descriptive complexity, distributed computing, logic, graph coloring}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2021.62
Ordered Fragments of First-Order Logic

Authors: Reijo Jaakkola

Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)

Abstract
Using a recently introduced algebraic framework for classifying fragments of first-order logic, we study the complexity of the satisfiability problem for several ordered fragments of first-order logic, which are obtained from the ordered logic and the fluted logic by modifying some of their syntactical restrictions.
Cite as

Reijo Jaakkola. Ordered Fragments of First-Order Logic. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 62:1-62:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{jaakkola:LIPIcs.MFCS.2021.62,
  author =	{Jaakkola, Reijo},
  title =	{{Ordered Fragments of First-Order Logic}},
  booktitle =	{46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
  pages =	{62:1--62:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-201-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{202},
  editor =	{Bonchi, Filippo and Puglisi, Simon J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.62},
  URN =		{urn:nbn:de:0030-drops-145025},
  doi =		{10.4230/LIPIcs.MFCS.2021.62},
  annote =	{Keywords: ordered logic, fluted logic, complexity, decidability}
}
Document
DOI: 10.4230/LIPIcs.DNA.2020.7
Implementing Non-Equilibrium Networks with Active Circuits of Duplex Catalysts

Authors: Antti Lankinen, Ismael Mullor Ruiz, and Thomas E. Ouldridge

Published in: LIPIcs, Volume 174, 26th International Conference on DNA Computing and Molecular Programming (DNA 26) (2020)

Abstract
DNA strand displacement (DSD) reactions have been used to construct chemical reaction networks in which species act catalytically at the level of the overall stoichiometry of reactions. These effective catalytic reactions are typically realised through one or more of the following: many-stranded gate complexes to coordinate the catalysis, indirect interaction between the catalyst and its substrate, and the recovery of a distinct "catalyst" strand from the one that triggered the reaction. These facts make emulation of the out-of-equilibrium catalytic circuitry of living cells more difficult. Here, we propose a new framework for constructing catalytic DSD networks: Active Circuits of Duplex Catalysts (ACDC). ACDC components are all double-stranded complexes, with reactions occurring through 4-way strand exchange. Catalysts directly bind to their substrates, and the "identity" strand of the catalyst recovered at the end of a reaction is the same molecule as the one that initiated it. We analyse the capability of the framework to implement catalytic circuits analogous to phosphorylation networks in living cells. We also propose two methods of systematically introducing mismatches within DNA strands to avoid leak reactions and introduce driving through net base pair formation. We then combine these results into a compiler to automate the process of designing DNA strands that realise any catalytic network allowed by our framework.
Cite as

Antti Lankinen, Ismael Mullor Ruiz, and Thomas E. Ouldridge. Implementing Non-Equilibrium Networks with Active Circuits of Duplex Catalysts. In 26th International Conference on DNA Computing and Molecular Programming (DNA 26). Leibniz International Proceedings in Informatics (LIPIcs), Volume 174, pp. 7:1-7:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{lankinen_et_al:LIPIcs.DNA.2020.7,
  author =	{Lankinen, Antti and Mullor Ruiz, Ismael and Ouldridge, Thomas E.},
  title =	{{Implementing Non-Equilibrium Networks with Active Circuits of Duplex Catalysts}},
  booktitle =	{26th International Conference on DNA Computing and Molecular Programming (DNA 26)},
  pages =	{7:1--7:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-163-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{174},
  editor =	{Geary, Cody and Patitz, Matthew J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.2020.7},
  URN =		{urn:nbn:de:0030-drops-129602},
  doi =		{10.4230/LIPIcs.DNA.2020.7},
  annote =	{Keywords: DNA strand displacement, Catalysis, Information-processing networks}
}
Document
DOI: 10.4230/OASIcs.SSV.2011.44
Verification of Safety-Critical Systems: A Case Study Report on Using Modern Model Checking Tools

Authors: Antti Jääskeläinen, Mika Katara, Shmuel Katz, and Heikki Virtanen

Published in: OASIcs, Volume 24, 6th International Workshop on Systems Software Verification (2012)

Abstract
paper, we describe a case study where a simple 2oo3 voting scheme for a shutdown system was verified using two bounded model checking tools, CBMC and EBMC. The system represents Systematic Capability level 3 according to IEC 61508 ed2.0. The verification process was based on requirements and pseudo code, and involved verifying C and Verilog code implementing the pseudo code. The results suggest that the tools were suitable for the task, but require considerable training to reach productive use for code embedded in industrial equipment. We also identified some issues in the development process that could be streamlined with the use of more formal verification methods. Towards the end of the paper, we discuss the issues we found and how to address them in a practical setting.
Cite as

Antti Jääskeläinen, Mika Katara, Shmuel Katz, and Heikki Virtanen. Verification of Safety-Critical Systems: A Case Study Report on Using Modern Model Checking Tools. In 6th International Workshop on Systems Software Verification. Open Access Series in Informatics (OASIcs), Volume 24, pp. 44-56, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{jaaskelainen_et_al:OASIcs.SSV.2011.44,
  author =	{J\"{a}\"{a}skel\"{a}inen, Antti and Katara, Mika and Katz, Shmuel and Virtanen, Heikki},
  title =	{{Verification of Safety-Critical Systems: A Case Study Report on Using Modern Model Checking Tools}},
  booktitle =	{6th International Workshop on Systems Software Verification},
  pages =	{44--56},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-36-1},
  ISSN =	{2190-6807},
  year =	{2012},
  volume =	{24},
  editor =	{Brauer, J\"{o}rg and Roveri, Marco and Tews, Hendrik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.SSV.2011.44},
  URN =		{urn:nbn:de:0030-drops-35891},
  doi =		{10.4230/OASIcs.SSV.2011.44},
  annote =	{Keywords: Functional safety, SIL-3, model checking, tools}
}
  • Refine by Author
  • 1 Ahvonen, Veeti
  • 1 Heiman, Damian
  • 1 Hella, Lauri
  • 1 Jaakkola, Reijo
  • 1 Jääskeläinen, Antti
  • Show More...

  • Refine by Classification
  • 1 Hardware → Biology-related information processing
  • 1 Networks → Network algorithms
  • 1 Theory of computation → Distributed algorithms
  • 1 Theory of computation → Finite Model Theory
  • 1 Theory of computation → Logic
  • Show More...

  • Refine by Keyword
  • 1 Catalysis
  • 1 DNA strand displacement
  • 1 Descriptive complexity
  • 1 Functional safety
  • 1 Information-processing networks
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 1 2012
  • 1 2020
  • 1 2021
  • 1 2023

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