Unique Decipherability in the Monoid of Languages: An Application of Rational Relations

We attack the problem of deciding whether a finite collection of finite languages is a code, that is, possesses the unique decipherability property in the monoid of finite languages. We investigate a few subcases where the theory of rational relations can be employed to solve the problem. The case of unary languages is one of them and as a consequence, we show how to decide for two given finite subsets of nonnegative integers, whether they are the nth root of a common set, for some n≥1. We also show that it is decidable whether a finite collection of finite languages is a Parikh code, in the sense that whenever two products of these sets are commutatively equivalent, so are the sequences defining these products. Finally, we consider a nonunary special case where all finite sets consist of words containing exactly one occurrence of the specific letter.     

Deterministic and nondeterministic flowchart interpretations

Programming languages are studied in the abstract. Algebraic theories supply the syntax for programming languages. Semantics is provided by coproduct preserving functors from the algebraic theory to some semantic category with finite coproducts. Deterministic programming languages are provided when the semantic domain is the category of pointed sets and point preserving functions. Nondeterministic programming languages occur when the semantic domain is the category of Abelian monoids. The class of all nondeterministic programming languages with a fixed syntax is shown to be a variety of algebras. All classes of deterministic programming languages that allow branching are shown to be nonvarietal. Other properties of classes of programming languages are studied using category theory.     

Characterizing TC<Superscript>0</Superscript> in Terms of Infinite Groups

We characterize the languages in TC⁰ = L(Maj[<,Bit]) and L(Maj[<]) as inverse morphic images of certain groups. Necessarily these are infinite, since nonregular sets are concerned. To limit the power of these infinite algebraic objects, we equip them with a finite type set and introduce the notion of a finitely typed (infinite) monoid. Following this approach we investigate type-respecting mappings and construct a new type of block product that more adequately deals with infinite monoids. We exhibit two classes of finitely typed groups which exactly characterize TC⁰ and L(Maj[<]) via inverse morphisms.     

Relations rationnelles infinitaires

In this paper, we build a theory of infinitary rational relations, which is an extension of the theory of finitary rational relations, i. e. sets ofK-vectors of finite words which are recognized by finite automata withK tapes, and at the same time an extension of the theory of infinitary rational languages, i.e., sets of finite and infinite words which are recognized by finite automata (the condition of recognizability of an infinite word is that its reading by the automaton must go through a state, wich belongs to a designated subset, infinitly time). Our main result is a theorem similar to the Kleene theorem about rational languages of finite words: it is proved that the family of relations recognized by finite automata withK tapes is the family of relations obtained from the finite finitary relations with a finite sequence of operations of: union, product, finite star, and infinite star. Then the closure properties of this family of relations, are studied.      

Fundamental properties of infinite trees

Infinite trees naturally arise in the formalization and the study of the semantics of programming languages. This paper investigates some of their combinatorial and algebraic properties that are especially relevant to semantics.This paper is concerned in particular with regular and algebraic infinite trees, not with regular or algebraic sets of infinite trees. For this reason most of the properties stated in this work become trivial when restricted either to finite trees or to infinite words.It presents a synthesis of various aspects of infinite trees, investigated by different authors in different contexts and hopes to be a unifying step towards a theory of infinite trees that could take place near the theory of formal languages and the combinatorics of thefree monoid.     

Schützenberger and Eilenberg theorems for words on linear orderings

This paper contains extensions to words on countable scattered linear orderings of two well-known results of characterization of languages of finite words. We first extend a theorem of Schützenberger establishing that the star-free sets of finite words are exactly the languages recognized by finite aperiodic semigroups. This gives an algebraic characterization of star-free sets of words over countable scattered linear orderings. Contrarily to the case of finite words, first-order definable languages are strictly included into the star-free languages when countable scattered linear orderings are considered. Second, we extend the variety theorem of Eilenberg for finite words: there is a one-to-one correspondence between varieties of languages of words on countable scattered linear orderings and pseudo-varieties of algebras. The star-free sets are an example of such a variety of languages.     

Highly Constrained Unification Grammars

Unification grammars are widely accepted as an expressive means for describing the structure of natural languages. In general, the recognition problem is undecidable for unification grammars. Even with restricted variants of the formalism, off-line parsable grammars, the problem is computationally hard. We present two natural constraints on unification grammars which limit their expressivity and allow for efficient processing. We first show that non-reentrant unification grammars generate exactly the class of context-free languages. We then relax the constraint and show that one-reentrant unification grammars generate exactly the class of mildly context-sensitive languages. We thus relate the commonly used and linguistically motivated formalism of unification grammars to more restricted, computationally tractable classes of languages.     

Topology on words

We investigate properties of topologies on sets of finite and infinite words over a finite alphabet. The guiding example is the topology generated by the prefix relation on the set of finite words, considered as a partial order. This partial order extends naturally to the set of infinite words; hence it generates a topology on the union of the sets of finite and infinite words. We consider several partial orders which have similar properties and identify general principles according to which the transition from finite to infinite words is natural. We provide a uniform topological framework for the set of finite and infinite words to handle limits in a general fashion.     

Constant-space quantum interactive proofs against multiple provers

We present upper and lower bounds of the computational complexity of the two-way communication model of multiple-prover quantum interactive proof systems whose verifiers are limited to measure-many two-way quantum finite automata. We prove that (i) the languages recognized by those multiple-prover systems running in expected polynomial time are exactly the ones in NEXP, the nondeterministic exponential-time complexity class, (ii) if we further require verifiers to be one-way quantum finite automata, then their associated proof systems recognize context-free languages but not beyond languages in NE, the nondeterministic linear exponential-time complexity class, and moreover, (iii) when no time bound is imposed, the proof systems become as powerful as Turing machines. The first two results answer affirmatively an open question, posed by Nishimura and Yamakami [J. Comput. System Sci. 75 (2009) 255–269], of whether multiple-prover quantum interactive proof systems are more powerful than single-prover ones. Our proofs are simple and intuitive, although they heavily rely on an earlier result on multiple-prover classical interactive proof systems of Feige and Shamir [J. Comput. System Sci. 44 (1992) 259–271].     

Synchronization of musical words

We study the synchronization of musical sequences by means of an operation defined on finite or infinite words called superimposition. This operation can formalize basic musical structures such as melodic canons and serial counterpoint. In the case of circular canons, we introduce the superimposition of infinite words, and we present an enumeration algorithm involving Lyndon words, which appear to be a useful tool for enumerating periodic musical structures. We also define the superimposition of finite words, the superimposition of languages, and the iterated superimposition of a language, which is applied to the study of basic aspects of serial music. This leads to the study of closure properties of rational languages of finite words under superimposition and iterated superimposition. The rationality of the transduction associated with the superimposition appears to be a powerful argument in the proof of these properties. Since the superimposition of finite words is the max operation of a sup-semilattice, the last section addresses the link between the rationality of a sup-semilattice operation and the rationality of the order relation associated with it.     

Fixed-Point Logics and Solitaire Games

The model-checking games associated with fixed-point logics are parity games, and it is currently not known whether the strategy problem for parity games can be solved in polynomial time. We study Solitaire-LFP, a fragment of least fixed-point logic, whose evaluation games are nested soltaire games. This means that on each strongly connected component of the game, only one player can make nontrivial moves. Winning sets of nested solitaire games can be computed efficiently. The model-checking problem for Solitaire-LFP is Pspace-complete in general and Ptime-complete for formulae of bounded width. On finite structures (but not on infinite ones), Solitaire-LFP is equivalent to transitive closure logic. We also consider the solitaire fragment of guarded fixed-point logics. Due to the restricted quantification pattern of these logics, the associated games are small and therefore admit more efficient model-checking algorithms.     

On string languages generated by sequential spiking neural P systems based on the number of spikes

Spiking neural P systems (SN P systems, for short) are a class of distributed parallel computing devices inspired from the way neurons communicate by means of spikes. In this work, we consider SN P systems with the following restriction: at each step the active neuron with the maximum (or minimum) number of spikes among the neurons that can spike will fire [if there is a tie for the maximum (or minimum) number of spikes stored in the active neurons, only one of the neurons containing the maximum (or minimum) is chosen non-deterministically]. We investigate the computational power of such sequential SN P systems that are used as language generators. We prove that recursively enumerable languages can be characterized as projections of inverse-morphic images of languages generated by such sequential SN P systems. The relationships of the languages generated by these sequential SN P systems with finite and regular languages are also investigated.     

An entity-relationship programming language

The syntax for an integrated E-R programming language is presented. The problems that arise when a query language is embedded in a general-purpose programming language are discussed. Other E-R languages are also discussed. The requirements for the language and a syntax for an E-R model in which entity sets are mutually disjoint and each entity type has a unique, perhaps multiattribute, key are presented. The syntax for a more limited model restricted to binary relationships between entity types and without attributes is presented. Some implementation considerations are discussed     

Strategical languages of infinite words

We deal in this paper with strategical languages of infinite words, that is those generated by a nondeterministic strategy in the sense of game theory. We first show the existence of a minimal strategy for such languages, for which we give an explicit expression. Then we characterize the family of strategical languages as that of closed ones, in the topological space of infinite words. Finally, we give a definition of a Nash equilibrium for such languages, that we illustrate with a famous example.     

Multiple equality sets and post machines

Equality sets of finite sets of homomorphisms are studied as part of formal language theory. Some particular equality sets, called Merge_k(k-COPY), are investigated. These languages are combinatorially difficult, and are full semiAFL generators of the recursively enumerable sets, and are semiAFL generators of the class MULTI-RESET, provided k ? 3. To accomplish this characterization, equality sets are related to multihead and multitape Post machines operating in real time. A Post machine has a one-way input tape and Post tapes as storage tapes, which in the multihead version are scanned from left to right by a write head and several read heads. By simulating Post machines by multiple reset machines, and vice versa, several new characterisations of the class MULTI-RESET are obtained, and it is shown that for multihead and multitape Post machines linear time is no more powerful than real time, and two Post tapes or, alternatively, three heads on one Post tape are as powerful as any finite number of heads or tapes. Finally, some complexity bounds for equality sets and Post machines are discussed.     

Maximal infinite-valued constraint languages

We systematically investigate the computational complexity of constraint satisfaction problems for constraint languages over an infinite domain. In particular, we study a generalization of the well-established notion of maximal constraint languages   from finite to infinite domains. If the constraint language can be defined with an ω$\omega$-categorical structure, then maximal constraint languages are in one-to-one correspondence to minimal oligomorphic clones. Based on this correspondence, we derive general tractability and hardness criteria for the corresponding constraint satisfaction problems.     

Variants of codes and indecomposable languages

We continue the investigation of representing a language as a catenation of languages, each of which cannot be further decomposed in a nontrivial fashion. We study such prime decompositions, both finite and infinite ones. The notion of a length code, an extension of the notion of a code leads to general results concerning decompositions of star languages. Special emphasis is on the decomposition of regular languages. Also some open problems are mentioned.     

A theory of ultimately periodic languages and automata with an application to time granularity

In this paper, we develop a theory of regular ω-languages that consist of ultimately periodic words only and we provide it with an automaton-based characterization. The resulting class of automata, called ultimately periodic automata (UPA), is a subclass of the class of Büchi automata and inherits some properties of automata over finite words (NFA). Taking advantage of the similarities among UPA, Büchi automata, and NFA, we devise efficient solutions to a number of basic problems for UPA, such as the inclusion, the equivalence, and the size optimization problems. The original motivation for developing a theory of ultimately periodic languages and automata was to represent and to reason about sets of time granularities in knowledge-based and database systems. In the last part of the paper, we show that UPA actually allow one to represent (possibly infinite) sets of granularities, instead of single ones, in a compact and suitable to algorithmic manipulation way. In particular, we describe an application of UPA to a concrete time granularity scenario taken from clinical medicine.     

RELATIVE UNCERTAINTY AND EVIDENCE SETS: A CONSTRUCTIVIST FRAMEWORK

Abstract

Several measures of uncertainty, in its various forms of nonspecificity, conflict, and fuzziness, valid both in finite and infinite domains are investigated. It is argued that dimensionless measures, relating uncertainty situations to the information content of their respective universal sets, can capture uncertainty efficiently both in finite and infinite domains. These measures are also considered more intuitive. To establish them, a more general approach to uncertainly measures is developed. After this, the utilization of these measures is exemplified in the measurement of the uncertainty content of evidence sets. These interval-based set structures, defined through evidence theory, are shown to possess ideal characteristics for the modeling of human cognitive categorization processes, within a constructivist framework.     

Adherences of languages

This paper studies context-free sets of finite and infinite words. In particular, it gives a natural way of associating to a language a set of infinite words. It then becomes possible to begin a study of families of sets of infinite words rather similar to the classical studies of families of languages.