Forbidden-Patterns and Word Extensions for Concatenation Hierarchies

Starfree regular languages can be build up from alphabet letters by using only Boolean operations and concatenation. The complexity of these languages can be measured with the so-called dot-depth. This measure leads to concatenation hierarchies like the dot-depth hierarchy (DDH) and the closely related Straubing-Thérien hierarchy (STH). The question whether the single levels of these hierarchies are decidable is still open and is known as the dot-depth problem. In this thesis we prove/reprove the decidability of some lower levels of both hierarchies. More precisely, we characterize these levels in terms of patterns in finite automata (subgraphs in the transition graph) that are not allowed. Therefore, such characterizations are called forbidden-pattern characterizations. The main results of the thesis are as follows: forbidden-pattern characterization for level 3/2 of the DDH (this implies the decidability of this level) decidability of the Boolean hierarchy over level 1/2 of the DDH definition of decidable hierarchies having close relations to the DDH and STH Moreover, we prove/reprove the decidability of the levels 1/2 and 3/2 of both hierarchies in terms of forbidden-pattern characterizations. We show the decidability of the Boolean hierarchies over level 1/2 of the DDH and over level 1/2 of the STH. A technique which uses word extensions plays the central role in the proofs of these results. With this technique it is possible to treat the levels 1/2 and 3/2 of both hierarchies in a uniform way. Furthermore, it can be used to prove the decidability of the mentioned Boolean hierarchies. Among other things we provide a combinatorial tool that allows to partition words of arbitrary length into factors of bounded length such that every second factor u leads to a loop with label u in a given finite automaton.

Level thesis:degree_level

thesis.doctoral

Grantor dc:publisher

Universität Würzburg

Year

2001

Author dc:creator

• Glaßer, Christian

Contributors dc:contributor

• Wagner, Klaus W.

• Theoretische Informatik
• reguläre Sprachen
• endliche Automaten
• Dot-Depth Problem
• Entscheidbarkeit
• Verbotsmuster
• Worterweiterungen
• Theoretical Computer Science
• regular languages
• finite automata
• decidability
• forbidden patterns
• word extensions

Repository record source_url

https://opus.bibliothek.uni-wuerzburg.de/frontdoor/index/index/docId/238

OAI identifier oai:identifier

oai:opus.bibliothek.uni-wuerzburg.de:238