CSR-2016_paper_66.pdf (633.39 kB)
Download file

The word problem for omega-terms over the Trotter-Weil hierarchy [extended abstract]

Download (633.39 kB)
conference contribution
posted on 22.02.2018, 11:38 authored by Manfred Kufleitner, Jan Philipp Wachter
© Springer International Publishing Switzerland 2016. Over finitewords, there is a tight connection between the quantifier alternation hierarchy inside two-variable first-order logic FO 2 and a hierarchy of finite monoids: theTrotter-Weil Hierarchy. The variousways of climbing up this hierarchy include Mal’cev products, deterministic and codeterministic concatenation as well as identities of ω-terms.We show that the word problem for ω-terms over each level of the Trotter-Weil Hierarchy is decidable; this means, for every variety V of the hierarchy and every identity u = v of ω-terms, one can decide whether all monoids in V satisfy u = v. More precisely, for every fixed variety V, our approach yields nondeterministic logarithmic space (NL) and deterministic polynomial time algorithms, which are more efficient than straightforward translations of the NL-algorithms. From a language perspective, the word problem for ω- terms is the following: for every language variety V in theTrotter-Weil Hierarchy and every language varietyWgivenbyan identity of ω-terms, one can decide whether V ⊆ W. This includes the case where V is some level of the FO 2 quantifier alternation hierarchy. As an application of our results, we show that the separation problems for the so-called corners of the Trotter- Weil Hierarchy are decidable.

Funding

The first author was supported by the German Research Foundation (DFG) under grants DI 435/5-2 and KU 2716/1-1.

History

School

  • Science

Department

  • Computer Science

Published in

International Computer Science Symposium in Russia, CSR 2016 Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Volume

9691

Pages

237 - 250

Citation

KUFLEITNER, M. and WACHTER, J.P., 2016. The word problem for omega-terms over the Trotter-Weil hierarchy [extended abstract]. IN: Kulikov, A.S. and Woeginger, G.J. (eds.) Computer Science Theory and Applications: 11th International Computer Science Symposium in Russia (CSR 2016), St. Petersburg, Russia, June 9-13, 2016, Proceedings, Chaim: Springer, pp. 237-250.

Publisher

© Springer

Version

AM (Accepted Manuscript)

Publisher statement

This work is made available according to the conditions of the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0) licence. Full details of this licence are available at: https://creativecommons.org/licenses/by-nc-nd/4.0/

Publication date

2016

Notes

This is a pre-copyedited version of a contribution published in Computer Science Theory and Applications: 11th International Computer Science Symposium in Russia (CSR 2016) edited by Kulikov, A.S. and Woeginger, G.J. published by Springer International. The definitive authenticated version is available online via https://doi.org/10.1007/978-3-319-34171-2_17

ISBN

9783319341705

ISSN

0302-9743

eISSN

1611-3349

Book series

Lecture Notes in Computer Science;9691

Language

en

Location

St. Petersburg, Russia

Usage metrics

Keywords

Exports