Search Results

Documents authored by Babu, Jasine

Document
DOI: 10.4230/LIPIcs.FSTTCS.2025.6
A Correct by Construction Fault Tolerant Voter for Input Selection of a Control System

Authors: Arif Ali AP, Jasine Babu, and Deepa Sara John

Published in: LIPIcs, Volume 360, 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)

Abstract
Safety-critical systems use redundant input units to improve their reliability and fault tolerance. A voting logic is then used to select a reliable input from the redundant sources. A fault detection and isolation rules help in selecting input units that can participate in voting. This work deals with the formal requirement formulation, design, verification and synthesis of a generic voting unit for an N-modular redundant measurement system used for control applications in avionics systems. The work follows a correct-by-construction approach, using the Rocq theorem prover.
Cite as

Arif Ali AP, Jasine Babu, and Deepa Sara John. A Correct by Construction Fault Tolerant Voter for Input Selection of a Control System. In 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 360, pp. 6:1-6:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{aliap_et_al:LIPIcs.FSTTCS.2025.6,
  author =	{Ali AP, Arif and Babu, Jasine and John, Deepa Sara},
  title =	{{A Correct by Construction Fault Tolerant Voter for Input Selection of a Control System}},
  booktitle =	{45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)},
  pages =	{6:1--6:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-406-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{360},
  editor =	{Aiswarya, C. and Mehta, Ruta and Roy, Subhajit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2025.6},
  URN =		{urn:nbn:de:0030-drops-250886},
  doi =		{10.4230/LIPIcs.FSTTCS.2025.6},
  annote =	{Keywords: Fault Tolerant System Design, Formal Verification, Correct by Construction, Input Selection, Interactive Theorem Proving}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2022.5
Packing Arc-Disjoint 4-Cycles in Oriented Graphs

Authors: Jasine Babu, R. Krithika, and Deepak Rajendraprasad

Published in: LIPIcs, Volume 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)

Abstract
Given a directed graph G and a positive integer k, the Arc Disjoint r-Cycle Packing problem asks whether G has k arc-disjoint r-cycles. We show that, for each integer r ≥ 3, Arc Disjoint r-Cycle Packing is NP-complete on oriented graphs with girth r. When r is even, the same result holds even when the input class is further restricted to be bipartite. On the positive side, focusing on r = 4 in oriented graphs, we study the complexity of the problem with respect to two parameterizations: solution size and vertex cover size. For the former, we give a cubic kernel with quadratic number of vertices. This is smaller than the compression size guaranteed by a reduction to the well-known 4-Set Packing. For the latter, we show fixed-parameter tractability using an unapparent integer linear programming formulation of an equivalent problem.
Cite as

Jasine Babu, R. Krithika, and Deepak Rajendraprasad. Packing Arc-Disjoint 4-Cycles in Oriented Graphs. In 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 250, pp. 5:1-5:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{babu_et_al:LIPIcs.FSTTCS.2022.5,
  author =	{Babu, Jasine and Krithika, R. and Rajendraprasad, Deepak},
  title =	{{Packing Arc-Disjoint 4-Cycles in Oriented Graphs}},
  booktitle =	{42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)},
  pages =	{5:1--5:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-261-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{250},
  editor =	{Dawar, Anuj and Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2022.5},
  URN =		{urn:nbn:de:0030-drops-173979},
  doi =		{10.4230/LIPIcs.FSTTCS.2022.5},
  annote =	{Keywords: arc-disjoint cycles, bipartite digraphs, oriented graphs, parameterized complexity}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2016.21
Every Property of Outerplanar Graphs is Testable

Authors: Jasine Babu, Areej Khoury, and Ilan Newman

Published in: LIPIcs, Volume 60, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)

Abstract
A D-disc around a vertex v of a graph G=(V,E) is the subgraph induced by all vertices of distance at most D from v. We show that the structure of an outerplanar graph on n vertices is determined, up to modification (insertion or deletion) of at most epsilon n edges, by a set of D-discs around the vertices, for D=D(epsilon) that is independent of the size of the graph. Such a result was already known for planar graphs (and any hyperfinite graph class), in the limited case of bounded degree graphs (that is, their maximum degree is bounded by some fixed constant, independent of |V|). We prove this result with no assumption on the degree of the graph. A pure combinatorial consequence of this result is that two outerplanar graphs that share the same local views are close to be isomorphic. We also obtain the following property testing results in the sparse graph model: * graph isomorphism is testable for outerplanar graphs by poly(log n) queries. * every graph property is testable for outerplanar graphs by poly(log n) queries. We note that we can replace outerplanar graphs by a slightly more general family of k-edge-outerplanar graphs. The only previous general testing results, as above, where known for forests (Kusumoto and Yoshida), and for some power-law graphs that are extremely close to be bounded degree hyperfinite (by Ito).
Cite as

Jasine Babu, Areej Khoury, and Ilan Newman. Every Property of Outerplanar Graphs is Testable. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 60, pp. 21:1-21:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{babu_et_al:LIPIcs.APPROX-RANDOM.2016.21,
  author =	{Babu, Jasine and Khoury, Areej and Newman, Ilan},
  title =	{{Every Property of Outerplanar Graphs is Testable}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)},
  pages =	{21:1--21:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-018-7},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{60},
  editor =	{Jansen, Klaus and Mathieu, Claire and Rolim, Jos\'{e} D. P. and Umans, Chris},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2016.21},
  URN =		{urn:nbn:de:0030-drops-66448},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2016.21},
  annote =	{Keywords: Property testing, Isomorphism, Outerplanar graphs}
}
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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact