On some Interconnections Between Combinatorial Optimization and Extremal Graph Theory
On some machine sequencing problems (II)
On some packing problem related to dynamic storage allocation
On some problems related to palindrome closure
In this paper, we solve some open problems related to (pseudo)palindrome closure operators and to the infinite words generated by their iteration, that is, standard episturmian and pseudostandard words. We show that if ϑ is an involutory antimorphism of A*, then the right and left ϑ-palindromic closures of any factor of a ϑ-standard word are also factors of some ϑ-standard word. We also introduce the class of pseudostandard words with “seed”, obtained by iterated pseudopalindrome closure starting...
On some properties of doubly-periodic words
We study the functional equation: where and are words over an alphabet . In particular we prove a «structure result» for the inner factors : for suitably chosen words one has: ,
On some properties of grounding nonuniform sets of modal conjunctions
A language grounding problem is considered for nonuniform sets of modal conjunctions consisting of conjunctions extended with more than one modal operator of knowledge, belief or possibility. The grounding is considered in the context of semiotic triangles built from language symbols, communicative cognitive agents and external objects. The communicative cognitive agents are assumed to be able to observe external worlds and store the results of observations in internal knowledge bases. It is assumed...
On some properties of -planes of type-2 fuzzy sets
Some basic properties of -planes of type-2 fuzzy sets are investigated and discussed in connection with the similar properties of -cuts of type-1 fuzzy sets. It is known, that standard intersection and standard union of type-1 fuzzy sets (it means intersection and union under minimum t-norm and maximum t-conorm, respectively) are the only cutworthy operations for type-1 fuzzy sets. Recently, a similar property was declared to be true also for -planes of type-2 fuzzy sets in a few papers. Thus,...
On stabbing triangles by lines in 3-space
We give an example of a set of points in such that, for any partition of into triples, there exists a line stabbing of the triangles determined by the triples.
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 substitution invariant Sturmian words: an application of Rauzy fractals
Sturmian words are infinite words that have exactly n+1 factors of length n for every positive integer n. A Sturmian word sα,p is also defined as a coding over a two-letter alphabet of the orbit of point ρ under the action of the irrational rotation Rα : x → x + α (mod 1). A substitution fixes a Sturmian word if and only if it is invertible. The main object of the present paper is to investigate Rauzy fractals associated with two-letter invertible substitutions. As an application, we give...
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 table-driven syntax-checking within on ALGOL compiler
On temporal program verification rules
On ternary square-free circular words.