"Advanced Programming Systems" is a newly created group, with researchers from the former groups NCC-DP Declarative Programming and NCC-F Foundations of Computer Science. The aim is to develop advanced systems that put fundamental research to practical use.

In the period 2003-2006, the main research objectives pursued by team members were:

- to design and implement a highly efficient deductive database system that couples the OPTYap logic system and the MySQL database management system.

- to address source-level transformations based on program analysis and partial-evaluation; implement advanced and

low-level coupling strategies; and evaluate performance using real size applications, with particular emphasis on relational inductive logic programming problems.

- to develop a new framework for XML processing based on an highly declarative model which explores the relation between terms in the logic programming paradigm and XML documents. Identify real world applications and scenarios where this framework can be used successfully and extend it with an Application Programming Interface.

- to investigate hidden tractable sub-structures of constraint and optimization problems with impact to model formulation and problem solving.

- to design new algorithmic, dynamic model reformulation and search techniques for finding exact or approximate solutions with main focus on visibility, surveillance, configuration, automated deduction, validation, and matching problems.

- to develop a web application to assist mathematics education, that may generate and solve drills automatically, based on constrained grammars and techniques from symbolic computation and automated reasoning.

- to investigate the application of type-based analysis for inferring size- and cost-equations for recursive, higher-order and polymorphic functional programs without requiring user annotations or unusual syntax.

-------------------

By team members (or in collaboration with members of former groups NCC-DP and NCC-F:

-------------------

Design of new algorithms for matching problems with priorities, preferences and tenants. Research was triggered by flaws detected in the Portuguese hiring law for state-school teachers. Results sent to the Government were taken in a new law.

MYDDAS, a [M]ySQL/[Y]ap [D]eductive [DA]tabase System that proposed and implemented several novel and state-of-the-art

solutions for the efficient coupling of a relational database system with a logic programming system.

XCentric, an XML processing framework based on the unification of flexible arity terms. A highly declarative model,

allowing focusing on the relevant parts of the documents. It implements a DTDs-based type system,

useful for validation and compact query representation. General-purpose XML processing and querying is enhanced.

VeriFLog, a tool that uses the highly declarative model of XCentric applied to verification and automatic correction of content

in large websites. Websites for collaborative work become more popular each day, but are also inherently vulnerable to vandalism and inclusion of inaccurate content. VeriFlog allows the definition of constraints by writing rules in a highly declarative syntax given by XCentric. The rules are automatically checked when new content is added or modified and errors can be automatically corrected.

Agilmat, a web application for mathematics education, modular and extensible, customizable, integrating distinct technologies and symbolic computation.

An anytime method for solving minimum vertex guard problems on polygons and attacking open conjectures on vertex

floodlight problems. (with CEOC-UI/UA)

Construction techniques for orthogonal polygons with relevance to sampling and backtrack-free enumeration of polyominoes with a known number of vertices, and as proof-techniques for combinatorial results.

Approaching of Relational Inductive Logic Programming through a deductive database framework, where an automatic compilation of extensional logic goals into aggregation SQL queries achieved results comparable to in-memory evaluation while greatly improving scalability.

------------------

IF = ISI impact factor

nC = Google Scholar citations by others, not repeated

------------------

Evelyne Contejean, Claude Marché, Ana Paula Tomás and Xavier Urbain, Mechanically proving termination using polynomial interpretations. In Journal of Automated Reasoning, 34:4 (May 2005), 325-363, Springer-Verlag. IF=0.608, nC=7

Jorge Coelho and Mário Florido, CLP(Flex): Constraint Logic Programming Applied to XML Processing. Proceedings of the 3rd International Conference on Ontologies, DataBases, and Applications of Semantics for Large Scale Information Systems (ODBASE 2004), Lecture Notes in Computer Science 3291, Springer-Verlag, 2004. IF=0.402, nC=5

Ana Paula Tomás, António Leslie Bajuelos, Quadratic-Time Linear-Space Algorithms for Generating Orthogonal Polygons with a Given Number of Vertices. In A. Laganà et al. (eds.), Computational Science and Its Applications (CGA'04 at ICCSA 2004), Lecture Notes in Computer Science 3045, 117-126, Springer-Verlag, 2004. IF=0.402, nC=0

Ana Paula Tomás, António Leslie Bajuelos, Fábio Marques, Partitioning Orthogonal Polygons by Extension of All Edges Incident to Reflex Vertices: lower and upper bounds on the number of pieces. In A. Laganà et al. (eds.), Computational Science and Its Applications (CGA'04 at ICCSA 2004), Lecture Notes in Computer Science 3045, 127-136, Springer-Verlag, 2004. IF=0.402, nC=0

Ana Paula Tomás and António Leslie Bajuelos, Generating Random Orthogonal Polygons. In R.Conejo, M.Urretavizcaya, J.-L. Pérez-de-la-Cruz (Eds), Current Topics in Artificial Intelligence: 10th Conf. of the Spanish Association for Artificial Intelligence, CAEPIA 2003, and 5th Conference on Technology Transfer, TTIA 2003. Revised Selected Papers, Lecture Notes in Computer Science 3040, 364-373, Springer-Verlag, 2004. IF=0.402, nC=0

Jorge Coelho and Mário Florido,Type-based XML Processing in Logic Programming. In V. Dahl, P. Wadler (eds.), Proceedings of the Fifth International Symposium on Practical Aspects of Declarative Languages (PADL'2003), Lecture Notes in Computer Science 2562, 273-285, Springer-Verlag, 2003. IF=0.402, nC=11

Michel Ferreira and Luís Damas, WAM Local Analysis. In V. Dahl, P. Wadler (eds.), Proceedings of the Fifth International Symposium on Practical Aspects of Declarative Languages (PADL'2003), Lecture Notes in Computer Science 2562, 286-303, Springer-Verlag, 2003. IF=0.402, nC=2

Ana Paula Tomás, António Leslie Bajuelos, Fábio Marques, Approximation Algorithms to Minimum Vertex Cover Problems on Polygons and Terrains. In P.M.A Sloot et al. (eds.), Proceedings of the International Conference on Computational Science (ICCS 2003), Lecture Notes in Computer Science 2657, 869-878, Springer-Verlag, 2003. IF=0.402, nC=1

Ana Paula Tomás, José Paulo Leal, A CLP-Based Tool for Computer Aided Generation and Solving of Maths Exercises. In V. Dahl, P. Wadler (eds.), Proceedings of the Fifth International Symposium on Practical Aspects of Declarative Languages (PADL'2003), Lecture Notes in Computer Science 2562, 223-240, Springer-Verlag, 2003. IF=0.402, nC=0

Michel Ferreira, Nuno A. Fonseca, Ricardo Rocha, Tiago Soares. Efficient and Scalable Induction of Logic Programs using a Deductive Database System, 16th International Conference on Inductive Logic Programming (ILP'2006), Lecture Notes in Artificial Intelligence 4455, 184-198. Springer-Verlag, 2006.

Ana Paula Tomás. Weak Stable Matchings with Tenants and Ties. In Francisco Azevedo, Pedro Barahona, Francois Fages and Francesca Rossi (eds), CSCLP'2006 workshop notes, Proceedings of the 11th Annual ERCIM Workshop on Constraint Programming, Pag. vi + 256, 2006.

Tiago Soares, Ricardo Rocha and Michel Ferreira, Generic Cut Actions for External Prolog Predicates. In P. Van Hentenryck (Ed), 8th International Symposium on Practical Aspects of Declarative Languages (PADL'2006), Lectures Notes in Computer Science 3819, 16-30, Springer-Verlag, 2006.

Jorge Coelho and Mário Florido, VeriFlog: Constraint Logic Programming Applied to Verification of Website Content. In International Workshop in XML Research and Applications (XRA 2006), Lecture Notes in Computer Science 3842, 148-156, Springer-Verlag, 2006.

Ana Paula Tomás, António Leslie Bajuelos, Fábio Marques. On Visibility Problems in the Plane -- Solving Minimum Vertex Guard Problems by Successive Approximations. In Proceedings of International Symposium on Artificial Intelligence and Mathematics, AI & MATH 2006, Florida, USA. (http://anytime.cs.umass.edu/aimath06/proceedings.html)

* MSc

Tânia Magalhães, Uma linguagem gráfica de programação para scripting em bioinformática. 2006

Sabrina Vieira da Silva, Coupling Logic Programming With Relational Databases, 2005.

Sónia Alexandra Ferreira da Silva e Sousa, AGISA: an integrated system for classroom administration, 2005.

Fábio Marques. Minimizing the Number of Guards in Art Galleries by Successive Approximations. 2004

Prototypes:

AGILMAT: a web application for math education, 2003-2006.

AGISA: an integrated system for classroom administration, 2004.

April: an inductive logic programming system, 2002-2006.

CLP(Flex): a constraint logic programming language for terms with flexible arity, 2003-2004.

GPSMan versions 6.3 and 6.3.1: a graphical manager of GPS (Global Positioning System) data, 1998-2006.

MYDDAS: a deductive database system coupling YapTab and MySQL, 2005-2006.

OPTYap: a parallel logic programming system supporting or-parallelism and tabling, based on Yap Prolog, 2000-2006.

SimTraffic: a traffic micro-simulator using a continuous model, 2006.

Spatial-Yap: a spatio-deductive database system, 2006.

XCentric: a logic programming language specialized for XML-processing, 2006.

* Organizing Committees:

Colloquium on Implementation of Constraint and Logic Programming Systems 2003 (CICLOPS'03), Mumbai, India, December 2003; ca. approx. 25; Michel Ferreira (co-organizer)

* Programme Committees:

Sixth International Colloquium on Implementation of Constraint and Logic Programming Systems (CICLOPS'06), Seattle, WA, USA, August 2006; Michel Ferreira.

ICLP 2006 Doctoral Consortium. 22nd International Conf. on Logic Programming. Seattle, WA, USA, August 2006, Discussant and Mentor, Michel Ferreira.

- foreign links [JP=joint publ, JPGT=joint post-grad training]

LRI-Université de Paris-Sud, Prof. Evelyne Contejean, and Claude Marché [JP]

RISC-Research Institute for Symbolic Computation, Austria, Dr. Temur Kutsia

Universidad Politécnica de Madrid, Prof. Manuel Abellanas Oar, Prof. Gregório Hernandez

University of New Mexico, Albuquerque, Prof. Manuel Hermenegildo, Deepak Kapur [JPGT]

University of St. Andrews, Prof. Kevin Hammond [JP,JPGT]

- research networks, bi-lateral actions

CRUP Spanish-Portuguese Action 77/06 "Algorithmic Problems in Illumination, Visibility and Surveillance". Universidade de Aveiro, Universidad Politécnica de Madrid, Universidade Católica Portuguesa, Universidad de Valladolid, Universidad de Alcalá

(01/2006-12/2007)

---

Relation to long term objectives denoted by

[SR] Software reliability

[SEC] Security

[RI] Reliable Information

[DDD] Distributed, decentralized, dynamic problems

---

- Spatial Data Processing [RI,DDD,SR,SEC]:

Design and implement a programming environment which offers a novel and state-of-the-art solution for the management of spatial data addressing spatial data modeling, spatial query languages and spatial data-mining. The system will combine three important technologies: object-relational databases, logic programming and inductive logic programming.

Approach challenging spatial applications through the logic-based spatial database. The area of intelligent transportation systems and vehicle-to-vehicle wireless communications is an interesting application field.

Extend a state-of-the-art traffic simulator developed at LIACC, which includes the micro-simulation of vehicles movement and the simulation of wireless telecommunications.

Address complex problems such as the design of collaborative navigation algorithms, vehicle-to-vehicle communication protocols and driving safety applications.

- Collaborative Knowledge Management Systems [RI]:

Develop a system which allows automatic integration and distribution of related data by applying concepts of unification of XML data. XML is the standard for data interchange. To organize collections of related documents and allow knowledge sharing it became urgent to have tools to manage related data now available in different XML formats.

- Embedded domain-specific language for memory testers [SR]:

Investigate the design of a higher level domain-specific language (DSL) for memory tests that would both facilitate development and reduce costs with ensuring correctness. Memory testing contributes to a large percentage of the final cost of memory circuits. Test programs are run on expensive, dedicated hardware and must be specified, developed and debugged prior to deployment. Recent contacts with industry indicate that there is interest for more robust tools for memory test development. The proposed methodology for specification and implementation is that of embedding the DSL compiler into a general-purpose functional language such as Haskell.

- Algorithms and constraints [RI,SR,DDD]:

Design models and solving techniques for multidisciplinary constraint problems emerging from the three other research goals, as routing problems in dynamic distributed and collaborative settings with real-time processing needs. Study constraint programming and geometric-based approaches for set cover and independent set problems with applications to spatial database systems.

Identify and exploit structural properties of Diophantine constraints systems with application to configuration problems,

XML documents validation, formal verification and automated reasoning, and compact representation of infinite or huge data

sets.

FCT:

19600 Plurianual 2007

42500 FCT Project MYDDAS 2007-2008

5480 "Porto Lazer, E.M", 2007-2009

+ salaries of team members, University of Porto and Polytechnic Institute of Porto 2007-2010

David Vaz, Michel Ferreira, Ricardo Lopes. Spatial-Yap: A Logic-based Geographic Information System. In V. Dahl and I. Niemela (Eds). Proceedings of the 23rd International Conference on Logic Programming (ICLP 2007). Lecture Notes in Computer Science 4670, 195-208, Springer-Verlag, 2007 (to appear)

Ana Paula Tomás. Weak Weak Stable Matchings with Tenants and Ties. In Francisco Azevedo, Pedro Barahona, Francois Fages and Francesca Rossi (eds), CSCLP'2006 workshop notes, Proceedings of the 11th Annual ERCIM Workshop on Constraint Programming, Pag. vi + 256, 2006.

Hugo Simoes, Kevin Hammond, Mário Florido and Pedro Vasconcelos. Using Intersection Types for Cost-analysis of Higher-Order Polymorphic Functional Programs. Proceedings of TYPES 2006, Lecture Notes in Computer Science, Springer-Verlag (to appear)

Michel Ferreira, Nuno A. Fonseca, Ricardo Rocha, Tiago Soares. Efficient and Scalable Induction of Logic Programs using a Deductive Database System. In 16th International Conference on Inductive Logic Programming (ILP'2006) . Lecture Notes in Artificial Intelligence 4455, 184-198, Springer-Verlag, 2006.

Jorge Coelho and Mário Florido. VeriFlog: Constraint Logic Programming Applied to Verification of Website Content. International Workshop in XML Research and Applications (XRA 2006), Lecture Notes in Computer Science 3842, 148-156, Springer-Verlag, 2006. 148-156

--- Scholarships for Post-Docs and post-grad (MSc and PhD) students.

--- Equipment:

The traffic simulation prototype is programmed to explore multi-threading in a high degree through the partitioning of maps in

disjoint geographic regions that can be independently simulated. In order to increase the simulation to larger regions and to higher number of vehicles, top-performance multi-core processors are needed, such as Intel's Core 2 Quad.

RAM is also an issue, as the simulation involves maintaining the local information of thousands of vehicles. In order to

be able to simulate in large scale intelligent transportation systems environments in a single machine (which greatly simplifies the wireless communication simulation layer over a distributed approach using several machines) , a 16G RAM computer is needed.

To validate the simulator, concrete experiments are planned, using off-the-shelf components, such as GPS receivers connected to laptops, which allow the car-to-car protocols to be tested in small-scale environments, typically requiring 6 bluetooth GPSs and laptop computers.