3 Search Results for "Maler, Oded"

Document
DOI: 10.4230/LIPIcs.CALCO.2019.5
Omega-Automata: A Coalgebraic Perspective on Regular omega-Languages

Authors: Vincenzo Ciancia and Yde Venema

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

Abstract
In this work, we provide a simple coalgebraic characterisation of regular omega-languages based on languages of lassos, and prove a number of related mathematical results, framed into the theory of a new kind of automata called Omega-automata. In earlier work we introduced Omega-automata as two-sorted structures that naturally operate on lassos, pairs of words encoding ultimately periodic streams (infinite words). Here we extend the scope of these Omega-automata by proposing them as a new kind of acceptor for arbitrary streams. We prove that Omega-automata are expressively complete for the regular omega-languages. We show that, due to their coalgebraic nature, Omega-automata share some attractive properties with deterministic automata operating on finite words, properties that other types of stream automata lack. In particular, we provide a simple, coalgebraic definition of bisimilarity between Omega-automata that exactly captures language equivalence and allows for a simple minimization procedure. We also prove a coalgebraic Myhill-Nerode style theorem for lasso languages, and use this result, in combination with a closure property on stream languages called lasso determinacy, to give a characterization of regular omega-languages.
Cite as

Vincenzo Ciancia and Yde Venema. Omega-Automata: A Coalgebraic Perspective on Regular omega-Languages. In 8th Conference on Algebra and Coalgebra in Computer Science (CALCO 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 139, pp. 5:1-5:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{ciancia_et_al:LIPIcs.CALCO.2019.5,
  author =	{Ciancia, Vincenzo and Venema, Yde},
  title =	{{Omega-Automata: A Coalgebraic Perspective on Regular omega-Languages}},
  booktitle =	{8th Conference on Algebra and Coalgebra in Computer Science (CALCO 2019)},
  pages =	{5:1--5:18},
  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.5},
  URN =		{urn:nbn:de:0030-drops-114338},
  doi =		{10.4230/LIPIcs.CALCO.2019.5},
  annote =	{Keywords: omega-automata, regular omega-languages, coalgebra, streams, bisimilarity}
}
Document
DOI: 10.4230/DagRep.9.2.48
Specification Formalisms for Modern Cyber-Physical Systems (Dagstuhl Seminar 19071)

Authors: Jyotirmoy V. Deshmukh, Oded Maler, and Dejan Nickovic

Published in: Dagstuhl Reports, Volume 9, Issue 2 (2019)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 19071 "Specification Formalisms for Modern Cyber-Physical Systems." Specifications play a major role in evaluating behaviors of modern cyber-physical systems (CPS). There is currently no specification language that allows joint description of safety, performance, security, privacy, and reliability aspects of CPS applications. The Dagstuhl seminar brought together researchers and practitioners from formal methods, control theory, machine learning and robotics to discuss the state-of-the-art and open challenges in specifying properties of modern CPS. Special attention was given to exploring the intersection of machine learning and formal specification languages, where formal specifications can serve as a bridge between the world of verification and the world of learning and data-mining.
Cite as

Jyotirmoy V. Deshmukh, Oded Maler, and Dejan Nickovic. Specification Formalisms for Modern Cyber-Physical Systems (Dagstuhl Seminar 19071). In Dagstuhl Reports, Volume 9, Issue 2, pp. 48-72, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@Article{deshmukh_et_al:DagRep.9.2.48,
  author =	{Deshmukh, Jyotirmoy V. and Maler, Oded and Nickovic, Dejan},
  title =	{{Specification Formalisms for Modern Cyber-Physical Systems (Dagstuhl Seminar 19071)}},
  pages =	{48--72},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2019},
  volume =	{9},
  number =	{2},
  editor =	{Deshmukh, Jyotirmoy V. and Maler, Oded and Nickovic, Dejan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.9.2.48},
  URN =		{urn:nbn:de:0030-drops-108581},
  doi =		{10.4230/DagRep.9.2.48},
  annote =	{Keywords: Cyber-physical systems, formal specifications, runtime verification and control}
}
Document
DOI: 10.4230/DagRep.8.2.88
Formal Methods for the Synthesis of Biomolecular Circuits (Dagstuhl Seminar 18082)

Authors: Yaakov Benenson, Neil Dalchau, Heinz Koeppl, and Oded Maler

Published in: Dagstuhl Reports, Volume 8, Issue 2 (2018)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 18082 "Formal Methods for the Synthesis of Biomolecular Circuits". Synthetic biology aims for the rational bottom-up engineering of new biological functionalities. Recent years have witnessed an increase in the degree of "rationality" in the design of synthetic biomolecular circuits. With it, fewer design-build-test cycles were necessary to achieve a desired circuit performance. Most of these success stories reported the realization of logic circuits, typically operating via regulation of gene expression and/or direct manipulation of DNA sequences with recombinases, executing combinatorial and sometimes sequential logic. This was often achieved with the help of two ingredients, a library of previously well-characterized parts and some computational modeling. Hence, although circuits in synthetic biology are still by far less understood and characterized than electronic circuits, the opportunity for the formal synthesis of circuit designs with respect to a behavioral specification starts to emerge in synthetic biology.
Cite as

Yaakov Benenson, Neil Dalchau, Heinz Koeppl, and Oded Maler. Formal Methods for the Synthesis of Biomolecular Circuits (Dagstuhl Seminar 18082). In Dagstuhl Reports, Volume 8, Issue 2, pp. 88-100, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@Article{benenson_et_al:DagRep.8.2.88,
  author =	{Benenson, Yaakov and Dalchau, Neil and Koeppl, Heinz and Maler, Oded},
  title =	{{Formal Methods for the Synthesis of Biomolecular Circuits (Dagstuhl Seminar 18082)}},
  pages =	{88--100},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2018},
  volume =	{8},
  number =	{2},
  editor =	{Benenson, Yaakov and Dalchau, Neil and Koeppl, Heinz and Maler, Oded},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.8.2.88},
  URN =		{urn:nbn:de:0030-drops-92912},
  doi =		{10.4230/DagRep.8.2.88},
  annote =	{Keywords: Synthetic biology, Electronic design automation, Program synthesis and verification}
}
  • Refine by Author
  • 2 Maler, Oded
  • 1 Benenson, Yaakov
  • 1 Ciancia, Vincenzo
  • 1 Dalchau, Neil
  • 1 Deshmukh, Jyotirmoy V.
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Automata over infinite objects
  • 1 Theory of computation → Formal languages and automata theory

  • Refine by Keyword
  • 1 Cyber-physical systems
  • 1 Electronic design automation
  • 1 Program synthesis and verification
  • 1 Synthetic biology
  • 1 bisimilarity
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 2 2019
  • 1 2018

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