Search

A logic in a finite language is said to be finitely presentable if it is axiomatized by finitely many finite rules. It is proved that binary non-indexed products of logics that are both finitely presentable and finitely equivalential are essentially finitely presentable. This result does not extend to binary non-indexed products of arbitrary finitely presentable logics, as shown by a counterexample. Finitely presentable logics are then exploited to introduce finitely presentable Leibniz classes, and to draw a parallel between the Leibniz and the Maltsev hierarchies.

A compacted binary tree is a directed acyclic graph encoding a binary tree in which common subtrees are factored and shared, such that they are represented only once. We show that the number of compacted binary trees of size $n$ grows asymptotically like $$\Theta\left( n! \, 4^n e^{3a_1n^{1/3}} n^{3/4} \right),$$ where $a_1\approx-2.338$ is the largest root of the Airy function. Our method involves a new two parameter recurrence which yields an algorithm of quadratic arithmetic complexity. We use empirical methods to estimate the values of all terms defined by the recurrence, then we prove by induction that these estimates are sufficiently accurate for large $n$ to determine the asymptotic form. Our results also lead to new bounds on the number of minimal finite automata recognizing a finite language on a binary alphabet. As a consequence, these also exhibit a stretched exponential., Comment: 37 pages, 14 figures. Version accepted for publication

We consider the following practical question: given a finite algebra [Formula: see text] in a finite language, can we efficiently decide whether the variety generated by [Formula: see text] has a difference term? We answer this question (positively) in the idempotent case and then describe algorithms for constructing difference term operations.

This paper is motivated by a practical question: given a finite algebra A in a finite language, how can we best program a computer to decide whether the variety generated by A has a difference term, and how hard is it to find the difference term? To help address this question, we produce a simple Maltsev condition which characterizes difference terms in the class of locally finite varieties. We do the same for weak difference terms.

A fundamental task in natural language processing is the efficient representation of lexica. From a computational viewpoint, lexica need to be represented in a way directly supporting fast access to entries, and minimizing space requirements. A standard method is to represent lexica as minimal deterministic (classical) finite-state automata. To reach such a representation it is of course possible to first build the trie of the lexicon and then to minimize this automaton afterwards. However, in general the intermediate trie is much larger than the resulting minimal automaton. Hence a much better strategy is to use a specialized algorithm to directly compute the minimal deterministic automaton in an incremental way. In this chapter we describe such a procedure.

We show that the shuffle L ⊔ ⊔ F of a piecewise-testable language L and a finite language F is piecewise-testable. The proof relies on a classic but little-used automata-theoretic characterization of piecewise-testable languages. We also discuss some mild generalizations of the main result, and provide bounds on the piecewise complexity of L ⊔ ⊔ F .

International audience; We study the grammatical production complexity of finite languages w.r.t. (i) different interpretations of approximation, i.e., equivalence, cover, and scattered cover, and (ii) whether the underlying grammar generates a finite or infinite language. In case the generated language is infinite, the intersection with all words up to a certain length has to be considered in order to obtain the finite language under consideration. In this way, we obtain six different measures for regular, linear context-free, and context-free grammars. We compare these measures according to the taxonomy introduced in [J. Dassow, Gh. Păun: Regulated Rewriting in Formal Language Theory, 1989] with each other by fixing the grammar type and varying the complexity measure and the other way around, that is, by fixing the complexity measure and varying the grammar type. In both of these cases, we develop an almost complete picture, which gives new and interesting insights into the old topic of grammatical production complexity.

We investigate the grammatical complexity of finite languages w.r.t. context-free grammars and variants thereof. For fixed alphabets, it is shown that both the minimal number of productions and the minimal size of a context-free grammar generating a finite language cannot be approximated within a factor of \(o(p^{1/6})\) and \(o(s^{1/7})\), respectively, unless Open image in new window . Here, p is the number of productions and s the size of the given grammar. Similar inapproximability results also hold for linear context-free and right-linear (or regular) grammars. As a byproduct, we show that the language of all cubes of a given length requires an exponential number of context-free productions and we also investigate upper and lower bounds on the complexity of the operations union and concatenation for finite languages.

Spiking neural P systems with astrocytes (SNPA systems, for short) are a class of distributed parallel computing devices inspired from the way spikes pass along the synapses between neurons. In this work, we investigate the computational power of SNPA systems as language generators. Specifically, representations of recursively enumerable languages and of regular languages are given by means of SNPA systems without forgetting rules. Furthermore, a simple finite language is produced which can be generated by SNPA systems, while it cannot be generated by usual spiking neural P systems. These results show that the astrocytes are a powerful ingredient for spiking neural P systems as language generators.

The forbidding and enforcing paradigm was introduced by Ehrenfeucht and Rozenberg as a way to define families of languages based on two sets of boundary conditions. Later, a variant of this paradigm was considered where an fe-system defines a single language. We investigate this variant further by studying fe-systems in which both the forbidding and enforcing sets are finite and show that they define regular languages. We prove that the class of languages defined by finite fe-systems is strictly between the strictly locally testable languages and the class of locally testable languages.

One of the important classes of varieties identified in tame congruence theory is the class of varieties which are n-permutable for some n .I n this paper, we prove two results: (1) for every n> 1, there is a polynomial-time algorithm that, given a finite idempotent algebra A in a finite language, determines whether the variety generated by A is n-permutable and (2) a variety is npermutable for some n if and only if it interprets an idempotent variety that is not interpretable in the variety of distributive lattices.

International audience; The Maximum Asymmetric Travelling Salesman Problem (Max-ATSP), which asks for a Hamiltonian path of maximum weight covering a digraph, and the Maximum Compression(Max-Comp), which, for a finite language P≔{s_1,…,s_p}, asks for w, a superstring of P minimising ∑s_i ∈S |s_i|−|w|, are both difficult to approximate (Max-SNP hard). Solving Max-ATSP on the overlap graph of the words of P solves Max-Comp. Many approximate algorithms have been designed to improve their approximation ratios, but these are increasingly complex. Often, these rely on solving the pendant problems where the cover is made of cycles instead of single path (Max-CC and SCCS). Thus, the greedy algorithm remains an attractive solution for its simplicity and ease of implementation. Here, using the full power of subset systems, we provide a unified approach for proving simply the approximation ratios of a greedy algorithm for these four problems. In addition, we introduce two new problems dealing with the case of cyclic input words, and exhibit a greedy approximation ratio for them. The Maximum Partitioned Hamiltonian Path generalises the Maximum Asymmetric Travelling Salesman Problem when the nodes are partitioned into classes and the path must contain one element of each class. The Maximum Cyclic Compression is the natural counterpart of Maximum Compression for cyclic strings.

Motivated by work on bio-operations on DNA strings, we consider an outfix-guided insertion operation that can be viewed as a generalization of the overlap assembly operation on strings studied previously. As the main result we construct a finite language L such that the outfix-guided insertion closure of L is nonregular. We consider also the closure properties of regular and deterministic context-free languages under the outfix-guided insertion operation and decision problems related to outfix-guided insertion. Deciding whether a language recognized by a deterministic finite automaton is closed under outfix-guided insertion can be done in polynomial time.

We present a structural representation of the Herbrand content of LK-proofs with cuts of complexity prenex Sigma-2/Pi-2. The representation takes the form of a typed non-deterministic tree grammar of order 2 which generates a finite language of first-order terms that appear in the Herbrand expansions obtained through cut-elimination. In particular, for every Gentzen-style reduction between LK-proofs we study the induced grammars and classify the cases in which language equality and inclusion hold., Comment: In Proceedings CL&C 2016, arXiv:1606.05820

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.

We describe strongly minimal theories T n with finite languages such that in the chain of countable models of T n , only the first n models have recursive presentations. Also, we describe a strongly minimal theory with a finite language such that every non-saturated model has a recursive presentation.

In human-machine systems, a user gets abstracted information of a machine via an interface and operates it referring to a manual. If a manual has an erroneous description leading to automation surprises, the user may be lost in his/her operations so that he/she may make a serious human error. In this paper, we propose an algorithm for generating a manual by which automation surprises never occur. We model the machine and the interface as a discrete event system and a mapping from machine's state to a display of the interface, respectively. First, we represent a manual as a finite language and model behavior of the system operated by the user with the manual as a tree called an operational tree. Next, we characterize three automation surprises using the tree. Finally, we propose an algorithm for generating an operational tree by which the machine reaches a target state.

We compare the number of states between minimal deterministic finite automata accepting a regular language and its reversal (mirror image). In the worst case the state complexity of the reversal is 2n for an n-state language. We present several classes of languages where this maximal blow-up is actually achieved and study the conditions for it. In the case of finite languages the maximal blow-up is not possible but still a surprising variety of different growth types can be exhibited.

Using techniques pioneered by R. McKenzie, we prove that there is no algorithm which, given a finite algebra in a finite language, determines whether the variety (equational class) generated by the algebra has a model companion. In particular, there exists a finite algebra such that the variety it generates has no model companion; this answers a question of Burris and Werner from 1979.

Finite Deterministic Cover Automata (DFCA) can be obtained from Deterministic Finite Automata (DFA) using the similarity relation and a method of merging similar states. The DFCA minimization procedure can yield different results depending on the order of merging the similar states, because the minimal DFCA for a finite language is in general not unique. We count the number of minimal DFCA that can be obtained from a given minimal DFA with n states by merging the similar states in the given DFA. We compute an upper-bound for this number and prove that in the worst case, it is n-1 for an unary alphabet, and $\frac{\lceil\frac{4n-9+\sqrt{8n+1}}{8}\rceil !}{(2\lceil \frac{4n-9+\sqrt{8n+1}}{8}\rceil -n+1)!}$ for a non-unary alphabet. We prove that this upper-bound is reached, i.e., for any given positive integer n one can construct a minimal DFA with n states, which has the number of minimal DFCA obtained by merging similar states equal to this maximum expression.

I present two measures of information for both consistent and inconsistent sets of sentences in a finite language of propositional logic. The measures of information are based on measures of inconsistency developed in Knight (2002). Relative information measures are then provided corresponding to the two information measures.

International audience; We define the locally maximal subwords and locally min- imal superwords common to a finite set of words. We also define the corresponding sets of alignments. We give a partial order relation between such sets of alignments, as well as two operations between them. We show that the constructed family of sets of alignments has the lattice structure. The study of analogical proportion in lattices gives hints to use this structure as a machine learning basis, aiming at inducing a generalization of the set of words.

We construct a finitely based congruence-distributive variety of algebras in a finite language whose set of subalgebras of finite simple algebras is non-recursive.

We derive a Mal'cev condition for congruence meet-semidistributivity and then use it to prove two theorems. Theorem A: if a variety in a finite language is congruence meet-semidistributive and residually less than some finite cardinal, then it is finitely based. Theorem B: there is an algorithm which, given m < ω and a finite algebra in a finite language, determines whether the variety generated by the algebra is congruence meet-semidistributive and residually less than m.

The notion of the rational closure of a positive knowledge base K of conditional assertions t_i |∼ p_i (standing for if t_i then normally p_i) was first introduced by Lehmann (1989) and developed by Lehmann and Magidor (1992). Following those authors we would also argue that the rational closure is, in a strong sense, the minimal information, or simplest, rational consequence relation satisfying K. In practice, however, one might expect a knowledge base to consist not just of positive conditional assertions, t_i |∼ p_i, but also negative conditional assertions, t_ _i |∼ p_i (standing for lif t_i then normally p_ir). Restricting ourselves to a finite language we show that the rational closure still exists for satisfiable knowledge bases containing both positive and negative conditional assertions and has similar properties to those exhibited in Lehmann and Magidor (1992). In particular an algorithm in Lehmann and Magidor (1992) which constructs the rational closure can be adapted to this case and yields, in turn, completeness theorems for the conditional assertions entailed by such a mixed knowledge base.

Earlier work concerning control of discrete event systems usually assumed that a correct model of the system to be controlled was available. A goal of this work is to provide an algorithm for determining the correct model from a set of models. The result of the algorithm is a finite language that can be used to test for the correct model or notification that the remaining models cannot be controllably distinguished. We use the finite state machine model with controllable and uncontrollable events presented by Ramadge and Wonham.

The first-order theory of the automorphism group of an infinite resplendent model in a finite language is undecidable.

In pattern matching problems, determining exact or approximative longest common subsequences of two languages appears in many practical problems. Applying weighted finite automata, as a modification of Mohri’s method (2003) in determining Levenstein edit distance of two languages, in this article, we propose an effective method which allows us to compute the longest common subsequences of two finite languages accepted by two finite automata A 1 and A 2 with the time complexity O(|A 1||A 2|), in that, |A i | is the number of states and edges of automata A i , i = 1,2.

Eco-colonies are grammar systems with very simple grammars called agents. Every agent generates its own finite language, all agents cooperate in a shared environment which is represented by a string. The environment is developing not only by the actions of the agents, but also as L systems using its developmental rules. In this chapter we deal with eco-colonies working in the weakly parallel derivation mode. We compare the generative power of weakly parallel eco-colonies with colonies and programmed grammars.

We discuss the notions of inexhaustible, weakly inexhaustible, age-inexhaustible and closure-inexhaustible for countable homogenous structures. Then we characterize these properties of homogeneous structures in various ways. We also exhibit several examples which show that the assumption of finite language is necessary for some of the results.

We investigate the problem of decomposing a language into a catenation of nontrivial languages, none of which can be decomposed further. In many cases this leads to the operation of an ordered catenation closure, introduced in this paper. We study properties of this operation, as well as its iterations. Special emphasis is on laid on ordered catenation closures of finite languages. It is also shown that if an infinite language is a code or a length code, then its ordered catenation closure does not possess a finite decomposition of indecomposable factors.

The hairpin completion is a natural operation on formal languages which has been inspired by biochemistry and DNA-computing. In this paper we solve two problems which were posed first in 2008 and 2009, respectively, and still left open: 1.) It is known that the iterated hairpin completion of a regular language is not context-free in general, but it was open whether the iterated hairpin completion of a singleton or finite language is regular or at least context-free. We will show that it can be non-context-free. 2.) A restricted but also very natural variant of the hairpin completion is the bounded hairpin completion. It was unknown whether the iterated bounded hairpin completion of a regular language remains regular. We prove that this is indeed the case.

We define a property for varieties V, the f.r.p. (finite replacement property). If it applies to a finitely based V then V is strongly finitely based in the sense of [14], see Theorem 2. Moreover, we obtain finite axiomatizability results for certain propositional logics associated with V, in its generality comparable to well-known finite base results from equational logic. Theorem 3 states that each variety generated by a 2-element algebra has the f.r.p. Essentially this implies finite axiomatizability of a 2-valued logic in any finite language.