Global ETD Search

11	Decidability Equivalence between the Star Problem and the Finite Power Problem in Trace Monoids Kirsten, Daniel, Richomme, Gwénaël 28 November 2012 (has links) In the last decade, some researches on the star problem in trace monoids (is the iteration of a recognizable language also recognizable?) has pointed out the interest of the finite power property to achieve partial solutions of this problem. We prove that the star problem is decidable in some trace monoid if and only if in the same monoid, it is decidable whether a recognizable language has the finite power property. Intermediary results allow us to give a shorter proof for the decidability of the two previous problems in every trace monoid without C4-submonoid. We also deal with some earlier ideas, conjectures, and questions which have been raised in the research on the star problem and the finite power property, e.g. we show the decidability of these problems for recognizable languages which contain at most one non-connected trace. info:eu-repo/classification/ddc/004 ddc:004
12	Two Techniques in the Area of the Star Problem Kirsten, Daniel, Marcinkowski, Jerzy 30 November 2012 (has links) This paper deals with decision problems related to the star problem in trace monoids, which means to determine whether the iteration of a recognizable trace language is recognizable. Due to a theorem by G. Richomme from 1994 [32, 33], we know that the star problem is decidable in trace monoids which do not contain a submonoid of the form {a,c}* x {b,d}. Here, we consider a more general problem: Is it decidable whether for some recognizable trace language and some recognizable or finite trace language P the intersection R ∩ P is recognizable? If P is recognizable, then we show that this problem is decidale iff the underlying trace monoid does not contain a submonoid of the form {a,c}* x b*. In the case of finite languages P, we show several decidability and undecidability results. info:eu-repo/classification/ddc/004 ddc:004
13	Algorithmische Eigenschaften von Branching-Time Logiken Bauer, Sebastian 14 January 2007 (has links) (PDF) Es wird die Axiomatisierbarkeit einer Klasse von temporalen Prädikatenlogiken über verzweigenden Strukturen gezeigt. Entscheidbarkeitsresultate folgen für diverse Fragmente dieser Logiken. Anwendungen werden diskutiert. Temorallogik quantifizierte Temporallogik Axiomatisierbarkeit Entscheidbarkeit Fragmante temporaler Prädikatenlogiken Bäume temporal logic first-order temporal logic axiomatizability decidability fragments of first-order temporal logic branching-time logic monodic fragments ddc:100 rvk:SK 130 rvk:CC 2600 Temporale Logik
14	Algorithmische Eigenschaften von Branching-Time Logiken Bauer, Sebastian 18 April 2006 (has links) Es wird die Axiomatisierbarkeit einer Klasse von temporalen Prädikatenlogiken über verzweigenden Strukturen gezeigt. Entscheidbarkeitsresultate folgen für diverse Fragmente dieser Logiken. Anwendungen werden diskutiert. info:eu-repo/classification/ddc/100 ddc:100 Temporale Logik

Page generated in 0.0401 seconds