Acta Informatica
Công bố khoa học tiêu biểu
* Dữ liệu chỉ mang tính chất tham khảo
Sắp xếp:
Space efficient algorithms for some graph theoretical problems
Acta Informatica - Tập 17 - Trang 411-423 - 1982
We present space-efficient-O(log2
n)-deterministic algorithms for some graph theoretical problems such as planarity testing, producing a plane embedding, finding minimum cost spanning trees, obtaining the connected, biconnected and triconnected components of a graph. Previous planarity algorithms used Ω(n) space. Several algorithms are based on a space-efficient matrix inversion method. The same b......
On the synchronization in parallel communicating grammar systems
Acta Informatica - Tập 30 - Trang 351-367 - 1993
We investigate the power of various types of synchronization in parallel communicating grammar systems. Systems without a universal clock (a pumping lemma is given for this case) proves in general to be weaker than the synchronized systems. Further synchronizing restrictions are introduced (added to the basic synchronization by a universal clock and their effect on the generative capacity of gramm......
Eigenschaften der von linearen Automaten erkennbaren Worte
Acta Informatica - Tập 3 - Trang 365-383 - 1974
The paper investigates the set of words accepted by a linear sequential machine M and the algebraic structure of this set. If M is nonsingular a strong relationship exists between this set and the transition group of the accepting automaton. Thus the algebraic structure of this group is used to describe some properties of the set of accepted words. If M is nilpotent, in addition, an algorithm is g......
Phân tích LL song song Dịch bởi AI
Acta Informatica - Tập 44 - Trang 1-21 - 2006
Một thuật toán phân tích LL song song có tính quyết định được trình bày. Thuật toán này dựa trên một sự chuyển đổi từ vấn đề phân tích thành giảm song song. Đầu tiên, một phiên bản không quyết định của bộ phân tích LL song song được giới thiệu. Sau đó, nó được chuyển đổi thành phiên bản có tính quyết định - bộ phân tích LLP. Bộ phân tích LLP(q,k) có tính quyết định sử dụng hai loại thông tin để ch......
#thuật toán phân tích LL #phân tích song song #ngữ pháp LLP #giảm song song #kiến trúc song song
Relating confluence, innermost-confluence and outermost-confluence properties of term rewriting systems
Acta Informatica - Tập 33 - Trang 595-606 - 1996
Innermost-confluence is important in giving call-by-value and denotational semantics and outermost-confluence is important in giving call-by-need and lazy semantics of programs. In this paper, we give a few sets of sufficient conditions under which the properties of confluence, innermost-confluence and outermost-confluence coincide. Confluence and innermost-confluence coincide for weakly innermost......
Cooperative distributed dynamic load balancing
Acta Informatica - Tập 25 - Trang 663-676 - 1988
This paper explores and applies the concept of cooperation to the load balancing problem in a computer network. We discuss an analytical model and propose a scheme which can be classified as distributed, dynamic, and stochastic. In the case of a homogeneous network, we guarantee that the load is balanced and no communication cost or information exchange is necessary.
A unified approach to the generation and the acception of formal languages
Acta Informatica - - 1978
The duality of generation and acception of the Chomsky classes of languages is emphasized by considering the corresponding acceptors as Semi-Thue-Systems instead of unnatural “machines”. It is shown as one main result that lba's, pda's and fsa's are characterized by imposing extremely simple and natural length conditions on the productions of the accepting Semi-Thue-System. As a second result, the......
Net-based control versus rational control The relation between ITNC vector languages and rational relations
Acta Informatica - Tập 34 - Trang 23-57 - 1997
An Individual Token Net Controller (or ITNC) is a particular type of state-machine decomposable Petri net that can be used as a synchronization mechanism in concurrent systems consisting of a fixed number of sequential subsystems. In this paper the family of ITNC vector languages is compared to the well-known family of rational relations. On the one hand it is proved that the family of rational r......
Tổng số: 1,156
- 1
- 2
- 3
- 4
- 5
- 6
- 10