Pushdown automata on arrays

This paper deals with some properties of pushdown automata (PDAs) on two-dimensional arrays. In particular, it is shown that there exists a deterministic array-bounded PDA which can traverse any simply connected pattern and halt when the traversal is complete.     

Some results in tree automata

Summary The following three results concerning tree automata are presented in this paper. (1) Rounds has presented the following open problem: For every recognizable setR, can we construct a deterministic finite-state transformation recognizingR? We show that this is not possible, in fact, even for a local set. However, the following is true: For every recognizable setR there is an inverse projectionR effectively obtained such thatR is recognized by a deterministic finite-state transformation. (2) Martin and Vere in their study of tree automata leave open the question of whether Generalized Syntax Directed Transductions (GSDT's) are closed under Arden's transformation or Greibach's transformation, and conjecture that they are not. We prove that this conjecture is true. It is also shown that GSDT's are not closed under transformation to LR(k) grammars. (3) Peters and Ritchie have shown that if, in a grammar where the generative rules are context-free, there are recognition rules which are context-sensitive, the language recognized is still context-free. A tree-automata-oriented proof is given by Rounds. We show that a similar result holds also for right linear grammars, i.e., if the generative rules are right linear, then using context-sensitive rules for recognition, one can still recognize only regular languages. Some other related results concerning context-sensitive extensions of subclasses of context-free languages are also presented.This work was partially supported by NSF Grant GJ27, U.S. Army Research Office, Durham (DA-31-124 ARO(D)-98), and NSF Grant GS-2509.A present on leave at The Institute for Advanced Study, Princeton, N.J.     

Rigid tree automata and applications

We introduce the class of rigid tree automata (RTA), an extension of standard bottom-up automata on ranked trees with distinguished states called rigid. Rigid states define a restriction on the computation of RTA on trees: RTA can test for equality in subtrees reaching the same rigid state. RTA are able to perform local and global tests of equality between subtrees, non-linear tree pattern matching, and some inequality and disequality tests as well. Properties like determinism, pumping lemma, Boolean closure, and several decision problems are studied in detail. In particular, the emptiness problem is shown decidable in linear time for RTA whereas membership of a given tree to the language of a given RTA is NP-complete. Our main result is the decidability of whether a given tree belongs to the rewrite closure of an RTA language under a restricted family of term rewriting systems, whereas this closure is not an RTA language. This result, one of the first on rewrite closure of languages of tree automata with constraints, is enabling the extension of model checking procedures based on finite tree automata techniques, in particular for the verification of communicating processes with several local non-rewritable memories, like security protocols. Finally, a comparison of RTA with several classes of tree automata with local and global equality tests, with dag automata and Horn clause formalisms is also provided.     

Weighted tree automata and weighted logics

We define a weighted monadic second order logic for trees where the weights are taken from a commutative semiring. We prove that a restricted version of this logic characterizes the class of formal tree series which are accepted by weighted bottom-up finite state tree automata. The restriction on the logic can be dropped if additionally the semiring is locally finite. This generalizes corresponding classical results of Thatcher, Wright, and Doner for tree languages and it extends recent results of Droste and Gastin [Weighted automata and weighted logics, in: Automata, Languages and Programming—32nd International Colloquium, ICALP 2005, Lisbon, Portugal, 2005, Proceedings, Lecture Notes in Computer Science, Vol. 3580, Springer, Berlin, 2005, pp. 513–525, full version in Theoretical Computer Science, to appear.] from formal power series on words to formal tree series.     

Fuzzy tree automata and syntactic pattern recognition

An approach of representing patterns by trees and processing these trees by fuzzy tree automata is described. Fuzzy tree automata are defined and investigated. The results include that the class of fuzzy root-to-frontier recognizable ?-trees is closed under intersection, union, and complementation. Thus, the class of fuzzy root-to-frontier recognizable ?-trees forms a Boolean algebra. Fuzzy tree automata are applied to processing fuzzy tree representation of patterns based on syntactic pattern recognition. The grade of acceptance is defined and investigated. Quantitative measures of ``approximate isosceles triangle,' ``approximate elongated isosceles triangle,' ``approximate rectangle,' and ``approximate cross' are defined and used in the illustrative examples of this approach. By using these quantitative measures, a house, a house with high roof, and a church are also presented as illustrative examples. In addition, three fuzzy tree automata are constructed which have the capability of processing the fuzzy tree representations of ``fuzzy houses,' ``houses with high roofs,' and ``fuzzy churches,' respectively. The results may have useful applications in pattern recognition, image processing, artificial intelligence, pattern database design and processing, image science, and pictorial information systems.     

A note on partially ordered tree automata

A recent paper by Bouajjani, Muscholl and Touili shows that the class of languages accepted by partially ordered word automata (or equivalently accepted by Σ₂-formulae) is closed under semi-commutation and it suggested the following open question: can we extend this result to tree languages? This problem can be addressed by proving (1) that the class of tree regular languages accepted by Σ₂ formulae is strictly included in the class of languages accepted by partially ordered automata, and (2) that Bouajjani and the others results cannot be extended to tree.     

Constructing infinite models represented by tree automata

We propose a method to use finite model builders in order to construct infinite models of first-order formulae. The constructed models are Herbrand interpretations, in which the interpretation of the predicate symbols is specified by tree tuple automata (Comon et al. 1997). Our approach is based on formula transformation: a formula ϕ is transformed into a formula Δ(ϕ) s.t. ϕ has a model representable by a term tuple automaton iff Δ(ϕ) has a finite model. This paper is an extended version of Peltier (2008).     

采用树自动机推理技术的信息抽取方法

提出了一种利用改进的k-contextual树自动机推理算法的信息抽取技术。其核心思想是将结构化（半结构化）文档转换成树,然后利用一种改进的k-contextual树（KLH树）来构造出能够接受样本的无秩树自动机,依据该自动机接收和拒绝状态来确定是否抽取网页信息。该方法充分利用了网页文档的树状结构,依托树自动机将传统的以单一结构途径的信息抽取方法与文法推理原则相结合,得到信息抽取规则。实验证明,该方法与同类抽取方法相比,样本学习时间以及抽取所需时间上均有所缩短。     

Parametric random generation of deterministic tree automata

Uniform random generators deliver a simple empirical means to estimate the average complexity of an algorithm. We present a general rejection algorithm that generates sequential letter-to-letter transducers up to isomorphism. We also propose an original parametric random generation algorithm to produce sequential letter-to-letter transducers with a fixed number of transitions. We tailor this general scheme to randomly generate deterministic tree walking automata and deterministic top–down tree automata. We apply our implementation of the generator to the estimation of the average complexity of a deterministic tree walking automata to nondeterministic top–down tree automata construction we also implemented.     

基于无秩树自动机的信息抽取技术研究

针对目前基于网页结构的信息抽取方法的缺陷,提出了一种基于无秩树自动机的信息抽取技术,其核心思想是通过将结构化(半结构化)文档转换成无秩树,然后利用(k,l)-contextual树构造样本自动机,依据树自动机接收和拒绝状态来对网页进行数据的抽取.该方法充分利用结构,依托树自动机将传统的以单一结构途径的信息抽取方法与文法推理原则相结合,得到信息抽取规则.实验结果表明,该方法与同类抽取方法相比在准确率、召回率以及抽取所需时间上均有所提高.     

Tree pattern mining with tree automata constraints

Most work on pattern mining focuses on simple data structures such as itemsets and sequences of itemsets. However, a lot of recent applications dealing with complex data like chemical compounds, protein structures, XML and Web log databases and social networks, require much more sophisticated data structures such as trees and graphs. In these contexts, interesting patterns involve not only frequent object values (labels) appearing in the graphs (or trees) but also frequent specific topologies found in these structures. Recently, several techniques for tree and graph mining have been proposed in the literature. In this paper, we focus on constraint-based tree pattern mining. We propose to use tree automata as a mechanism to specify user constraints over tree patterns. We present the algorithm CoBMiner which allows user constraints specified by a tree automata to be incorporated in the mining process. An extensive set of experiments executed over synthetic and real data (XML documents and Web usage logs) allows us to conclude that incorporating constraints during the mining process is far more effective than filtering the interesting patterns after the mining process.     

下推自动机的状态转换图与下推自动机的化简

参照有限状态自动机图形表示方式的思想方法,研究了标准下推自动机的图形表示——PAD 状态转换图,证明了下推自动机与标准下推自动机的等价性。给出了对标准下推自动机进行化简的原则,并给出了化简算法,实现了下推自动机的化简。     

Complexity of weak acceptance conditions in tree automata

Weak acceptance conditions for automata on infinite words or trees are defined in terms of the set of states that appear in the run. This is in contrast with, more usual, strong conditions that are defined in terms of states appearing infinitely often on the run. Weak conditions appear in the context of model-checking and translations of logical formalisms to automata. We study the complexity of the emptiness problem for tree automata with weak conditions. We also study the translations between automata with weak and strong conditions.     

基于树自动机的XML过滤技术

为了提高XML数据流的查询匹配效率,基于XML过滤技术研究提出了一种基于树自动机的XML过滤技术XTAFilter.该技术利用hash表来存储谓词,并对多个查询表达式XPath通过共享路径构建树自动机,减少了匹配的时间,提高了查询匹配的效率,同时降低系统运行时的活动状态.搭建仿真平台对技术进行验证,仿真实验结果表明,XTAFilter 技术能有效地提高XML数据流的匹配效率,提高了系统的实用性.     

Backward and forward bisimulation minimization of tree automata

We improve on an existing [P.A. Abdulla, J. Högberg, L. Kaati, Bisimulation minimization of tree automata, International Journal of Foundations of Computer Science 18(4) (2007) 699–713] bisimulation minimization algorithm for finite-state tree automata by introducing backward and forward bisimulation and developing minimization algorithms for them. Minimization via forward bisimulation is also effective on deterministic tree automata, faster than the previous algorithm, and yields the minimal equivalent deterministic tree automaton. Minimization via backward bisimulation generalizes the previous algorithm and can yield smaller automata but is just as fast. We demonstrate implementations of these algorithms on a typical task in natural language processing.     

On regular tree languages and deterministic pushdown automata

The theory of formal string languages and of formal tree languages are both important parts of the theory of formal languages. Regular tree languages are recognized by finite tree automata. Trees in their postfix notation can be seen as strings. This paper presents a simple transformation from any given (bottom-up) finite tree automaton recognizing a regular tree language to a deterministic pushdown automaton accepting the same tree language in postfix notation. The resulting deterministic pushdown automaton can be implemented easily by an existing parser generator because it is constructed for an LR(0) grammar, and its size directly corresponds to the size of the deterministic finite tree automaton. The class of regular tree languages in postfix notation is a proper subclass of deterministic context-free string languages. Moreover, the class of tree languages which are in their postfix notation deterministic context-free string languages is a proper superclass of the class of regular tree languages.