5 Search Results for "G�mez-Zamalloa, Miguel"


Document
Track A: Algorithms, Complexity and Games
A 4/3 Approximation for 2-Vertex-Connectivity

Authors: Miguel Bosch-Calvo, Fabrizio Grandoni, and Afrouz Jabal Ameli

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)


Abstract
The 2-Vertex-Connected Spanning Subgraph problem (2VCSS) is among the most basic NP-hard (Survivable) Network Design problems: we are given an (unweighted) undirected graph G. Our goal is to find a subgraph S of G with the minimum number of edges which is 2-vertex-connected, namely S remains connected after the deletion of an arbitrary node. 2VCSS is well-studied in terms of approximation algorithms, and the current best (polynomial-time) approximation factor is 10/7 by Heeger and Vygen [SIDMA'17] (improving on earlier results by Khuller and Vishkin [STOC'92] and Garg, Vempala and Singla [SODA'93]). Here we present an improved 4/3 approximation. Our main technical ingredient is an approximation preserving reduction to a conveniently structured subset of instances which are "almost" 3-vertex-connected. The latter reduction might be helpful in future work.

Cite as

Miguel Bosch-Calvo, Fabrizio Grandoni, and Afrouz Jabal Ameli. A 4/3 Approximation for 2-Vertex-Connectivity. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 29:1-29:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{boschcalvo_et_al:LIPIcs.ICALP.2023.29,
  author =	{Bosch-Calvo, Miguel and Grandoni, Fabrizio and Jabal Ameli, Afrouz},
  title =	{{A 4/3 Approximation for 2-Vertex-Connectivity}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{29:1--29:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.29},
  URN =		{urn:nbn:de:0030-drops-180813},
  doi =		{10.4230/LIPIcs.ICALP.2023.29},
  annote =	{Keywords: Algorithm, Network Design, Vertex-Connectivity, Approximation}
}
Document
Invited Paper
Challenges and Opportunities in C/C++ Source-To-Source Compilation (Invited Paper)

Authors: João Bispo, Nuno Paulino, and Luís Miguel Sousa

Published in: OASIcs, Volume 107, 14th Workshop on Parallel Programming and Run-Time Management Techniques for Many-Core Architectures and 12th Workshop on Design Tools and Architectures for Multicore Embedded Computing Platforms (PARMA-DITAM 2023)


Abstract
The C/C++ compilation stack (Intermediate Representations (IR), compilation passes and backends) is encumbered by a steep learning curve, which we believe can be lowered by complementing it with approaches such as source-to-source compilation. Source-to-source compilation is a technology that is widely used and quite mature in certain programming environments, such as JavaScript, but that faces a low adoption rate in others. In the particular case of C and C++ some of the identified factors include the high complexity of the languages, increased difficulty in building and maintaining C/C++ parsers, or limitations on using source code as an intermediate representation. Additionally, new technologies such as Multi-Level Intermediate Representation (MLIR) have appeared as potential competitors to source-to-source compilers at this level. In this paper, we present what we have identified as current challenges of source-to-source compilation of C and C++, as well as what we consider to be opportunities and possible directions forward. We also present several examples, implemented on top of the Clava source-to-source compiler, that use some of these ideas and techniques to raise the abstraction level of compiler research on complex compiled languages such as C or C++. The examples include automatic parallelization of for loops, high-level synthesis optimisation, hardware/software partitioning with run-time decisions, and automatic insertion of inline assembly for fast prototyping of custom instructions.

Cite as

João Bispo, Nuno Paulino, and Luís Miguel Sousa. Challenges and Opportunities in C/C++ Source-To-Source Compilation (Invited Paper). In 14th Workshop on Parallel Programming and Run-Time Management Techniques for Many-Core Architectures and 12th Workshop on Design Tools and Architectures for Multicore Embedded Computing Platforms (PARMA-DITAM 2023). Open Access Series in Informatics (OASIcs), Volume 107, pp. 2:1-2:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{bispo_et_al:OASIcs.PARMA-DITAM.2023.2,
  author =	{Bispo, Jo\~{a}o and Paulino, Nuno and Sousa, Lu{\'\i}s Miguel},
  title =	{{Challenges and Opportunities in C/C++ Source-To-Source Compilation}},
  booktitle =	{14th Workshop on Parallel Programming and Run-Time Management Techniques for Many-Core Architectures and 12th Workshop on Design Tools and Architectures for Multicore Embedded Computing Platforms (PARMA-DITAM 2023)},
  pages =	{2:1--2:15},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-269-3},
  ISSN =	{2190-6807},
  year =	{2023},
  volume =	{107},
  editor =	{Bispo, Jo\~{a}o and Charles, Henri-Pierre and Cherubin, Stefano and Massari, Giuseppe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.PARMA-DITAM.2023.2},
  URN =		{urn:nbn:de:0030-drops-177225},
  doi =		{10.4230/OASIcs.PARMA-DITAM.2023.2},
  annote =	{Keywords: Source-to-source, compilation, transpilers, C/C++, code transformation}
}
Document
Contract-Java: Design by Contract in Java with Safe Error Handling

Authors: Miguel Oliveira e Silva and Pedro G. Francisco

Published in: OASIcs, Volume 38, 3rd Symposium on Languages, Applications and Technologies (2014)


Abstract
Design by Contract (DbC) is a programming methodology in which the meaning of program entities, such as methods and classes, is made explicit by the use of programming predicates named assertions. A false assertion is always a manifestation of an incorrect program. This simple founding idea, when properly applied, give programmers a tool able to specify, test, debug, document programs, as well as a mechanism to construct a simple, safe and sane error handling mechanism. Nevertheless, although well adapted to object-oriented programming (and other popular techniques such as unit testing), DbC still has a very low practical acceptance and application. We believe that one of the main reasons for such is the lack of a proper support for it in many programming languages currently in use (such as Java). A complete support for DbC requires not only the ability to specify assertions; but also the necessity to distinguish different kinds of assertions, depending of what is being asserted; a proper integration in object-oriented programming; and, finally, a coherent connection with error handling mechanisms. It is in this last requirement that existing tools that extend Java with DbC mechanisms completely fail to properly, and coherently, integrate DbC within Java programming. The dominant practices for systematically handling failures in programming languages are not DbC based, using instead a defensive programming approach, either by using normal languages mechanisms (as in programming language C) or by the use of typed exceptions in try/catch based exception mechanisms. In this article, we will present and justify the requirements posed on programming languages for a complete support for DbC; On the context of the last presented requirement – error handling – defensive programming will be discussed and criticized; It will be showed that, unlike Eiffel's original DbC error handling, existing typed exceptions in try/catch based exception mechanisms are not well adapted to algorithmic abstraction provided by methods; Finally, a new DbC Java extension named Contract-Java will be presented and it will be showed that it is coherently integrated both with Java existing mechanisms and DbC. It will be presented an innovative Contract-Java extension to DbC that automatically generates debugging information for (non-rescued) contract failures, that we believe further enhances the DbC debugging capabilities.

Cite as

Miguel Oliveira e Silva and Pedro G. Francisco. Contract-Java: Design by Contract in Java with Safe Error Handling. In 3rd Symposium on Languages, Applications and Technologies. Open Access Series in Informatics (OASIcs), Volume 38, pp. 111-126, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)


Copy BibTex To Clipboard

@InProceedings{oliveiraesilva_et_al:OASIcs.SLATE.2014.111,
  author =	{Oliveira e Silva, Miguel and Francisco, Pedro G.},
  title =	{{Contract-Java: Design by Contract in Java with Safe Error Handling}},
  booktitle =	{3rd Symposium on Languages, Applications and Technologies},
  pages =	{111--126},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-68-2},
  ISSN =	{2190-6807},
  year =	{2014},
  volume =	{38},
  editor =	{Pereira, Maria Jo\~{a}o Varanda and Leal, Jos\'{e} Paulo and Sim\~{o}es, Alberto},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.SLATE.2014.111},
  URN =		{urn:nbn:de:0030-drops-45641},
  doi =		{10.4230/OASIcs.SLATE.2014.111},
  annote =	{Keywords: design by contract, defensive programming, exceptions, Java, contract-Java}
}
Document
Towards Testing Concurrent Objects in CLP

Authors: Elvira Albert, Puri Arenas, and Miguel Gómez-Zamalloa

Published in: LIPIcs, Volume 17, Technical Communications of the 28th International Conference on Logic Programming (ICLP'12) (2012)


Abstract
Testing is a vital part of the software development process. It is even more so in the context of concurrent languages, since due to undesired task interleavings and to unexpected behaviours of the underlying task scheduler, errors can go easily undetected. This paper studies the extension of the CLP-based framework for glass-box test data generation of sequential programs to the context of concurrent objects, a concurrency model which constitutes a promising solution to concurrency in OO languages. Our framework combines standard termination and coverage criteria used for testing sequential programs with specific criteria which control termination and coverage from the concurrency point of view, e.g., we can limit the number of task interleavings allowed and the number of loop unrollings performed in each parallel component, etc.

Cite as

Elvira Albert, Puri Arenas, and Miguel Gómez-Zamalloa. Towards Testing Concurrent Objects in CLP. In Technical Communications of the 28th International Conference on Logic Programming (ICLP'12). Leibniz International Proceedings in Informatics (LIPIcs), Volume 17, pp. 98-108, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)


Copy BibTex To Clipboard

@InProceedings{albert_et_al:LIPIcs.ICLP.2012.98,
  author =	{Albert, Elvira and Arenas, Puri and G\'{o}mez-Zamalloa, Miguel},
  title =	{{Towards Testing Concurrent Objects in CLP}},
  booktitle =	{Technical Communications of the 28th International Conference on Logic Programming (ICLP'12)},
  pages =	{98--108},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-43-9},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{17},
  editor =	{Dovier, Agostino and Santos Costa, V{\'\i}tor},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICLP.2012.98},
  URN =		{urn:nbn:de:0030-drops-36134},
  doi =		{10.4230/LIPIcs.ICLP.2012.98},
  annote =	{Keywords: Testing, Glass-box Test Data Generation, Active Objects, Symbolic Execution}
}
Document
Ontology Access Provisioning in Grid Environments

Authors: Miguel Esteban Gutiérrez and Asuncion Gomez-Perez

Published in: Dagstuhl Seminar Proceedings, Volume 5271, Semantic Grid: The Convergence of Technologies (2005)


Abstract
The increase of use of semantic technologies has reached almost every computer science related field, including the grid computing field . The next generation Grid should virtualise the notion of distribution in computation, storage, and communication over unlimited resources with well defined computational semantics. A Grid node may provide new services, functions or even new concepts that are unknown to clients. The semantics of such services are defined by means of Ontologies [Gruber, 1993; Gómez-Pérez et al., 2003]. Thus providing the appropriate means for accessing and using Ontologies in the Grid is fundamental if semantic technologies are to be used. So, the transition from monolithic, centralized ontology services to a virtual organization of Grid compliant and Grid aware ontology services that can coordinate and cooperate with each other is crucial to progress towards the Semantic Grid [De Roure et al., 2005].

Cite as

Miguel Esteban Gutiérrez and Asuncion Gomez-Perez. Ontology Access Provisioning in Grid Environments. In Semantic Grid: The Convergence of Technologies. Dagstuhl Seminar Proceedings, Volume 5271, p. 1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)


Copy BibTex To Clipboard

@InProceedings{gutierrez_et_al:DagSemProc.05271.9,
  author =	{Guti\'{e}rrez, Miguel Esteban and Gomez-Perez, Asuncion},
  title =	{{Ontology Access Provisioning in Grid Environments}},
  booktitle =	{Semantic Grid: The Convergence of Technologies},
  pages =	{1--1},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{5271},
  editor =	{Carole Goble and Carl Kesselman and York Sure},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.05271.9},
  URN =		{urn:nbn:de:0030-drops-3832},
  doi =		{10.4230/DagSemProc.05271.9},
  annote =	{Keywords: Ontology Access, WS-DAIO}
}
  • Refine by Author
  • 1 Albert, Elvira
  • 1 Arenas, Puri
  • 1 Bispo, João
  • 1 Bosch-Calvo, Miguel
  • 1 Francisco, Pedro G.
  • Show More...

  • Refine by Classification
  • 1 Software and its engineering → Compilers
  • 1 Software and its engineering → Development frameworks and environments
  • 1 Software and its engineering → Software maintenance tools
  • 1 Software and its engineering → Source code generation
  • 1 Theory of computation → Routing and network design problems

  • Refine by Keyword
  • 1 Active Objects
  • 1 Algorithm
  • 1 Approximation
  • 1 C/C++
  • 1 Glass-box Test Data Generation
  • Show More...

  • Refine by Type
  • 5 document

  • Refine by Publication Year
  • 2 2023
  • 1 2005
  • 1 2012
  • 1 2014

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