Search

Your search keyword '"Jacquemard, Florent"' showing total 14 results
Start Over Author "Jacquemard, Florent" Topic tree automaton

Refine your results

more »

more »

14 results on '"Jacquemard, Florent"'

2. Rewrite Closure and CF Hedge Automata

Author

Jacquemard, Florent, Rusinowitch, Michael, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Dediu, Adrian-Horia, editor, Martín-Vide, Carlos, editor, and Truthe, Bianca, editor

Published
2013
Full Text
View/download PDF

3. Controlled Term Rewriting

Author

Jacquemard, Florent, Kojima, Yoshiharu, Sakai, Masahiko, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Goebel, Randy, editor, Siekmann, Jörg, editor, Wahlster, Wolfgang, editor, Tinelli, Cesare, editor, and Sofronie-Stokkermans, Viorica, editor

Published
2011
Full Text
View/download PDF

4. Unique Normalization for Shallow TRS

Author

Godoy, Guillem, Jacquemard, Florent, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, and Treinen, Ralf, editor

Published
2009
Full Text
View/download PDF

5. Rigid Tree Automata

Author

Jacquemard, Florent, Klay, Francis, Vacher, Camille, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Dediu, Adrian Horia, editor, Ionescu, Armand Mihai, editor, and Martín-Vide, Carlos, editor

Published
2009
Full Text
View/download PDF

7. Closure of Hedge-Automata Languages by Hedge Rewriting

Author

Jacquemard, Florent, Rusinowitch, Michael, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, and Voronkov, Andrei, editor

Published
2008
Full Text
View/download PDF

9. Rigid Reachability

Author

Ganzinger, Harald, Jacquemard, Florent, Veanes, Margus, Goos, Gerhard, editor, Hartmanis, Juris, editor, van Leeuwen, Jan, editor, Hsiang, Jieh, editor, and Ohori, Atsushi, editor

Published
1998
Full Text
View/download PDF

13. Ground reducibility is EXPTIME-complete

Author

Hubert Comon, Florent Jacquemard, Laboratoire Spécification et Vérification [Cachan] (LSV), École normale supérieure - Cachan (ENS Cachan)-Centre National de la Recherche Scientifique (CNRS), Verification in databases (DAHU), École normale supérieure - Cachan (ENS Cachan)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Cachan (ENS Cachan)-Centre National de la Recherche Scientifique (CNRS)-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Constraints, automatic deduction and software properties proofs (PROTHEO), INRIA Lorraine, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS), INRIA, and Jacquemard, Florent

Subjects
Polynomial, [INFO.INFO-LO] Computer Science [cs]/Logic in Computer Science [cs.LO], TheoryofComputation_COMPUTATIONBYABSTRACTDEVICES, Computational complexity theory, 2-EXPTIME, Deterministic algorithm, [INFO.INFO-OH]Computer Science [cs]/Other [cs.OH], EXPTIME, 0102 computer and information sciences, 02 engineering and technology, computational complexity, 01 natural sciences, tree automata, Theoretical Computer Science, Combinatorics, Deterministic automaton, term rewriting, 0202 electrical engineering, electronic engineering, information engineering, Two-way deterministic finite automaton, Tree automaton, Mathematics, Discrete mathematics, Linear bounded automaton, ground reducbility, Pushdown automaton, [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO], 16. Peace & justice, Computer theorem-proving, Computer Science Applications, TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES, Computational Theory and Mathematics, 010201 computation theory & mathematics, 020201 artificial intelligence & image processing, Tree (set theory), inductive theorem proving, complexity, Alternating Turing machine, Computer Science::Formal Languages and Automata Theory, rewriting systems, Information Systems
Abstract

We prove that ground reducibility is EXPTIME-complete in the general case. EXPTIME-hardness is proved by encoding the computations of an alternating Turing machine whose space is polynomially bounded. It is more difficult to show that ground reducibility belongs to DEXPTIME. We associate first an automaton with disequality constraints A/sub R,t/ to a rewrite system R and a term t. This automaton is deterministic and accepts a term u if and only if t is not ground reducible by R. The number of states of A/sub R,t/ is O(2/sup /spl par/R/spl par//spl times//spl par/t/spl par//) and the size of the constraints are polynomial in the size of R,t. Then we prove some new pumping lemmas, using a total ordering on the computations of the automaton. Thanks to these lemmas, we can give an upper bound to the number of distinct subtrees of a minimal successful computation of an automaton with disequality constraints. It follows that emptiness of such an automaton can be decided in time polynomial in the number of its states and exponential in the size of its constraints. Altogether, we get a simply exponential deterministic algorithm for ground reducibility.

Published
2003
Full Text
View/download PDF

14. Rewrite Closure and CF Hedge Automata

Author

Florent Jacquemard, Michaël Rusinowitch, Synchronous Realtime Processing and Programming of Music Signals (MuTant), Institut de Recherche et Coordination Acoustique/Musique (IRCAM)-Inria Paris-Rocquencourt, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS), Sciences et Technologies de la Musique et du Son (STMS), Institut de Recherche et Coordination Acoustique/Musique (IRCAM)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS), Combination of approaches to the security of infinite states systems (CASSIS), Franche-Comté Électronique Mécanique, Thermique et Optique - Sciences et Technologies (UMR 6174) (FEMTO-ST), Université de Technologie de Belfort-Montbeliard (UTBM)-Ecole Nationale Supérieure de Mécanique et des Microtechniques (ENSMM)-Centre National de la Recherche Scientifique (CNRS)-Université de Franche-Comté (UFC), Université Bourgogne Franche-Comté [COMUE] (UBFC)-Université Bourgogne Franche-Comté [COMUE] (UBFC)-Université de Technologie de Belfort-Montbeliard (UTBM)-Ecole Nationale Supérieure de Mécanique et des Microtechniques (ENSMM)-Centre National de la Recherche Scientifique (CNRS)-Université de Franche-Comté (UFC), Université Bourgogne Franche-Comté [COMUE] (UBFC)-Université Bourgogne Franche-Comté [COMUE] (UBFC)-Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Formal Methods (LORIA - FM), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Université de Technologie de Belfort-Montbeliard (UTBM)-Ecole Nationale Supérieure de Mécanique et des Microtechniques (ENSMM)-Université de Franche-Comté (UFC), Université Bourgogne Franche-Comté [COMUE] (UBFC)-Université Bourgogne Franche-Comté [COMUE] (UBFC)-Centre National de la Recherche Scientifique (CNRS)-Université de Technologie de Belfort-Montbeliard (UTBM)-Ecole Nationale Supérieure de Mécanique et des Microtechniques (ENSMM)-Université de Franche-Comté (UFC), Université Bourgogne Franche-Comté [COMUE] (UBFC)-Université Bourgogne Franche-Comté [COMUE] (UBFC)-Centre National de la Recherche Scientifique (CNRS)-Inria Nancy - Grand Est, Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL), Jacquemard, Florent, Inria Paris-Rocquencourt, and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Institut de Recherche et Coordination Acoustique/Musique (IRCAM)-Centre National de la Recherche Scientifique (CNRS)

Subjects
FOS: Computer and information sciences, Computer Science - Logic in Computer Science, Theoretical computer science, Nested word, [INFO.INFO-LO] Computer Science [cs]/Logic in Computer Science [cs.LO], Rewrite closure, Formal Languages and Automata Theory (cs.FL), Computer science, XQuery Update Facility, Computer Science - Formal Languages and Automata Theory, 0102 computer and information sciences, 02 engineering and technology, computer.software_genre, 01 natural sciences, Tree automata, XML processing, [INFO.INFO-FL]Computer Science [cs]/Formal Languages and Automata Theory [cs.FL], Regular language, Computer Science - Databases, Hedge automata, Computer Science::Logic in Computer Science, 0202 electrical engineering, electronic engineering, information engineering, Static typechecking, Tree automaton, Context-free tree languages, Access Control Policies Verification, [INFO.INFO-DB]Computer Science [cs]/Databases [cs.DB], Programming language, [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO], Databases (cs.DB), 020207 software engineering, Hedge (linguistics), Logic in Computer Science (cs.LO), TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES, Closure (mathematics), 010201 computation theory & mathematics, TheoryofComputation_LOGICSANDMEANINGSOFPROGRAMS, Computer Science::Programming Languages, Tree (set theory), Rewriting, computer, Computer Science::Formal Languages and Automata Theory
Abstract

We introduce an extension of hedge automata called bidimensional context-free hedge automata, proposing a new uniform representation of vertical and horizontal computation steps in unranked ordered trees. The class recognized languages is shown to be preserved by rewrite closure with inverse-monadic rules. We also extend the parameterized rewriting rules used for modeling the W3C XQuery Update Facility in previous works, by the possibility to insert a new parent node above a given node. We show that the rewrite closure of hedge automata languages with these extended rewriting systems are context-free hedge languages.

Published
2012

Catalog

Books, media, physical & digital resources
See catalog results