<script type="text/javascript">
<!--
document.write('<div id="oa_widget"></div>');
document.write('<script type="text/javascript" src="https://www.openaire.eu/index.php?option=com_openaire&view=widget&format=raw&projectId=undefined&type=result"></script>');
-->
</script>

COPY SCRIPT

For further information contact us at helpdesk@openaire.eu

First-order properties of trees, star-free expressions, and aperiodicity

Name: First-order properties of trees, star-free expressions, and aperiodicity
Creator: Uschi Heuter
Keywords: 4. Education, Formal languages and automata, tree languages, first-order definability, 15. Life on land, Automata and formal grammars in connection with logical questions, 16. Peace & justice, tree automata

descriptionPublicationkeyboard_double_arrow_right Article , Part of book or chapter of book 01 Jan 1991Publisher:EDP SciencesJournal:RAIRO - Theoretical Informatics and Applications, volume 25, pages 125-145 (issn: 0988-3754, eissn: 1290-385X,

Authors: Uschi Heuter;

doi: 10.1051/ita/1991250201251 , 10.1007/bfb0035840

First-order properties of trees, star-free expressions, and aperiodicity

- Summary
- Subjects
- Metrics

Abstract

It was shown by \textit{W. Thomas} [Trees in algebra and programming, 9th Coll., Bordeaux, France, 31-49 (1984; Zbl 0557.68051)] that for tree languages the notions of first-order definability, aperiodicity and star- freeness are not equivalent as they are in the case of regular word languages. He also gave some relationships between the corresponding families of tree languages. The picture of the situation is complemented by proving that the first-order definable tree languages form a proper subfamily of the aperiodic regular tree languages, and by showing how the first-order definable tree languages can be obtained as a subfamily of the star-free tree languages. Methods based on Ehrenfeucht-Fraissé games are used for both results.

Related Organizations

RWTH Aachen University
Germany

Keywords

Formal languages and automata, tree languages, first-order definability, Automata and formal grammars in connection with logical questions, tree automata

Impact byBIP!

	citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	26
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Average
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Top 10%
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Average