Mathematical Foundations of Computer Science 2009
34th International Symposium, MFCS 2009, Novy Smokovec, High Tatras, Slovakia, August 24-28, 2009. Proceedings
Page
%P
-
Article
Open AccessOn the Separation Question for Tree Languages
We show that the separation property fails for the classes Σ n of the Rabin-Mostowski index hierarchy of alternating automata on infinite trees. This ex...
-
Chapter
On Topological Completeness of Regular Tree Languages
We identify the class of \({\bf\Sigma}^{1}_{1}\) –inductive sets studied by Moschovakis as a set theoretical generalizat...
-
Book and Conference Proceedings
-
Chapter and Conference Paper
Unsafe Grammars and Panic Automata
We show that the problem of checking if an infinite tree generated by a higher-order grammar of level 2 (hyperalgebraic) satisfies a given μ-calculus formula (or, equivalently, if it is accepted by an alternating...
-
Chapter and Conference Paper
Higher-Order Pushdown Trees Are Easy
We show that the monadicsec ond-order theory of an infinite tree recognized by a higher-order pushdown automaton of any level is decidable. We also show that trees recognized by pushdown automata of level n coinc...
-
Chapter and Conference Paper
μ-Calculus via Games (Extended Abstract)
In this survey I would like to present some connections between the μ-calculus and games, more specifically games of possibly infinite duration played on labeled graphs. A fundamental connection was establishe...
-
Chapter and Conference Paper
Deciding Monadic Theories of Hyperalgebraic Trees
We show that the monadic second-order theory of any infinite tree generated by a higher-order grammar of level 2 subject to a certain syntactic restriction is decidable. By this we extend the result of Courcel...
-
Chapter and Conference Paper
Relating hierarchies of word and tree automata
For an ω-word language L, the derived tree language Path(L) is the language of trees having all their paths in L. We consider the hierarchies of deterministic automata on words and nondeterministic automata on tr...
-
Chapter and Conference Paper
First-order queries over temporal databases inexpressible in temporal logic
Queries over temporal databases involve references to time. We study differences between two approaches of including such references into a first-order query language (e.g., relational calculus): explicit (usi...
-
Chapter and Conference Paper
Automata on infinite trees with counting constraints
We investigate finite automata on infinite trees with the usual Muller criterion for the success of an infinite computation path, but with the acceptance paradigm modified in that not all the computation paths...
-
Chapter and Conference Paper
On the cardinality of sets of infinite trees recognizable by finite automata
We show that a Rabin recognizable set of trees is uncountable iff it is of the cardinality continuum iff it contains a non-regular tree. If a Rabin recognizable set L is countable, it can be represented as ...
-
Chapter and Conference Paper
On fixed-point clones
Expressions involving least and greatest fixed point operators are interpreted in the power-set algebra of (possibly infinite) trees and also in some abstract models. Initiality of the tree algebra is established...
-
Chapter and Conference Paper
Equational μ-calculus
-
Chapter and Conference Paper
Fixed-point semantics for algebraic (tree) grammars
