Characterizations for the regular prefix codes and related families

Intrinsic characterizations by means of analogues of regular expressions are given for six families of regular languages related to the prefix codes, namely their reversals and their closure under union, the right and left ideals, and their complements. First, a characterization for the regular prefix codes is obtained, which is then used to characterize the other families. Characterizations by finite automata are also presented.This research has been sponsored in part by FINEP, CNPq and Canadian NRC.     

Codeterministic automata on infinite words

We prove that any recognizable set of infinite words is the infinite behaviour of some finite codeterministic automaton.     

Sorted dependency insertion grammars

An enhanced generative formalism is proposed based on the combination of two features: contextual derivation (as in Marcus contextual grammars) and sorted dependency structures (as in dependency grammars). The model is related to a variant of restarting automaton with rewriting and deletion. Preliminary results on the generative power as well as closure and decidability properties of the new model are presented.     

Remove Irrelevant Atomic Formulas for Timed Automaton Model Checking

Most of the timed automata reachability analysis algorithms in the literature explore the state spaces by enumeration of symbolic states, which use time constraints to represent a set of concrete states. A time constraint is a conjunction of atomic formulas which bound the differences of clock values. In this paper, it is shown that some atomic formulas of symbolic states generated by the algorithms can be removed to improve the model checking time- and space-efficiency. Such atomic formulas are called as irrelevant atomic formulas. A method is also presented to detect irrelevant formulas based on the test-reset information about clock variables. An optimized model-checking algorithm is designed based on these techniques. The case studies show that the techniques presented in this paper significantly improve the space- and time-efficiency of reachability analysis.     

Algebraic properties of LA-languages

In this study, we introduce the concepts of L-valued regular substitution (LA-substitution), deterministic L-valued regular substitution (DLA-substitution), L-valued fuzzy homomorphism and its inverse images, homomorphism and its inverse images for a lattice-ordered monoid L. We also study the properties of LA-languages and DLA-languages under the above-mentioned algebraic operations. The algebraic characterization of the L-valued regular language is given.     

LTL over integer periodicity constraints

Periodicity constraints are used in many logical formalisms, in fragments of Presburger LTL, in calendar logics, and in logics for access control, to quote a few examples. In the paper, we introduce the logic PLTL^mod, an extension of Linear-Time Temporal Logic LTL with past-time operators whose atomic formulae are defined from a first-order constraint language dealing with periodicity. Although the underlying constraint language is a fragment of Presburger arithmetic shown to admit a PSPACE-complete satisfiability problem, we establish that PLTL^mod model-checking and satisfiability problems remain in PSPACE as plain LTL (full Presburger LTL is known to be highly undecidable). This is particularly interesting for dealing with periodicity constraints since the language of PLTL^mod has a language more concise than existing languages and the temporalization of our first-order language of periodicity constraints has the same worst case complexity as the underlying constraint language. Finally, we show examples of introduction the quantification in the logical language that provide to PLTL^mod, EXPSPACE-complete problems. As another application, we establish that the equivalence problem for extended single-string automata, known to express the equality of time granularities, is PSPACE-complete by designing a reduction from QBF and by using our results for PLTL^mod.     

基于电话网络的家用电器远程控制系统的实现

本文给出了基于电话网络的家用电器远程控制系统的总体框图。分析了振铃检测、DTMF解码和实时时钟DS12887的原理。对ISD2590的信息检索模式提出了M1和M6相结合的使用方法,并设计出了硬件电路。经过系统运行,验证了该系统的有效性和实用性。     

入侵检测系统中模式匹配自动机的构造研究

本文提出了一种新的用于构造入侵检测模式匹配自动机的方法。该方法从构造判定单个模式的NFA自动机入手,通过集成单个的NFA而得到全集的NFA,并将全集NFA转换为与之等价的DFA并化简,从而可得到全集的确定型模式匹配有限自动机。由于该方法可以完全自动完成,从而可以方便地为入侵检测系统构造模式匹配自动机。     

一维水锤问题的格子气自动机

给出一维关阀断流水锤问题的时间、空间、流体完全离散的格子气自动机。