Inference of deterministic one-counter languages

Inference algorithms for the class of deterministic one-counter languages are presented that are based on enumeration methods. A method is described that enumerates DOCAs of a certain normal form in such a way that no two isomorphic DOCAs are generated. This is done by the generation of certain partitions on sets of so-called computation traces.     

The LBA-problem and the deterministic tape complexity of two-way one-counter languages over a one-letter alphabet

Summary It is shown, that NTAPE(n) is equal to TAPE(n) if and only if every language L⊂⊣{1}^*⊢ which is acceptable by a nondeterministic two-way one-counter automaton whose counter length is bounded by the length of its input is contained in TAPE(log n).     

Palindrome words and reverse closed languages

A word which is equal to its mirror image is called a palindrome word. Any language consisting of palindrome words is called a palindrome language. In this paper we investigate properties of palindrome words and languages. We show that there is no dense regular language consisting of palindrome words. A language contains all the mirror images of its elements is called a reverse closed language. Clearly, every palindrome language is reverse closed. We show that whether a given regular or context-free language is reverse closed is decidable. We study certain properties concerning reverse closed finite maximal prefix codes in this paper. Properties of languages that commute with reverse closed languages are investigated too.     

LTL is closed under topological closure

We constructively prove that for every LTL formula φ, the smallest safety property containing the property expressed by φ is also expressible in LTL. It immediately follows that LTL admits the safety-liveness decomposition: any property expressed by an LTL formula is equivalent to the intersection of a safety property and a liveness property, both of them expressible in LTL. Our proof is based on constructing a minimal deterministic counter-free Büchi automaton that recognizes the smallest safety property containing the property expressed by φ.     

A family of languages for architecture constraint specification

During software development, architecture decisions should be documented so that quality attributes guaranteed by these decisions and required in the software specification could be persisted. An important part of these architectural decisions is often formalized using constraint languages which differ from one stage to another in the development process. In this paper, we present a family of architectural constraint languages, called ACL. Each member of this family, called a profile, can be used to formalize architectural decisions at a given stage of the development process. An ACL profile is composed of a core constraint language, which is shared with the other profiles, and a MOF architecture metamodel. In addition to this family of languages, this paper introduces a transformation-based interpretation method of profiles and its associated tool.     

The finiteness of synchronous,tabled picture languages is decidable

In the present paper, synchronous, tabled chain code picture systems based on Lindenmayer systems (sT0L system) are studied with respect to the finiteness of their picture languages. The finiteness is proved to be decidable. Additionally, a method is given for deciding whether or not an sT0L system generates a finite picture language.     

The equivalence of deterministic gsm replications onQ-rational languages is decidable

It is shown that two deterministic gsm replications ₁ and ₂ are equivalent on the supportL of aQ-rational formal power series if and only if ₁ (w) = ₂ (w) for allw inL such that the length ofw does not exceed a certain bound which depends only on the numbers of states in the deterministic gsm's involved and on the size of the matrix system acceptingL. Application of this result to the deterministic gsm equivalence problem improves known bounds. Finally, sufficient conditions for an arbitrary family of languages to have a decidable deterministic gsm replication equivalence problem are presented.     

Fuzzy reasoning model under quotient space structure

In this paper, we present a theoretical framework of fuzzy reasoning model under quotient space structure. It consists of (1) introducing quotient space structure into fuzzy sets, i.e., constructing fuzzy set representations of different grain-size spaces and their relationships; (2) introducing the concept of fuzzy sets into quotient space theory, i.e., introducing fuzzy equivalence relation and discussing its corresponding reasoning in different grain-size spaces; and (3) discussing the relationship and transformation among different granular computing methodologies. The framework proposed is aimed to combine two powerful abilities in order to enhance the efficiency of fuzzy reasoning: one is the ability of computing with words based on fuzzy set methodology, the other is the ability of hierarchical problem solving based on quotient space approach.     

The equivalence problem for two dpda's,one of which is a finite-turn or one-counter machine

For some non-real-time subclasses $\text{C}$ of deterministic pushdown automata (dpda), we give a general scheme to extend a decision procedure of the equivalence to that for two dpda's, one of which is in $\text{C}$. Using this scheme, we prove that the equivalence problem is decidable for two dpda's, one of which is a finite-turn or one-counter machine.     

Prefix-primitive annihilators of languages under some operations

This paper studies some properties of prefix-primitive annihilators of languages under the catenation, shuffle product and bi-catenation operations. We prove that for every finite language L under the catenation operation, the left prefix-primitive annihilator of L is not equal to the right prefix-primitive annihilator of L, the left prefix-primitive annihilator of languages is not regular for any finite language, and the left prefix-primitive annihilator of any thin languages is not empty. Moreover, we also characterize the prefix-primitive annihilators of non-empty language under the shuffle product and bi-catenation operations over the alphabet with two letters.     

Implementation of MAYaK family languages for macropiplined multiprocessor computing systems

We describe the main implementation solutions for the MAYaK family of parallel programming languages, as determined by their distinctive features compared to sequential programming languages. These solutions have been implemented in the MAYaK parallel programming system for the ES 1766 multiprocessor computing system.Translated from Kibernetika, No. 3, pp. 29–34, 55, May–June, 1989.     

The equality of EOL languages and codings of ol languages

It is proved that a language is a coding (a letter-to-letter homomorphism) of a OL language, if, and only if, it is an EOL language.     

On a family of acceptors for some classes of developmental languages

A machine model, which consists essentially of a finite state control and an array of counters with first-in-last-out access, is formulated and it is proved that, under certain restrictions, the class of languages accepted is identical to the class of developmental languages without interactions.