Minimal equational representations of recognizable tree languages

DOI10.1007/S002360050071MaRDI QIDQ1901719zbMATH OpenOpenAlexFDO

Authors Zoltán Fülöp, Sándor Vágvölgyi

Publication date 15 November 1995

Published in Acta Informatica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s002360050071

zbMATH Keywords

congruential tree languagesdeterministic bottom-up tree automatonequational representationsrecognizable tree languagesterm algebratree language

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Review text

A tree language is congruential if it is the union of finitely many classes of a finitely generated congruence on the term algebra. It is well known that congruential tree languages are the same as recognizable tree languages. An equational representation is an ordered pair \((E,P)\), where \(E\) is either a ground term equation system or a ground term rewriting system, and \(P\) is a finite set of ground terms. We say that \((E,P)\) represents the congruential tree language \(L\) which is the union of those \(\leftrightarrow^*_E\)-classes containing an element of \(P\), i.e., for which \(L = \bigcup \{[p]_{\leftrightarrow^*_E} |p \in P\}\). We define two sorts of minimality for equational representations. We introduce the cardinality vector \((|E|, |P|)\) of an equational representation \((E, P)\). Let \(\preceq_l\) and \(\preceq_a\) denote the lexicographic and antilexicographic orders on the set of ordered pairs of nonnegative integers, respectively. Let \(L\) be a congruential tree language. An equational representation \((E,P)\) of \(L\) with \(\preceq_l\)-minimal (\(\preceq_a\)-minimal) cardinality vector is called \(\preceq_l\)-minimal (\(\preceq_a\)-minimal). We compute, for an \(L\) given by a deterministic bottom-up tree automaton, both a \(\preceq_l\)-minimal and a \(\preceq_a\)-minimal equational representation of \(L\).

Recommendations

• A fast algorithm for constructing a tree automaton recognizing a congruential tree language
• Tree algebras and varieties of tree languages
• scientific article; zbMATH DE number 4135419
• scientific article; zbMATH DE number 139615
• Représentations matricielles des séries d'arbre reconnaissables

Cited in

(12)

• Deterministic bottom-up tree transducers and ground term rewrite systems
• A fast algorithm for constructing a tree automaton recognizing a congruential tree language
• Intersection of finitely generated congruences over term algebra
• Term rewriting restricted to ground terms.
• On ground tree transformations and congruences induced by tree automata.
• Congruential complements of ground term rewrite systems
• Restricted ground tree transducers
• Constructing small tree grammars and small circuits for formulas
• scientific article; zbMATH DE number 4135419 (Why is no real title available?)
• scientific article; zbMATH DE number 139615 (Why is no real title available?)
• scientific article; zbMATH DE number 1136085 (Why is no real title available?)
• MINIMAL RECOGNIZERS AND SYNTACTIC MONOIDS OF DR TREE LANGUAGES

This page was built for publication: Minimal equational representations of recognizable tree languages

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1901719)