Source author record

Tobias Walter

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Formal Languages and Automata Theory Logic in Computer Science

Catalog footprint

Research overview

4works

2topics

3close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

Characterizing classes of regular languages using prefix codes of bounded synchronization delay

In this paper we continue a classical work of Schützenberger on codes with bounded synchronization delay. He was interested to characterize those regular languages where the groups in the syntactic monoid belong to a variety $H$ . He allowed operations on the language side which are union, intersection, concatenation and modified Kleene-star involving a mapping of a prefix code of bounded synchronization delay to a group $G\in H$ , but no complementation. In our notation this leads to the language classes $SD_G(A^\infty)$ and $SD_H(A^\infty$ ). Our main result shows that $SD_H(A^\infty)$ always corresponds to the languages having syntactic monoids where all subgroups are in $H$ . Schützenberger showed this for a variety $H$ if $H$ contains Abelian groups, only. Our method shows the general result for all $H$ directly on finite and infinite words. Furthermore, we introduce the notion of local Rees products which refers to a simple type of classical Rees extensions. We give a decomposition of a monoid in terms of its groups and local Rees products. This gives a somewhat similar, but simpler decomposition than in Rhodes' synthesis theorem. Moreover, we need a singly exponential number of operations, only. Finally, our decomposition yields an answer to a question in a recent paper of Almeida and Klíma about varieties that are closed under Rees products.

preprint2015arXiv

Level Two of the Quantifier Alternation Hierarchy over Infinite Words

The study of various decision problems for logic fragments has a long history in computer science. This paper is on the membership problem for a fragment of first-order logic over infinite words; the membership problem asks for a given language whether it is definable in some fixed fragment. The alphabetic topology was introduced as part of an effective characterization of the fragment $Σ_2$ over infinite words. Here, $Σ_2$ consists of the first-order formulas with two blocks of quantifiers, starting with an existential quantifier. Its Boolean closure is $\mathbb{B}Σ_2$ . Our first main result is an effective characterization of the Boolean closure of the alphabetic topology, that is, given an $ω$ -regular language $L$ , it is decidable whether $L$ is a Boolean combination of open sets in the alphabetic topology. This is then used for transferring Place and Zeitoun's recent decidability result for $\mathbb{B}Σ_2$ from finite to infinite words.

preprint2014arXiv

One Quantifier Alternation in First-Order Logic with Modular Predicates

Adding modular predicates yields a generalization of first-order logic FO over words. The expressive power of FO[<,MOD] with order comparison $x<y$ and predicates for $x \equiv i \mod n$ has been investigated by Barrington, Compton, Straubing and Therien. The study of FO[<,MOD]-fragments was initiated by Chaubard, Pin and Straubing. More recently, Dartois and Paperman showed that definability in the two-variable fragment FO2[<,MOD] is decidable. In this paper we continue this line of work. We give an effective algebraic characterization of the word languages in Sigma2[<,MOD]. The fragment Sigma2 consists of first-order formulas in prenex normal form with two blocks of quantifiers starting with an existential block. In addition we show that Delta2[<,MOD], the largest subclass of Sigma2[<,MOD] which is closed under negation, has the same expressive power as two-variable logic FO2[<,MOD]. This generalizes the result FO2[<] = Delta2[<] of Therien and Wilke to modular predicates. As a byproduct, we obtain another decidable characterization of FO2[<,MOD].

preprint2012arXiv

Regular Languages are Church-Rosser Congruential

This paper proves a long standing conjecture in formal language theory. It shows that all regular languages are Church-Rosser congruential. The class of Church-Rosser congruential languages was introduced by McNaughton, Narendran, and Otto in 1988. A language L is Church-Rosser congruential, if there exists a finite confluent, and length-reducing semi-Thue system S such that L is a finite union of congruence classes modulo S. It was known that there are deterministic linear context-free languages which are not Church-Rosser congruential, but on the other hand it was strongly believed that all regular language are of this form. Actually, this paper proves a more general result.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.