Search

Your search keyword '"Université de Varsovie-Université de Varsovie"' showing total 5 results
Start Over Author "Université de Varsovie-Université de Varsovie"
5 results on '"Université de Varsovie-Université de Varsovie"'

1. On the expressive power of non-deterministic and unambiguous Petri nets over infinite words

Author

Olivier Finkel, Michał Skrzypczak, Institut de Mathématiques de Jussieu - Paris Rive Gauche (IMJ-PRG), Université Pierre et Marie Curie - Paris 6 (UPMC)-Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Institute of Informatics, University of Warsaw, Banacha 2, 02-097 Warsaw, Poland., Institute of Informatics, and Université de Varsovie-Université de Varsovie

Subjects
FOS: Computer and information sciences, Logic in computer science, Algebra and Number Theory, TheoryofComputation_COMPUTATIONBYABSTRACTDEVICES, Formal Languages and Automata Theory (cs.FL), TheoryofComputation_GENERAL, Computer Science - Formal Languages and Automata Theory, Petri nets, Highly undecidable properties, Infinite words, Theoretical Computer Science, Borel hierarchy, Wadge degrees, [MATH.MATH-LO]Mathematics [math]/Logic [math.LO], Computational Theory and Mathematics, Unambiguous Petri nets, Computer Science::Logic in Computer Science, Cantor topology, Automata and formal languages, Computer Science::Formal Languages and Automata Theory, Information Systems
Abstract

We prove that $\omega$-languages of (non-deterministic) Petri nets and $\omega$-languages of (non-deterministic) Turing machines have the same topological complexity: the Borel and Wadge hierarchies of the class of $\omega$-languages of (non-deterministic) Petri nets are equal to the Borel and Wadge hierarchies of the class of $\omega$-languages of (non-deterministic) Turing machines. We also show that it is highly undecidable to determine the topological complexity of a Petri net $\omega$-language. Moreover, we infer from the proofs of the above results that the equivalence and the inclusion problems for $\omega$-languages of Petri nets are $\Pi_2^1$-complete, hence also highly undecidable. Additionally, we show that the situation is quite the opposite when considering unambiguous Petri nets, which have the semantic property that at most one accepting run exists on every input. We provide a procedure of determinising them into deterministic Muller counter machines with counter copying. As a consequence, we entail that the $\omega$-languages recognisable by unambiguous Petri nets are $\Delta^0_3$ sets., Comment: arXiv admin note: substantial text overlap with arXiv:1712.07945

Published
2021

2. Induced minors and well-quasi-ordering

Author

Jaroslaw Blasiok, Jean-Florent Raymond, Marcin Kamiński, Théophile Trunck, Department of Mathematics, Computer Science and Mechanics [Warsaw], University of Warsaw ( UW ), Institute of Informatics, University of Warsaw, Banacha 2, 02-097 Warsaw, Poland., Institute of Informatics, Université de Varsovie-Université de Varsovie, Faculty of Mathematics, Informatics, and Mechanics [Warsaw], Algorithmes, Graphes et Combinatoire ( ALGCO ), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier ( LIRMM ), Université de Montpellier ( UM ) -Centre National de la Recherche Scientifique ( CNRS ) -Université de Montpellier ( UM ) -Centre National de la Recherche Scientifique ( CNRS ), Laboratoire de l'Informatique du Parallélisme ( LIP ), École normale supérieure - Lyon ( ENS Lyon ) -Université Claude Bernard Lyon 1 ( UCBL ), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique ( Inria ) -Centre National de la Recherche Scientifique ( CNRS ), Faculty of Mathematics, Informatics, and Mechanics [Warsaw] (MIMUW), University of Warsaw (UW), Algorithmes, Graphes et Combinatoire (ALGCO), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS), Modèles de calcul, Complexité, Combinatoire (MC2), Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM), Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL)

Subjects
FOS: Computer and information sciences, Discrete Mathematics (cs.DM), Well-quasi-ordering, Induced subgraph, G.2.2, 0102 computer and information sciences, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], [ MATH.MATH-CO ] Mathematics [math]/Combinatorics [math.CO], 01 natural sciences, Theoretical Computer Science, Combinatorics, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], FOS: Mathematics, Combinatorial dichotomies, Mathematics - Combinatorics, Discrete Mathematics and Combinatorics, 0101 mathematics, ComputingMilieux_MISCELLANEOUS, Mathematics, Applied Mathematics, 010102 general mathematics, Complete graph, [ INFO.INFO-DM ] Computer Science [cs]/Discrete Mathematics [cs.DM], Graph theory, 16. Peace & justice, Graph, Vertex (geometry), Computational Theory and Mathematics, 010201 computation theory & mathematics, Combinatorics (math.CO), 05C, 06A07, Combinatorial theory, Induced minors, Computer Science - Discrete Mathematics
Abstract

A graph $H$ is an induced minor of a graph $G$ if it can be obtained from an induced subgraph of $G$ by contracting edges. Otherwise, $G$ is said to be $H$-induced minor-free. Robin Thomas showed that $K_4$-induced minor-free graphs are well-quasi-ordered by induced minors [Graphs without $K_4$ and well-quasi-ordering, Journal of Combinatorial Theory, Series B, 38(3):240 -- 247, 1985]. We provide a dichotomy theorem for $H$-induced minor-free graphs and show that the class of $H$-induced minor-free graphs is well-quasi-ordered by the induced minor relation if and only if $H$ is an induced minor of the gem (the path on 4 vertices plus a dominating vertex) or of the graph obtained by adding a vertex of degree 2 to the complete graph on 4 vertices. To this end we proved two decomposition theorems which are of independent interest. Similar dichotomy results were previously given for subgraphs by Guoli Ding in [Subgraphs and well-quasi-ordering, Journal of Graph Theory, 16(5):489--502, 1992] and for induced subgraphs by Peter Damaschke in [Induced subgraphs and well-quasi-ordering, Journal of Graph Theory, 14(4):427--435, 1990].

Published
2019
Full Text
View/download PDF

3. Reachability in fixed dimension vector addition systems with states

Author

Czerwiński, Wojciech, Lasota, Slawomir, Lazić, Ranko, Leroux, Jérôme, Mazowiecki, Filip, Institute of Informatics, University of Warsaw, Banacha 2, 02-097 Warsaw, Poland., Institute of Informatics, Université de Varsovie-Université de Varsovie, Department of Computer Science [Warwick], University of Warwick [Coventry], Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Max Planck Institute for Software Systems (MPI-SWS), Igor Konnov and Laura Kov{\'{a}}cs, ANR-17-CE40-0028,BRAVAS,IDEAL-BASED ALGORITHMS FOR VASSES AND WELL-STRUCTURED SYSTEMS(2017), Leroux, Jérôme, and IDEAL-BASED ALGORITHMS FOR VASSES AND WELL-STRUCTURED SYSTEMS - - BRAVAS2017 - ANR-17-CE40-0028 - AAPG2017 - VALID

Subjects
FOS: Computer and information sciences, Formal Languages and Automata Theory (cs.FL), Computer Science - Formal Languages and Automata Theory, [INFO]Computer Science [cs], [INFO] Computer Science [cs], ComputingMilieux_MISCELLANEOUS, QA76
Abstract

The reachability problem is a central decision problem for formal verification based on vector addition systems with states (VASS), which are equivalent to Petri nets and form one of the most studied and applied models of concurrency. Reachability for VASS is also inter-reducible with a plethora of problems from a number of areas of computer science. In spite of recent progress, the complexity of the reachability problem remains unsettled, and it is closely related to the lengths of shortest VASS runs that witness reachability. We consider VASS of fixed dimension, and obtain three main results. For the first two, we assume that the integers in the input are given in unary, and that the control graph of the given VASS is flat (i.e., without nested cycles). We obtain a family of VASS in dimension 3 whose shortest reachability witnessing runs are exponential, and we show that the reachability problem is NP-hard in dimension 7. These results resolve negatively questions that had been posed by the works of Blondin et al. in LICS 2015 and Englert et al. in LICS 2016, and contribute a first construction that distinguishes 3-dimensional flat VASS from 2-dimensional VASS. Our third result, by means of a novel family of products of integer fractions, shows that 4-dimensional VASS can have doubly exponentially long shortest reachability witnessing runs. The smallest dimension for which this was previously known is 14.

Published
2020
Full Text
View/download PDF

4. Bounding Average-energy Games

Author

Mickael Randour, Piotr Hofman, Nicolas Markey, Martin Zimmermann, Patricia Bouyer, Laboratoire Spécification et Vérification [Cachan] (LSV), École normale supérieure - Cachan (ENS Cachan)-Centre National de la Recherche Scientifique (CNRS), University of Warsaw (UW), SUpervision of large MOdular and distributed systems (SUMO), Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-LANGAGE ET GÉNIE LOGICIEL (IRISA-D4), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), Département d'Informatique [Bruxelles] (ULB), Faculté des Sciences [Bruxelles] (ULB), Université libre de Bruxelles (ULB)-Université libre de Bruxelles (ULB), Universität des Saarlandes [Saarbrücken], ArXiv, European Project: 308087,EC:FP7:ERC,ERC-2012-StG_20111012,EQUALIS(2013), Institute of Informatics, University of Warsaw, Banacha 2, 02-097 Warsaw, Poland., Institute of Informatics, Université de Varsovie-Université de Varsovie, Université de Bretagne Sud (UBS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Rennes (ENS Rennes)-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-CentraleSupélec-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Bretagne Sud (UBS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-École normale supérieure - Rennes (ENS Rennes)-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), CentraleSupélec-Télécom Bretagne-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Rennes (ENS Rennes)-Université de Bretagne Sud (UBS)-Centre National de la Recherche Scientifique (CNRS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-CentraleSupélec-Télécom Bretagne-Université de Rennes 1 (UR1), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-École normale supérieure - Rennes (ENS Rennes)-Université de Bretagne Sud (UBS)-Centre National de la Recherche Scientifique (CNRS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), and Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)

Subjects
FOS: Computer and information sciences, Computer Science - Logic in Computer Science, Computer Science::Computer Science and Game Theory, Formal Languages and Automata Theory (cs.FL), Computer Science - Formal Languages and Automata Theory, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Upper and lower bounds, Combinatorics, [INFO.INFO-FL]Computer Science [cs]/Formal Languages and Automata Theory [cs.FL], Computer Science - Computer Science and Game Theory, Bounding overwatch, Multiple time dimensions, 0202 electrical engineering, electronic engineering, information engineering, Mathematics, Discrete mathematics, [INFO.INFO-GT]Computer Science [cs]/Computer Science and Game Theory [cs.GT], [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO], Decidability, Logic in Computer Science (cs.LO), Constraint (information theory), 010201 computation theory & mathematics, 020201 artificial intelligence & image processing, Energy (signal processing), Computer Science and Game Theory (cs.GT)
Abstract

We consider average-energy games, where the goal is to minimize the long-run average of the accumulated energy. While several results have been obtained on these games recently, decidability of average-energy games with a lower-bound constraint on the energy level (but no upper bound) remained open; in particular, so far there was no known upper bound on the memory that is required for winning strategies. By reducing average-energy games with lower-bounded energy to infinite-state mean-payoff games and analyzing the density of low-energy configurations, we show an almost tight doubly-exponential upper bound on the necessary memory, and that the winner of average-energy games with lower-bounded energy can be determined in doubly-exponential time. We also prove EXPSPACE-hardness of this problem. Finally, we consider multi-dimensional extensions of all types of average-energy games: without bounds, with only a lower bound, and with both a lower and an upper bound on the energy. We show that the fully-bounded version is the only case to remain decidable in multiple dimensions., Comment: Full version of FoSSaCS 2017 paper

Published
2016
Full Text
View/download PDF

5. On the Topological Complexity of omega-Languages of Non-Deterministic Petri Nets

Author

Finkel, Olivier, Skrzypczak, Michał, Équipe de Logique Mathématique (ELM), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Institut de Mathématiques de Jussieu (IMJ), Université Pierre et Marie Curie - Paris 6 (UPMC)-Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Institute of Informatics, University of Warsaw, Banacha 2, 02-097 Warsaw, Poland., Institute of Informatics, Université de Varsovie-Université de Varsovie, and The second author has been supported by National Science Centre grant no. DEC-2012/05/N/ST6/03254.

Subjects
Cantor space, [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], FOS: Computer and information sciences, Computer Science - Logic in Computer Science, TheoryofComputation_COMPUTATIONBYABSTRACTDEVICES, complete sets, Formal Languages and Automata Theory (cs.FL), [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO], Petri nets, Computer Science - Formal Languages and Automata Theory, Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing), Languages of infinite words, Computational Complexity (cs.CC), Borel hierarchy, Logic in Computer Science (cs.LO), Computer Science - Computational Complexity, Computer Science::Logic in Computer Science, topological complexity, Büchi acceptance condition, Computer Science::Formal Languages and Automata Theory
Abstract

International audience; We show that there are $\Sigma_3^0$-complete languages of infinite words accepted by non-deterministic Petri nets with Büchi acceptance condition, or equivalently by Büchi blind counter automata. This shows that omega-languages accepted by non-deterministic Petri nets are topologically more complex than those accepted by deterministic Petri nets.

Published
2014
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results