Files in this item

FilesDescriptionFormat

application/pdf

application/pdfCombining Equat ... er AC and ACI Theories.pdf (463kB)
(no description provided)PDF

Description

Title:Combining Equational Tree Automata Over AC and ACI Theories
Author(s):Hendrix, Joe; Ohsaki, Hitoshi
Subject(s):computer science
Abstract:In this paper, we study combining equational tree automata in two different senses: (1) whether decidability results about equational tree automata over disjoint theories imply similar decidability results in the combined theory; (2) checking emptiness of a language obtained from the Boolean combination of regular equational tree languages. We present a negative result for the first problem. Specifically, we show that the intersection-emptiness problem for tree automata over a theory containing at least one AC symbol, one ACI symbol, and 4 constants is undecidable despite being decidable if either the AC or ACI symbol is removed. Our result shows that decidability of intersection-emptiness is a non-modular property even for the union of disjoint theories. Our second contribution is to show a decidability result which implies the decidability of two open problems: (1) If idempotence is treated as a rule f(x,x) -> x rather than an equation f(x,x) = x, is it decidable whether an AC tree automata accepts an idempotent normal form? (2) If E contains a single ACI symbol and arbitrary free symbols, is emptiness decidable for a Boolean combination of regular E-tree languages?
Issue Date:2008-02
Genre:Technical Report
Type:Text
URI:http://hdl.handle.net/2142/11428
Other Identifier(s):UIUCDCS-R-2008-2940
Rights Information:You are granted permission for the non-commercial reproduction, distribution, display, and performance of this technical report in any format, BUT this permission is only for a period of 45 (forty-five) days from the most recent time that you verified that this technical report is still available from the University of Illinois at Urbana-Champaign Computer Science Department under terms that include this permission. All other rights are reserved by the author(s).
Date Available in IDEALS:2009-04-22


This item appears in the following Collection(s)

Item Statistics