Author name cluster

David Janin

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

5 papers

2 author rows

I&C Journal 2015 Journal Article

On labeled birooted tree languages: Algebras, automata and logic

David Janin

With an aim to developing expressive language theoretical tools applicable to inverse semigroup languages, that is, subsets of inverse semigroups, this paper explores the language theory of finite labeled birooted trees: Munn's birooted trees extended with vertex labeling. To this purpose, we define a notion of finite state birooted tree automata that simply extends finite state word automata semantics. This notion is shown to capture the class of languages that are definable in Monadic Second Order Logic and upward closed with respect to the natural order. Then, we derive from these automata the notion of quasi-recognizable languages, that is, languages recognizable by means of (adequate) premorphisms into finite (adequately) ordered monoids. This notion is shown to capture finite Boolean combinations of languages as above, a class that contains classical regular languages of finite (mono-rooted) trees. This contrasts with the known collapse of classical algebraic tools when applied to inverse semigroups.

Details DOI

Highlights Conference 2013 Conference Abstract

From strings to higher dimensional strings

David Janin

There are well-known connections between word language theory and semigroup theory, mediated by free monoids, with deep link with the theory of finite state automata. By considering free inverse monoids instead of free monoids and premorphisms into ordered monoids instead of morphisms into monoids, we manage to lift these connections to languages of finite trees and, beyond, towards a more general notion of higher dimensional strings. In this talk, we will give a quick overview of the background results with a special emphasis on the main underlying concepts and methods.

PDF Details

MFCS Conference 2012 Conference Paper

Quasi-recognizable vs MSO Definable Languages of One-Dimensional Overlapping Tiles - (Extended Abstract)

David Janin

Abstract It has been shown [6] that, within the McAlister inverse monoid [10], whose elements can be seen as overlapping one-dimensional tiles, the class of languages recognizable by finite monoids collapses compared with the class of languages definable in Monadic Second Order Logic (MSO). This paper aims at capturing the expressive power of the MSO definability of languages of tiles by means of a weakening of the notion of algebraic recognizability which we shall refer to as quasi-recognizability. For that purpose, since the collapse of algebraic recognizability is intrinsically linked with the notion of monoid morphism itself, we propose instead to use premorphisms, monotonic mappings on ordered monoids that are only required to be sub-multiplicative with respect to the monoid product, i. e. mapping φ so that for all x and y, φ ( xy ) ≤ φ ( x ) φ ( y ). In doing so, we indeed obtain, with additional but relatively natural closure conditions, the expected quasi-algebraic characterization of MSO definable languages of positive tiles. This result is achieved via the axiomatic definition of an original class of well-behaved ordered monoid so that quasi-recognizability implies MSO definability. An original embedding of any (finite) monoid S into a (finite) well-behaved ordered monoid \({\mathcal Q}(S)\) is then used to prove the converse.

Details

MFCS Conference 1999 Conference Paper

On the Structure of the Monadic Logic of the Binary Tree

David Janin
Giacomo Lenzi

Abstract Since the work of Rabin [ 9 ], it has been known that any monadic second order property of the (labeled) binary tree with successor functions (and not the prefix ordering) is a monadic Δ 3 property. In this paper, we show this upper bound is optimal in the sense that there is a monadic Σ 2 formula, stating the existence of a path where a given predicate holds infinitely often, which is not equivalent to any monadic Σ 2 formula. We even show that some monadic second order definable properties of the binary tree are not definable by any boolean combination of monadic Σ 2 and Σ 2 formulas. These results rely in particular on applications of Ehrenfeucht-Fraïssé like game techniques to the case of monadic Σ 2 formulas.

Details

MFCS Conference 1995 Conference Paper

Automata for the Modal mu-Calculus and related Results

David Janin
Igor Walukiewicz

Abstract The propositional Μ -calculus as introduced by Kozen in [4] is considered. The notion of disjunctive formula is defined and it is shown that every formula is semantically equivalent to a disjunctive formula. For these formulas many difficulties encountered in the general case may be avoided. For instance, satisfiability checking is linear for disjunctive formulas. This kind of formula gives rise to a new notion of finite automaton which characterizes the expressive power of the Μ -calculus over all transition systems.

Details