Publikationen

Vince Bárány

2008

V. Bárány. A Hierarchy of Automatic $\omega$-Words having a Decidable MSO Theory. RAIRO - Theor. Inf. Appl., vol. 42, pp. 417-450, 2008.

Abstract BibTeX

We investigate automatic presentations of omega-words. Starting points of our study are the works of Rigo and Maes, Caucal, and Carton and Thomas concerning lexicographic presentation, MSO-interpretability in algebraic trees, and the decidability of the MSO theory of morphic words. Refining their techniques we observe that the lexicographic presentation of a (morphic) word is in a certain sense canonical. We then generalize our techniques to a hierarchy of classes of omega-words enjoying the above mentioned definability and decidability properties. We introduce k-lexicographic presentations, and morphisms of level k stacks and show that these are inter-translatable, thus giving rise to the same classes of k-lexicographic or level k morphic words. We prove that these presentations are also canonical, which implies decidability of the MSO theory of every k-lexicographic word as well as closure of these classes under MSO-definable recolorings, e.g. closure under deterministic sequential mappings. The classes of k-lexicographic words are shown to constitute an infinite hierarchy.

@article{Bar08ITA,
     author = {Vince Bárány},
     title = {A Hierarchy of Automatic $\omega$-Words having a Decidable MSO Theory},
     journal = {RAIRO - Theor. Inf. Appl.},
     volume = {42},
     pages = {417-450},
     year = {2008},
     doi = {10.1051/ita:2008008},
     url = {http://www.logic.rwth-aachen.de/~vbarany/hom_ITA.pdf},
}
Ł. Kaiser, S. Rubin, and V. Bárány. Cardinality and counting quantifiers on omega-automatic structures. In Proceedings of the 25th International Symposium on Theoretical Aspects of Computer Science, STACS 2008 (S. Albers and P. Weil, Eds.), pp. 385–396, 2008.

Abstract BibTeX

We investigate structures that can be represented by omega-automata, so called omega-automatic structures, and prove that relations defined over such structures in first-order logic expanded by the first-order quantifiers `there exist at most $\aleph_0$ many', 'there exist finitely many' and 'there exist $k$ modulo $m$ many' are omega-regular. The proof identifies certain algebraic properties of omega-semigroups. As a consequence an omega-regular equivalence relation of countable index has an omega-regular set of representatives. This implies Blumensath's conjecture that a countable structure with an $\omega$-automatic presentation can be represented using automata on finite words. This also complements a very recent result of Hjörth, Khoussainov, Montalban and Nies showing that there is an omega-automatic structure which has no injective presentation.

@inproceedings{BKR08,
     author = {Łukasz Kaiser and Sasha Rubin and Vince Bárány},
     title = {Cardinality and counting quantifiers on omega-automatic structures},
     booktitle = {Proceedings of the 25th International Symposium on Theoretical Aspects of Computer Science, STACS 2008},
     editor = {Susanne Albers and Pascal Weil},
     url = {http://www.logic.rwth-aachen.de/~kaiser/cardinality_automatic.pdf},
     pages = {385–396},
     year = {2008},
}

2007

V. Bárány. Automatic Presentations of Infinite Structures. PhD thesis, RWTH Aachen, 2007.

BibTeX

@phdthesis{Bar07diss,
     author = {V. Bárány},
     title = {Automatic Presentations of Infinite Structures},
     school = {RWTH Aachen},
     type = {Dissertation},
     year = {2007},
     url = {http://www.logic.rwth-aachen.de/~vbarany/diss.pdf},
}

2006

V. Bárány. A Hierarchy of Automatic Words having a Decidable MSO Theory. In Online Proceedings of the 11th Journées Montoises, Rennes (D. Caucal, Ed.), 2006.

Abstract BibTeX

We investigate automatic presentations of infinite words. Starting points of our study are the works of Rigo and Maes, and Carton and Thomas concerning the lexicographic presentation, respectively the decidability of the MSO theory of morphic words. Refining their techniques we observe that the lexicographic presentation of a (morphic) word is canonical in a certain sense. We then go on to generalize our techniques to a hierarchy of classes of infinite words enjoying the above mentioned properties. We introduce $k$-lexicographic presentations, and morphisms of level $k$ stacks and show that these are inter-translatable, thus giving rise to the same classes of $k$-lexicographic or level $k$ morphic words. We prove that these presentations are also canonical, which implies decidability of the MSO theory of every $k$-lexicographic word as well as closure of these classes under restricted MSO interpretations, e.g. closure under deterministic sequential mappings. The classes of $k$-lexicographic words are shown to form an infinite hierarchy.

@inproceedings{Bar06JM,
     author = {Vince Bárány},
     title = {A Hierarchy of Automatic Words having a Decidable MSO Theory},
     year = {2006},
     booktitle = {Online Proceedings of the 11th Journées Montoises, Rennes},
     editor = {D. Caucal},
     url = {http://www.logic.rwth-aachen.de/~vbarany/jm06.pdf},
}
V. Bárány, C. Löding, and O. Serre. Regularity Problems for Visibly Pushdown Languages. In Proceedings of the 23rd Annual Symposioum on Theoretical Aspects of Computer Science, STACS 2006 (B. Durand and W. Thomas, Eds.), vol. 3884 of LNCS, pp. 420–431. Springer, 2006.

Abstract BibTeX

Visibly pushdown automata are special pushdown automata whose stack behavior is driven by the input symbols according to a partition of the alphabet. We show that it is decidable for a given visibly pushdown automaton whether it is equivalent to a visibly counter automaton, i.e. an automaton that uses its stack only as counter. In particular, this allows to decide whether a given visibly pushdown language is a regular restriction of the set of well-matched words, meaning that the language can be accepted by a finite automaton if only well-matched words are considered as input.

@inproceedings{BLS06STACS,
     author = {Vince Bárány and Christof Löding and Olivier Serre},
     title = {Regularity Problems for Visibly Pushdown Languages},
     year = {2006},
     booktitle = {Proceedings of the 23rd Annual Symposioum on Theoretical Aspects of Computer Science, STACS 2006},
     editor = {B. Durand and W. Thomas},
     series = {LNCS},
     volume = {3884},
     pages = {420–431},
     publisher = {Springer},
     url = {http://www.logic.rwth-aachen.de/~vbarany/BLS_stacs06_withAppendix.pdf},
}
V. Bárány. Invariants of Automatic Presentations and Semi-Synchronous Transductions. In Proceedings of the 23rd Annual Symposioum on Theoretical Aspects of Computer Science, STACS 2006 (B. Durand and W. Thomas, Eds.), vol. 3884 of LNCS, pp. 289–300. Springer, 2006.

Abstract BibTeX

Automatic structures are countable structures finitely presentable by a collection of automata. We study questions related to properties invariant with respect to the choice of an automatic presentation. We give a negative answer to a question of Rubin concerning definability of intrinsically regular relations by showing that order-invariant first-order logic can be stronger than first-order logic with counting on automatic structures. We introduce a notion of equivalence of automatic presentations, define semi-synchronous transductions, and show how these concepts correspond. Our main result is that a one-to-one function on words preserves regularity as well as non-regularity of all relations iff it is a semi-synchronous transduction. We also characterize automatic presentations of the complete structures of Blumensath and Grädel.

@inproceedings{Bar06STACS,
     author = {Vince Bárány},
     title = {Invariants of Automatic Presentations and Semi-Synchronous Transductions},
     year = {2006},
     booktitle = {Proceedings of the 23rd Annual Symposioum on Theoretical Aspects of Computer Science, STACS 2006},
     editor = {B. Durand and W. Thomas},
     series = {LNCS},
     volume = {3884},
     pages = {289–300},
     publisher = {Springer},
     url = {http://www.logic.rwth-aachen.de/~vbarany/stacs06_88_appendix.pdf},
}