Loading...
Please wait, while we are loading the content...
Similar Documents
A syntactic congruence for languages of birooted trees
| Content Provider | Semantic Scholar |
|---|---|
| Author | Blumensath, Achim Janin, David |
| Copyright Year | 2017 |
| Abstract | The study of languages of labelled birooted trees, that is, elements of the free inverse monoid enriched by a vertex labelling, has led to the notion of quasi-recognisability. It generalises the usual notion of recognisability by replacing homomorphisms by certain prehomomorphism into finite ordered monoids, called adequate, that only preserve some products: the so-called disjoint ones. In this paper we study the underlying partial algebra setting and we define a suitable notion of a syntactic congruence such that (i) having a syntactic congruence of finite index captures MSO-definability; (ii) a certain order-bisimulation refinement of the syntactic congruence captures quasi-recognisability in the same way. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | https://hal.archives-ouvertes.fr/hal-00947972/document |
| Language | English |
| Access Restriction | Open |
| Subject Keyword | Algorithm Arabic numeral 0 Bisimulation Congruence of squares Graph (discrete mathematics) Graphical user interface HL7PublishingSubSection |
| Content Type | Text |
| Resource Type | Article |
