On some Basic Properties of the Kolmogorov Complexity
On some classes of tree automata and tree languages.
On some closure properties of generable languages
On some context free languages that are not deterministic ETOL languages
On some elementary properties of uniform automata
On some factorization problems.
On some machine sequencing problems (II)
On some packing problem related to dynamic storage allocation
On star height hierarchies of context-free languages
On State Reduction In Deterministic Finite Transducers And Some Properties Of Deterministic Regular Translations
On strong homomorphisms of finitely semigenerated languages
On subdirectly irreducible automata
On subgraphs without large components
We consider, for a positive integer , induced subgraphs in which each component has order at most . Such a subgraph is said to be -divided. We show that finding large induced subgraphs with this property is NP-complete. We also consider a related graph-coloring problem: how many colors are required in a vertex coloring in which each color class induces a -divided subgraph. We show that the problem of determining whether some given number of colors suffice is NP-complete, even for -coloring...
On subword complexities of homomorphic images of languages
On synchronized sequences and their separators
We introduce the notion of a -synchronized sequence, where is an integer larger than 1. Roughly speaking, a sequence of natural numbers is said to be -synchronized if its graph is represented, in base , by a right synchronized rational relation. This is an intermediate notion between -automatic and -regular sequences. Indeed, we show that the class of -automatic sequences is equal to the class of bounded -synchronized sequences and that the class of -synchronized sequences is strictly...
On synchronized sequences and their separators
We introduce the notion of a k-synchronized sequence, where k is an integer larger than 1. Roughly speaking, a sequence of natural numbers is said to be k-synchronized if its graph is represented, in base k, by a right synchronized rational relation. This is an intermediate notion between k-automatic and k-regular sequences. Indeed, we show that the class of k-automatic sequences is equal to the class of bounded k-synchronized sequences and that the class of k-synchronized sequences is...
On temporal program verification rules
On the Algebraic Complexity of Sets of Functions
On the analysis of Petri nets and their synthesis from process languages
Processes in Place/Transition (P/T) nets are defined inductively by a peculiar numbering of place occurrences. Along with an associative sequential composition called catenation and a neutral process, a monoid of processes is obtained. The power algebra of this monoid contains all process languages with appropriate operations on them. Hence the problems of analysis and synthesis, analogous to those in the formal languages and automata theory, arise. Here, the analysis problem is: for a given P/T...
On the Analysis of Petri Nets and their Synthesis from Process Languages
Processes in Place/Transition (P/T) nets are defined inductively by a peculiar numbering of place occurrences. Along with an associative sequential composition called catenation and a neutral process, a monoid of processes is obtained. The power algebra of this monoid contains all process languages with appropriate operations on them. Hence the problems of analysis and synthesis, analogous to those in the formal languages and automata theory, arise. Here, the analysis problem is: for a given P/T...