• Refine your search:
  • 
    Keyword:
    
    • ACM: F.: Theory of Computation / F.4: MATHEMATICAL LOGIC AND FORMAL LANGUAGES / F.4.3: Formal Languages (2)
    • [INFO.INFO-FL]Computer Science [cs] / Formal Languages and Automata Theory [cs.FL] (2)
    • ACM: F.: Theory of Computation / F.4: MATHEMATICAL LOGIC AND FORMAL LANGUAGES / F.4.3: Formal Languages / F.4.3.3: Decision problems (1)
    • XML streams (1)
    • XPath (1)
    • [INFO.INFO-LO]Computer Science [cs] / Logic in Computer Science [cs.LO] (1)
    • [INFO.INFO-SE]Computer Science [cs] / Software Engineering [cs.SE] (1)
    • algebraic characterizations (1)
    • arbres (1)
    • automata (1)
    •   more
  • 
    Creator / Publisher:
    
    • Gauwin, Olivier (3)
    • ANR-13-JS02-0010,EXSTREAM,Extensions du traitement par flux(2013) (2)
    • Laboratoire Bordelais de Recherche en Informatique (LaBRI) (2)
    • Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB) (2)
    • ANR-16-CE40-0007,DELTA,DÉfis pour la Logique, les Transducteurs et les Automates(2016) (1)
    • Baschenis, Félix (1)
    • Département d'Informatique Bruxelles (ULB) (1)
    • Faculté des Sciences Bruxelles (ULB) (1)
    • Filiot, Emmanuel (1)
    • Institut National de Recherche en Informatique et en Automatique (Inria) (1)
    • Joachim Niehren (1)
    • Laboratoire d'Informatique Fondamentale de Lille (LIFL) (1)
    • Lhote, Nathan (1)
    • Modeling Tree Structures, Machine Learning, and Information Extraction (MOSTRARE) (1)
    • Muscholl, Anca (1)
    • Puppis, Gabriele (1)
    • Université de Lille, Sciences et Technologies-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lille, Sciences Humaines et Sociales-Centre National de la Recherche Scientifique (CNRS) (1)
    • Université de Lille, Sciences et Technologies-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lille, Sciences Humaines et Sociales-Centre National de la Recherche Scientifique (CNRS)-Université de Lille, Sciences et Technologies-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lille, Sciences Humaines et Sociales-Centre National de la Recherche Scientifique (CNRS)-Inria Lille - Nord Europe (1)
    • Université des Sciences et Technologie de Lille - Lille I (1)
    • Université libre de Bruxelles (ULB)-Université libre de Bruxelles (ULB) (1)
  • 
    Year:
    
    • 2018 (1)
    • 2016 (1)
    • 2009 (1)
  • 
    Medium
  • 
    Type:
    
    • Article (2)
    • Book (1)
  • 
    BLLDB-Access:
    • free (3)
    • subject to license (0)

Search in the Catalogues and Directories

All fields Title Creator / Publisher Keyword Year AND OR AND NOT All fields Title Creator / Publisher Keyword Year AND OR AND NOT All fields Title Creator / Publisher Keyword Year AND OR AND NOT All fields Title Creator / Publisher Keyword Year AND OR AND NOT All fields Title Creator / Publisher Keyword Year Sort by creator [A → Z]' creator [Z → A]' publishing year ↑ (asc)' publishing year ↓ (desc)' title [A → Z]' title [Z → A]' Simple Search Hits 1 – 3 of 3 1 One-way definability of two-way word transducers Baschenis, Félix; Gauwin, Olivier; Muscholl, Anca... In: EISSN: 1860-5974 ; Logical Methods in Computer Science ; https://hal.archives-ouvertes.fr/hal-02121085 ; Logical Methods in Computer Science, Logical Methods in Computer Science Association, 2018, 14 (4), ⟨10.23638/LMCS-14(4:22)2018⟩ ; https://lmcs.episciences.org/5021 (2018) BASE Show details 2 First-order definability of rational transductions: An algebraic approach Filiot, Emmanuel; Gauwin, Olivier; Lhote, Nathan In: Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science (LICS'16) ; 31st Annual ACM/IEEE Symposium on Logic in Computer Science (LICS'16) ; https://hal.archives-ouvertes.fr/hal-01308509 ; 31st Annual ACM/IEEE Symposium on Logic in Computer Science (LICS'16), Jul 2016, New York, United States. pp.387--396, ⟨10.1145/2933575.2934520⟩ ; http://lics.rwth-aachen.de/lics16/ (2016) Abstract: International audience ; The algebraic theory of rational languages has provided powerful decidability results. Among them, one of the most fundamental is the definability of a rational language in the class of aperiodic languages, i.e., languages recognized by finite automata whose transition relation defines an aperiodic congruence. An important corollary of this result is the first-order definability of monadic second-order formulas over finite words. Our goal is to extend these results to rational transductions, i.e. word functions realized by finite transducers. We take an algebraic approach and consider definability problems of rational transductions in a given variety of congruences (or monoids). The strength of the algebraic theory of rational languages relies on the existence of a congruence canonically attached to every language, the syntactic congruence. In a similar spirit, Reutenauer and Schützenberger have defined a canonical device for rational transductions, that we extend to establish our main contribution: an effective characterization of V-transductions, i.e. rational transductions realizable by transducers whose transition relation defines a congruence in a (decidable) variety V. In particular, it provides an algorithm to decide the definability of a rational transduction by an aperiodic finite transducer. Using those results, we show that the FO-definability of a rational transduction is decidable, where FO-definable means definable in a first-order restriction of logical transducers a la Courcelle. Keyword: [INFO.INFO-FL]Computer Science [cs]/Formal Languages and Automata Theory [cs.FL]; [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO]; ACM: F.: Theory of Computation/F.4: MATHEMATICAL LOGIC AND FORMAL LANGUAGES/F.4.3: Formal Languages; ACM: F.: Theory of Computation/F.4: MATHEMATICAL LOGIC AND FORMAL LANGUAGES/F.4.3: Formal Languages/F.4.3.3: Decision problems; algebraic characterizations; definability problems; first-order logic; rational word transductions URL: https://hal.archives-ouvertes.fr/hal-01308509/file/main_lics.pdf https://doi.org/10.1145/2933575.2934520 https://hal.archives-ouvertes.fr/hal-01308509/document https://hal.archives-ouvertes.fr/hal-01308509 BASE Hide details 3 Streaming Tree Automata and XPath ; Flux XML, Requêtes XPath et Automates Gauwin, Olivier. - : HAL CCSD, 2009 In: https://tel.archives-ouvertes.fr/tel-00421911 ; Software Engineering [cs.SE]. Université des Sciences et Technologie de Lille - Lille I, 2009. English (2009) BASE Show details

Mobile view All Catalogues UB Frankfurt Linguistik 0 IDS Mannheim 0 OLC Linguistik 0 UB Frankfurt Retrokatalog 0 DNB Subject Category Language 0 Institut für Empirische Sprachwissenschaft 0 Leibniz-Centre General Linguistics (ZAS) 0 Bibliographies BLLDB 0 BDSL 0 IDS Bibliografie zur deutschen Grammatik 0 IDS Bibliografie zur Gesprächsforschung 0 IDS Konnektoren im Deutschen 0 IDS Präpositionen im Deutschen 0 IDS OBELEX meta 0 MPI-SHH Linguistics Collection 0 MPI for Psycholinguistics 0 Linked Open Data catalogues Annohub 0 Online resources Link directory 0 Journal directory 0 Database directory 0 Dictionary directory 0 Open access documents BASE 3 Linguistik-Repository 0 IDS Publikationsserver 0 Online dissertations 0 Language Description Heritage 0