Zobrazeno 1 - 10
of 43
pro vyhledávání: '"Kartzow, Alexander"'
Autor:
Kartzow, Alexander
We study the first-order model checking problem on two generalisations of pushdown graphs. The first class is the class of nested pushdown trees. The other is the class of collapsible pushdown graphs. Our main results are the following. First-order l
Autor:
Kartzow, Alexander, Weidner, Thomas
Constraint automata are an adaptation of B\"uchi-automata that process data words where the data comes from some relational structure S. Every transition of such an automaton comes with constraints in terms of the relations of S. A transition can onl
Externí odkaz:
http://arxiv.org/abs/1504.06105
Recently, we have shown that satisfiability for $\mathsf{ECTL}^*$ with constraints over $\mathbb{Z}$ is decidable using a new technique. This approach reduces the satisfiability problem of $\mathsf{ECTL}^*$ with constraints over some structure A (or
Externí odkaz:
http://arxiv.org/abs/1412.2905
Autor:
Kartzow, Alexander
Recently, Schlicht and Stephan lifted the notion of automatic-structures to the notion of (finite-word) ordinal-automatic structures. These are structures whose domain and relations can be represented by automata reading finite words whose shape is s
Externí odkaz:
http://arxiv.org/abs/1410.5197
Autor:
Heußner, Alexander, Kartzow, Alexander
Higher-order counter automata (\HOCS) can be either seen as a restriction of higher-order pushdown automata (\HOPS) to a unary stack alphabet, or as an extension of counter automata to higher levels. We distinguish two principal kinds of \HOCS: those
Externí odkaz:
http://arxiv.org/abs/1306.1069
We show that satisfiability for CTL* with equality-, order-, and modulo-constraints over Z is decidable. Previously, decidability was only known for certain fragments of CTL*, e.g., the existential and positive fragments and EF.
Comment: To appe
Comment: To appe
Externí odkaz:
http://arxiv.org/abs/1306.0814
Autor:
Kartzow, Alexander, Schlicht, Philipp
Bruyere and Carton lifted the notion of finite automata reading infinite words to finite automata reading words with shape an arbitrary linear order L. Automata on finite words can be used to represent infinite structures, the so-called word-automati
Externí odkaz:
http://arxiv.org/abs/1304.0912
Autor:
Kartzow, Alexander
Publikováno v:
Logical Methods in Computer Science, Volume 9, Issue 1 (March 20, 2013) lmcs:1220
We show that graphs generated by collapsible pushdown systems of level 2 are tree-automatic. Even if we allow epsilon-contractions and reachability predicates (with regular constraints) for pairs of configurations, the structures remain tree-automati
Externí odkaz:
http://arxiv.org/abs/1303.2453
Autor:
Kartzow, Alexander
We introduce a new hierarchy of higher-order nested pushdown trees generalising Alur et al.'s concept of nested pushdown trees. Nested pushdown trees are useful representations of control flows in the verification of programs with recursive calls of
Externí odkaz:
http://arxiv.org/abs/1202.1980
Autor:
Kartzow, Alexander
We study the first-order model checking problem on two generalisations of pushdown graphs. The first class is the class of nested pushdown trees. The other is the class of collapsible pushdown graphs. Our main results are the following. First-order l
Externí odkaz:
http://arxiv.org/abs/1202.0137