 |
 |
Special Issue in Honor of Zoltán Ésik
Editors: Luca Aceto, Arnaud Carayol, Anna Ingólfsdóttir
1. Algebraic and logical descriptions of generalized trees
Quasi-trees generalize trees in that the unique "path" between two nodes may be infinite and have any countable order type. They are used to define the rank-width of a countable graph in such a way that it is equal to the least upper-bound of the rank-widths of its finite induced subgraphs. Join-trees are the corresponding directed trees. They are useful to define the modular decomposition of a countable graph. We also consider ordered join-trees, that generalize rooted trees equipped with a linear order on the set of sons of each node. We define algebras with finitely many operations that generate (via infinite terms) these generalized trees. We prove that the associated regular objects (those defined by regular terms) are exactly the ones that are the unique models of monadic second-order sentences. These results use and generalize a similar result by W. Thomas for countable linear orders.
2. Petri Automata
Kleene algebra axioms are complete with respect to both language models and binary relation models. In particular, two regular expressions recognise the same language if and only if they are universally equivalent in the model of binary relations. We consider Kleene allegories, i.e., Kleene algebras with two additional operations and a constant which are natural in binary relation models: intersection, converse, and the full relation. While regular languages are closed under those operations, the above characterisation breaks. Putting together a few results from the literature, we give a characterisation in terms of languages of directed and labelled graphs. By taking inspiration from Petri nets, we design a finite automata model, Petri automata, allowing to recognise such graphs. We prove a Kleene theorem for this automata model: the sets of graphs recognisable by Petri automata are precisely the sets of graphs definable through the extended regular expressions we consider. Petri automata allow us to obtain decidability of identity-free relational Kleene lattices, i.e., the equational theory generated by binary relations on the signature of regular expressions with intersection, but where one forbids unit. This restriction is used to ensure that the corresponding graphs are acyclic. We actually show that this decision problem is EXPSPACE-complete.
3. Pushing for weighted tree automata
A weight normalization procedure, commonly called pushing, is introduced for weighted tree automata (wta) over commutative semifields. The normalization preserves the recognized weighted tree language even for nondeterministic wta, but it is most useful for bottom-up deterministic wta, where it can be used for minimization and equivalence testing. In both applications a careful selection of the weights to be redistributed followed by normalization allows a reduction of the general problem to the corresponding problem for bottom-up deterministic unweighted tree automata. This approach was already successfully used by Mohri and Eisner for the minimization of deterministic weighted string automata. Moreover, the new equivalence test for two wta $M$ and $M'$ runs in time $\mathcal O((\lvert M \rvert + \lvert M'\rvert) \cdot \log {(\lvert Q\rvert + \lvert Q'\rvert)})$, where $Q$ and $Q'$ are the states of $M$ and $M'$, respectively, which improves the previously best run-time $\mathcal O(\lvert M \rvert \cdot \lvert M'\rvert)$.
4. Weighted omega-Restricted One Counter Automata
Let $S$ be a complete star-omega semiring and $\Sigma$ be an alphabet. For a weighted $\omega$-restricted one-counter automaton $\mathcal{C}$ with set of states $\{1, \dots, n\}$, $n \geq 1$, we show that there exists a mixed algebraic system over a complete semiring-semimodule pair ${((S \ll \Sigma^* \gg)^{n\times n}, (S \ll \Sigma^{\omega}\gg)^n)}$ such that the behavior $\Vert\mathcal{C} \Vert$ of $\mathcal{C}$ is a component of a solution of this system. In case the basic semiring is $\mathbb{B}$ or $\mathbb{N}^{\infty}$ we show that there exists a mixed context-free grammar that generates $\Vert\mathcal{C} \Vert$. The construction of the mixed context-free grammar from $\mathcal{C}$ is a generalization of the well-known triple construction in case of restricted one-counter automata and is called now triple-pair construction for $\omega$-restricted one-counter automata.
5. A survey on difference hierarchies of regular languages
Difference hierarchies were originally introduced by Hausdorff and they play an important role in descriptive set theory. In this survey paper, we study difference hierarchies of regular languages. The first sections describe standard techniques on difference hierarchies, mostly due to Hausdorff. We illustrate these techniques by giving decidability results on the difference hierarchies based on shuffle ideals, strongly cyclic regular languages and the polynomial closure of group languages.
6. Monadic Second Order Logic with Measure and Category Quantifiers
We investigate the extension of Monadic Second Order logic, interpreted over infinite words and trees, with generalized "for almost all" quantifiers interpreted using the notions of Baire category and Lebesgue measure.
Section:
Automata and logic
7. Extensional Semantics for Higher-Order Logic Programs with Negation
We develop an extensional semantics for higher-order logic programs with negation, generalizing the technique that was introduced in [Bezem99,Bezem01] for positive higher-order programs. In this way we provide an alternative extensional semantics for higher-order logic programs with negation to the one proposed in [CharalambidisER14]. As an immediate useful consequence of our developments, we define for the language we consider the notions of stratification and local stratification, which generalize the familiar such notions from classical logic programming. We demonstrate that for stratified and locally stratified higher-order logic programs, the proposed semantics never assigns the unknown truth value. We conclude the paper by providing a negative result: we demonstrate that the well-known stable model semantics of classical logic programming, if extended according to the technique of [Bezem99,Bezem01] to higher-order logic programs, does not in general lead to extensional stable models.
8. Reasoning About Bounds in Weighted Transition Systems
We propose a way of reasoning about minimal and maximal values of the weights of transitions in a weighted transition system (WTS). This perspective induces a notion of bisimulation that is coarser than the classic bisimulation: it relates states that exhibit transitions to bisimulation classes with the weights within the same boundaries. We propose a customized modal logic that expresses these numeric boundaries for transition weights by means of particular modalities. We prove that our logic is invariant under the proposed notion of bisimulation. We show that the logic enjoys the finite model property and we identify a complete axiomatization for the logic. Last but not least, we use a tableau method to show that the satisfiability problem for the logic is decidable.
9. An $\omega$-Algebra for Real-Time Energy Problems
We develop a $^*$-continuous Kleene $\omega$-algebra of real-time energy functions. Together with corresponding automata, these can be used to model systems which can consume and regain energy (or other types of resources) depending on available time. Using recent results on $^*$-continuous Kleene $\omega$-algebras and computability of certain manipulations on real-time energy functions, it follows that reachability and Büchi acceptance in real-time energy automata can be decided in a static way which only involves manipulations of real-time energy functions.
10. On Free $\omega$-Continuous and Regular Ordered Algebras
We study varieties of certain ordered $\Sigma$-algebras with restricted completeness and continuity properties. We give a general characterization of their free algebras in terms of submonads of the monad of $\Sigma$-coterms. Varieties of this form are called \emph{quasi-regular}. For example, we show that if $E$ is a set of inequalities between finite $\Sigma$-terms, and if $\mathcal{V}_\omega$ and $\mathcal{V}_\mathrm{reg}$ denote the varieties of all $\omega$-continuous ordered $\Sigma$-algebras and regular ordered $\Sigma$-algebras satisfying $E$, respectively, then the free $\mathcal{V}_\mathrm{reg}$-algebra $F_\mathrm{reg}(X)$ on generators $X$ is the subalgebra of the corresponding free $\mathcal{V}_\omega$-algebra $F_\omega(X)$ determined by those elements of $F_\omega(X)$ denoted by the regular $\Sigma$-coterms. This is a special case of a more general construction that applies to any quasi-regular family. Examples include the *-continuous Kleene algebras, context-free languages, $\omega$-continuous semirings and $\omega$-continuous idempotent semirings, OI-macro languages, and iteration theories.