-
Denis Bechet,
Alexandre Dikovsky,
and Annie Foret.
Dependency Structure Grammars.
In Proceedings of the LACL 2005 Conference : Logical Aspects of Computational Linguistics, LNCS(LNAI) 3492,
pages 18-34,
2005.
springer.
[PDF]
Abstract: |
In this paper, we define Dependency Structure Grammars (DSG), which are rewriting rule grammars generating sentences together with their dependency structures, are more expressive than CF-grammars and non-equivalent to mildly context-sensitive grammars. We show that DSG are weakly equivalent to Categorial Dependency Grammars (CDG) recently introduced in [6,3]. In particular, these dependency grammars naturally express long distance dependencies and enjoy good mathematical properties. |
@InProceedings{Foret05b,
author = {Denis Bechet and Alexandre Dikovsky and Annie Foret},
title = {Dependency Structure Grammars},
booktitle = {Proceedings of the LACL 2005 Conference : Logical Aspects of Computational Linguistics, LNCS(LNAI) 3492},
year = 2005,
publisher = {springer},
pages = {18--34},
pdf= {http://www.springerlink.com/content/yda6x9u1t99y3198/ },
abstract={ In this paper, we define Dependency Structure Grammars (DSG), which are rewriting rule grammars generating sentences together with their dependency structures, are more expressive than CF-grammars and non-equivalent to mildly context-sensitive grammars. We show that DSG are weakly equivalent to Categorial Dependency Grammars (CDG) recently introduced in [6,3]. In particular, these dependency grammars naturally express long distance dependencies and enjoy good mathematical properties. }
}
-
Denis Bechet and Annie Foret.
On Rigid NL Lambek Grammars Inference from Generalized Functor-Argument Data.
In FGMOL'05, the tenth conference on Formal Grammar and the ninnth on the Mathematics of Language,
Edinburgh, Scotland,
2005.
Keyword(s): grammatical inference,
categorial grammars,
non- associative Lambek calculus,
learning from positive examples,
model of Gold.
Abstract: |
This paper is concerned with the inference of categorial grammars, a context-free grammar formalism in the field of computational linguistics. A recent result has shown that whereas they are not learnable from strings in the model of Gold, rigid and k-valued non-asso ciative Lamb ek grammars are still learnable from generalized functor-argument structured sentences. We fo cus here on the algorithmic part of this result and provide an algo- rithm that can b e seen as an extension of Buszkowski, Penn and Kanazawa's contributions for classical categorial grammars. |
@inproceedings{For05c,
author = {Denis Bechet and Annie Foret},
title = {On Rigid {NL Lambek} Grammars Inference from Generalized Functor-Argument Data},
booktitle = {FGMOL'05, the tenth conference on Formal Grammar and the ninnth on the Mathematics of Language},
year = 2005,
address = {Edinburgh, Scotland},
Abstract = { This paper is concerned with the inference of categorial grammars, a context-free grammar formalism in the field of computational linguistics. A recent result has shown that whereas they are not learnable from strings in the model of Gold, rigid and k-valued non-asso ciative Lamb ek grammars are still learnable from generalized functor-argument structured sentences. We fo cus here on the algorithmic part of this result and provide an algo- rithm that can b e seen as an extension of Buszkowski, Penn and Kanazawa's contributions for classical categorial grammars. },
Keywords={ grammatical inference, categorial grammars, non- associative Lambek calculus, learning from positive examples, model of Gold},
}
-
Denis Bechet and Annie Foret.
k-Valued Non-Associative Lambek Grammars (without Product) Form a Strict Hierarchy of Languages.
In Proceedings of the LACL 2005 Conference: Logical Aspects of Computational Linguistics, LNCS(LNAI) 3492,
pages 1-17,
2005.
springer.
[PDF]
Abstract: |
The notion of k-valued categorial grammars where a word is associated to at most k types is often used in the field of lexicalized grammars as a fruitful constraint for obtaining several properties like the existence of learning algorithms. This principle is relevant only when the classes of k-valued grammars correspond to a real hierarchy of languages. This paper establishes the relevance of this notion for two related grammatical systems. In the first part, the classes of k-valued non-associative Lambek (NL) grammars without product is proved to define a strict hierarchy of languages. The second part introduces the notion of generalized functor argument for non-associative Lambek ($NL_{\emptyset}$) calculus without product but allowing empty antecedent and establishes also that the classes of k-valued ($NL_{\emptyset}$) grammars without product form a strict hierarchy of languages |
@InProceedings{Foret05a,
author = {Denis Bechet and Annie Foret},
title = { k-Valued Non-Associative {L}ambek Grammars (without Product) Form a Strict Hierarchy of Languages},
booktitle = {Proceedings of the LACL 2005 Conference: Logical Aspects of Computational Linguistics, LNCS(LNAI) 3492},
year = 2005,
publisher= {springer},
pages = {1--17},
pdf= {http://www.springerlink.com/content/k4cy3ynkmmd56hct/ },
Abstract = { The notion of k-valued categorial grammars where a word is associated to at most k types is often used in the field of lexicalized grammars as a fruitful constraint for obtaining several properties like the existence of learning algorithms. This principle is relevant only when the classes of k-valued grammars correspond to a real hierarchy of languages. This paper establishes the relevance of this notion for two related grammatical systems. In the first part, the classes of k-valued non-associative Lambek (NL) grammars without product is proved to define a strict hierarchy of languages. The second part introduces the notion of generalized functor argument for non-associative Lambek ($NL_{\emptyset}$) calculus without product but allowing empty antecedent and establishes also that the classes of k-valued ($NL_{\emptyset}$) grammars without product form a strict hierarchy of languages }
}
-
T. Denmat,
M. Ducassé,
and O. Ridoux.
Data mining and cross-checking of execution traces. A re-interpretation of Jones, Harrold and Stasko test information visualization.
In T. Ellman and A. Zisman, editors,
Proceedings of the 20th IEEE/ACM International Conference on Automated Software Engineering,
November 2005.
ACM Press.
Note: See RR-5661 for a long version of this article.
Keyword(s): Software Engineering,
Debugging,
Artificial Intelligence,
Learning,
Knowledge acquisition.
Abstract: |
The current trend in debugging and testing is to cross-check information collected during several executions. Jones et al., for example, propose to use the instruction coverage of passing and failing runs in order to visualize suspicious statements. This seems promising but lacks a formal justification. In this paper, we show that the method of Jones et al. can be re-interpreted as a data mining procedure. More particularly, they define an indicator which characterizes association rules between data. With this formal framework we are able to explain intrinsic limitations of the above indicator. |
@InProceedings{denmat05b,
Author={T. Denmat and M. Ducassé and O. Ridoux},
Title={Data mining and cross-checking of execution traces. A re-interpretation of {Jones, Harrold and Stasko} test information visualization},
Pages={ },
BookTitle={Proceedings of the 20th IEEE/ACM International Conference on Automated Software Engineering},
Year={2005},
Editor={T. Ellman and A. Zisman},
Publisher={ACM Press},
Month={November},
Note={See RR-5661 for a long version of this article},
Keywords={Software Engineering, Debugging, Artificial Intelligence, Learning, Knowledge acquisition},
Abstract={The current trend in debugging and testing is to cross-check information collected during several executions. Jones et al., for example, propose to use the instruction coverage of passing and failing runs in order to visualize suspicious statements. This seems promising but lacks a formal justification. In this paper, we show that the method of Jones et al. can be re-interpreted as a data mining procedure. More particularly, they define an indicator which characterizes association rules between data. With this formal framework we are able to explain intrinsic limitations of the above indicator.}
}
-
T. Denmat,
A. Gotlieb,
and Mireille Ducassé.
Proving or Disproving Likely Invariants with Constraint Reasoning.
In A. Serebrenik, editor,
Proceedings of the 15th Workshop on Logic-based Method for Programming Environments,
Sitges, SPAIN,
October 2005.
Note: Satelite event of International Conference on Logic Programming (ICLP'2005). Published in Computer Research Repository cs.SE/0508108.
[WWW]
Keyword(s): Software Engineering,
Testing and Debugging,
Program verification,
Constraint and logic languages.
Abstract: |
A program invariant is a property that holds for every execution of the program. Recent work suggest to infer likely-only invariants, via dynamic analysis. A likely invariant is a property that holds for some executions but is not guaranteed to hold for all executions. In this paper, we present work in progress addressing the challenging problem of automatically verifying that likely invariants are actual invariants. We propose a constraint-based reasoning approach that is able, unlike other approaches, to both prove or disprove likely invariants. In the latter case, our approach provides counter-examples. We illustrate the approach on a motivating example where automatically generated likely invariants are verified. |
@InProceedings{DGD05,
Author={T. Denmat and A. Gotlieb and Mireille Ducassé},
Title={Proving or Disproving Likely Invariants with Constraint Reasoning},
BookTitle={Proceedings of the 15th Workshop on Logic-based Method for Programming Environments},
Address = {Sitges, SPAIN},
Year={2005},
Editor={A. Serebrenik},
Month={October},
Note={Satelite event of International Conference on Logic Programming (ICLP'2005). Published in Computer Research Repository cs.SE/0508108},
url={http://arxiv.org/abs/cs.pl/0508108},
keywords={Software Engineering, Testing and Debugging, Program verification, Constraint and logic languages},
Abstract={A program invariant is a property that holds for every execution of the program. Recent work suggest to infer likely-only invariants, via dynamic analysis. A likely invariant is a property that holds for some executions but is not guaranteed to hold for all executions. In this paper, we present work in progress addressing the challenging problem of automatically verifying that likely invariants are actual invariants. We propose a constraint-based reasoning approach that is able, unlike other approaches, to both prove or disprove likely invariants. In the latter case, our approach provides counter-examples. We illustrate the approach on a motivating example where automatically generated likely invariants are verified. }
}
-
Sébastien Ferré,
Olivier Ridoux,
and Benjamin Sigonneau.
Arbitrary Relations in Formal Concept Analysis and Logical Information Systems.
In ICCS,
LNCS 3596,
pages 166-180,
2005.
Springer.
Keyword(s): logical concept analysis,
relation,
logical information system,
navigation.
Abstract: |
A logical view of formal concept analysis considers attributes of a formal context as unary predicates. In a first part, we propose an augmented definition that handles {\em binary relations} between objects. A Galois connection is defined on augmented contexts. It represents concept inheritance as usual, but also relations between concepts. As usual, labeling operators are also defined. In particular, concepts and relations are visible and labeled in a single structure. In a second part, we show how relations can be used for navigating in an augmented concept lattice. This part augments the theory of Logical Information Systems. An implementation is sketched, and first experimental results are presented. |
@InProceedings{FerRidSig2005,
author = {Sébastien Ferré and Olivier Ridoux and Benjamin Sigonneau},
title = {Arbitrary Relations in Formal Concept Analysis and Logical Information Systems},
booktitle = {ICCS},
year = {2005},
pages = {166-180},
publisher = {Springer},
series = {LNCS 3596},
keywords = {logical concept analysis, relation, logical information system, navigation},
abstract = {A logical view of formal concept analysis considers attributes of a formal context as unary predicates. In a first part, we propose an augmented definition that handles {\em binary relations} between objects. A Galois connection is defined on augmented contexts. It represents concept inheritance as usual, but also relations between concepts. As usual, labeling operators are also defined. In particular, concepts and relations are visible and labeled in a single structure. In a second part, we show how relations can be used for navigating in an augmented concept lattice. This part augments the theory of Logical Information Systems. An implementation is sketched, and first experimental results are presented.},
}
-
L. Langevine and M. Ducassé.
A Tracer Driver for Hybrid Execution Analyses.
In Proceedings of the 6th Automated Debugging Symposium,
September 2005.
ACM Press.
Note: See RR-5611 for a longer version of this article.
[WWW]
Keyword(s): Software Engineering,
Debugging,
Monitors,
Tracing,
Programming Environments.
Abstract: |
Tracers provide users with useful information about program executions. In this paper we propose a ``tracer driver'', from a single tracer, it provides a powerful front-end for multiple dynamic analysis tools while limiting the overhead of the trace generation. The tracer driver can be used both synchronously and asynchronously. The relevant execution events are specified by flexible event patterns and a large variety of trace data can be given either systematically or ``on demand''. The proposed tracer driver has been designed and experimented in the context of constraint logic programming, within GNU-Prolog. Its principles are, however, independent of the traced programming language. Experimental measures show that the flexibility and power of the described architecture are also the basis of reasonable performances. |
@InProceedings{langevine05,
Author={L. Langevine and M. Ducassé},
Title={A Tracer Driver for Hybrid Execution Analyses},
BookTitle={Proceedings of the 6th Automated Debugging Symposium},
Year={2005},
Publisher={ACM Press},
url={http://doi.acm.org/10.1145/1085130.1085149},
Month={September},
Note= {see RR-5611 for a longer version of this article},
keywords={Software Engineering, Debugging, Monitors, Tracing, Programming Environments},
Abstract={Tracers provide users with useful information about program executions. In this paper we propose a ``tracer driver'', from a single tracer, it provides a powerful front-end for multiple dynamic analysis tools while limiting the overhead of the trace generation. The tracer driver can be used both synchronously and asynchronously. The relevant execution events are specified by flexible event patterns and a large variety of trace data can be given either systematically or ``on demand''. The proposed tracer driver has been designed and experimented in the context of constraint logic programming, within GNU-Prolog. Its principles are, however, independent of the traced programming language. Experimental measures show that the flexibility and power of the described architecture are also the basis of reasonable performances. }
}
-
L. Langevine and M. Ducassé.
A Tracer Driver for Versatile Dynamic Analyses of Constraint Logic Programs.
In A. Serebrenik, editor,
Proceedings of the 15th Workshop on Logic-based Method for Programming Environments,
Sitges, SPAIN,
October 2005.
Note: Satelite event of International Conference on Logic Programming (ICLP'2005). Published in Computer Research Repository cs.SE/0508105.
[WWW]
Keyword(s): Software Engineering,
Debugging,
Monitors,
Tracing,
Programming Environments.
Abstract: |
Programs with constraints are hard to debug. In this paper, we describe a general architecture to help develop new debugging tools for constraint programming. The possible tools are fed by a single general-purpose tracer. A tracer-driver is used to adapt the actual content of the trace, according to the needs of the tool. This enables the tools and the tracer to communicate in a client-server scheme. Each tool describes its needs of execution data thanks to event patterns. The tracer driver scrutinizes the execution according to these event patterns and sends only the data that are relevant to the connected tools. Experimental measures show that this approach leads to good performance in the context of constraint logic programming, where a large variety of tools exists and the trace is potentially huge. |
@InProceedings{langevine05b,
Author={L. Langevine and M. Ducassé},
Title={A Tracer Driver for Versatile Dynamic Analyses of Constraint Logic Programs},
BookTitle={Proceedings of the 15th Workshop on Logic-based Method for Programming Environments},
Address = {Sitges, SPAIN},
Year={2005},
Editor={A. Serebrenik},
Month={October},
Note={Satelite event of International Conference on Logic Programming (ICLP'2005). Published in Computer Research Repository cs.SE/0508105},
url={http://arxiv.org/abs/cs.pl/0508105},
keywords={Software Engineering, Debugging, Monitors, Tracing, Programming Environments},
abstract={Programs with constraints are hard to debug. In this paper, we describe a general architecture to help develop new debugging tools for constraint programming. The possible tools are fed by a single general-purpose tracer. A tracer-driver is used to adapt the actual content of the trace, according to the needs of the tool. This enables the tools and the tracer to communicate in a client-server scheme. Each tool describes its needs of execution data thanks to event patterns. The tracer driver scrutinizes the execution according to these event patterns and sends only the data that are relevant to the connected tools. Experimental measures show that this approach leads to good performance in the context of constraint logic programming, where a large variety of tools exists and the trace is potentially huge. }
}
-
Yoann Padioleau and Olivier Ridoux.
A Parts-of-File File System.
In USENIX Annual Technical Conference, General Track (Short Paper),
2005.
[WWW]
Abstract: |
The Parts-of-file File System (PofFS) allows read-write accesses to different views of a given file or set of files in order to help the user separate and manipulate different concerns. The set of files is considered as a mount point from which views can be selected as read-write files via directories. Paths are formulas mentioning properties of a desired view. Each directory contain a file (the view) which contains the parts of the mounted files that satisfy the properties. This service is offered generically at the file system level, and a plug-in interface permits that file formats, or application-specific details are handled by user-defined operators. Special plug-ins called transducers can be defined for automatically attaching properties to parts of files. Performances are encouraging; files of 100 000 lines are handled efficiently. |
@inproceedings{padioleau05,
author = {Yoann Padioleau and Olivier Ridoux},
title = {A Parts-of-File File System},
booktitle = {USENIX Annual Technical Conference, General Track (Short Paper)},
year = {2005},
url = {http://www.usenix.org/events/usenix05/tech/general/padioleau.html},
abstract = { The Parts-of-file File System (PofFS) allows read-write accesses to different views of a given file or set of files in order to help the user separate and manipulate different concerns. The set of files is considered as a mount point from which views can be selected as read-write files via directories. Paths are formulas mentioning properties of a desired view. Each directory contain a file (the view) which contains the parts of the mounted files that satisfy the properties. This service is offered generically at the file system level, and a plug-in interface permits that file formats, or application-specific details are handled by user-defined operators. Special plug-ins called transducers can be defined for automatically attaching properties to parts of files. Performances are encouraging; files of 100 000 lines are handled efficiently.},
}
-
Yoann Padioleau,
Benjamin Sigonneau,
Olivier Ridoux,
and Sébastien Ferré.
LISFS: a Logical Information System as a File System.
In Véronique Benzaken, editor,
Bases de données avancées,
pages 393-398,
October 2005.
Université de Rennes 1.
[WWW]
[PDF]
Abstract: |
We present Logical Information Systems (LIS). A LIS can be viewed as a schema-less database whose objects are described by logical formulas. Objects are automatically organized according to their logical description, and logical formulas can be used for representing both queries and navigation links. The key feature of a LIS is that it answers a query with a set of navigation links expressed in the same logic as the query. As navigation links are dynamically computed from any query, and can be used as query increments, it follows that querying and navigation steps can be combined in any order. We then present LISFS, a file-system implementation of a LIS, where objects are files or parts of files. This has the benefit to make LIS features available right now to existing applications. This implementation can easily be extended and specialized through a plug-in mechanism. Finally, we present some applications in the field of personal databases (e.g., music, images, emails), and demonstrate that building specialized interfaces for visualizing databases can be done easily through LISFS navigation. |
@InProceedings{lisfs-bda05,
author = {Padioleau, Yoann and Sigonneau, Benjamin and Ridoux, Olivier and Ferré, Sébastien},
title = {LISFS: a Logical Information System as a File System},
booktitle = {Bases de données avancées},
pages = {393--398},
year = {2005},
editor = {Benzaken, Véronique},
month = oct,
publisher = {Université de Rennes 1},
url = {http://bda05.irisa.fr/},
pdf = {http://www.irisa.fr/lande/sigonneau/publications/articles/bda2005.pdf},
abstract = "We present Logical Information Systems (LIS). A LIS can be viewed as a schema-less database whose objects are described by logical formulas. Objects are automatically organized according to their logical description, and logical formulas can be used for representing both queries and navigation links. The key feature of a LIS is that it answers a query with a set of navigation links expressed in the same logic as the query. As navigation links are dynamically computed from any query, and can be used as query increments, it follows that querying and navigation steps can be combined in any order. We then present LISFS, a file-system implementation of a LIS, where objects are files or parts of files. This has the benefit to make LIS features available right now to existing applications. This implementation can easily be extended and specialized through a plug-in mechanism. Finally, we present some applications in the field of personal databases (e.g., music, images, emails), and demonstrate that building specialized interfaces for visualizing databases can be done easily through LISFS navigation. "
}