A counterexample to a conjecture of McDanell

A partially singular optimal control trajectory will contain one or more junctions at which nonsingular and singular subarcs are joined. McDanell's conjecture concerns the necessary conditions for optimality at such a junction. The conjecture is divided into two parts, each part distinguished by the relative magnitudes of two parameters. Until now the conjecture has been proved correct for several different classes of problem. However, this paper presents a partially singular optimal control trajectory containing one junction for which one part of the conjecture is untrue. Attempts to construct a similar trajectory in order to disprove the second part of the conjecture have so far been unsuccessful.     

A counterexample to Mustafa-Glovers'' monotonicity conjecture

It is conjectured by Mustafa and Glover (1990) that the norm of the closed-loop transfer function monotonically increases as the specified norm bound y increases, if the so-called central controller is used. In this paper, a simple counterexample is given by reducing the problem to an interpolation problem. A sufficient condition which guarantees the monotonicity of the γ-characteristic is shown.     

A counterexample to a conjecture of Schnorr referring to monotone networks

Schnorr[1] proved a lower bound on the number of additions in monotone computations of rational polynomials. He conjectured a similar lower bound on the number of ∨-gates in monotone networks computing monotone Boolean functions. We disprove this conjecture.     

A note on the expressibility problem for modal logics and star-free regular expressions

The purpose of this note is to (i) raise attention for an interesting type of decision problem for logics, known under different names such as the expressibility problem and the uniform clone membership problem, (ii) disseminate a remarkable and powerful negative result of M.F. Ra?ǎ from the 1980s that seems to have escaped attention of many researchers, and (iii) show, with the help of Ra?ǎ's theorem, that the problem is undecidable for star-free regular expressions.In Section 1 we introduce the expressibility problem, taking Boolean formulas as an example. In Section 2, we present, and improve upon, Ra?ǎ's theorem for transitive modal logics. In Section 3, we derive, as a consequence of Ra?ǎ's theorem, the undecidability of the expressibility problem for star-free regular expressions. Finally, we conclude in Section 4 with some open questions.     

A theoretical limit for safety verification techniques with regular fix-point computations

In computer aided verification, the reachability problem is particularly relevant for safety analyses. Given a regular tree language L, a term t and a relation R, the reachability problem consists in deciding whether there exist a positive integer n and terms t₀,t₁,…,tn such that t₀∈L, tn=t and for every 0?i<n, (ti,ti+1)∈R. In this case, the term t is said to be reachable, otherwise it is said unreachable. This problem is decidable for particular kinds of relations, but it is known to be undecidable in general, even if L is finite. Several approaches to tackle the unreachability problem are based on the computation of an R-closed regular language containing L. In this paper we show a theoretical limit to this kind of approaches for this problem.     

A note on equations for commutative regular languages

In this note we prove that the equations satisfied by one-letter regular languages are exactly those satisfied by commutative regular languages. This answers a problem raised by Arto Salomaa.     

Two-way deterministic automata with two reversals are exponentially more succinct than with one reversal

We prove that limiting the number of reversals from two to one can cause an exponential blow-up in the size of two-way deterministic automaton.     

A shorter proof that palindromes are not a Church-Rosser language, with extensions to almost-confluent and preperfect Thue systems

In 2002, Jurdziński and Lory? settled a long-standing conjecture that palindromes are not a Church-Rosser language. Their proof involved a difficult analysis of computation graphs associated with 2-pushdown-stack automata. We present a shorter and easier proof in terms of 1-tape Turing machines.We also discuss how the proof generalises to almost-confluent Thue systems and the differing powers of Church-Rosser, almost-confluent, and preperfect Thue systems in relation to palindromes.     

A note on partially ordered tree automata

A recent paper by Bouajjani, Muscholl and Touili shows that the class of languages accepted by partially ordered word automata (or equivalently accepted by Σ₂-formulae) is closed under semi-commutation and it suggested the following open question: can we extend this result to tree languages? This problem can be addressed by proving (1) that the class of tree regular languages accepted by Σ₂ formulae is strictly included in the class of languages accepted by partially ordered automata, and (2) that Bouajjani and the others results cannot be extended to tree.     

A string pattern matching extension to pascal and some comparisons with snobol4

This paper presents an extension of Pascal with string pattern matching. Pattern definitions are built using six basic operations: alternation, concatenation, immediate value assignment, intersection, difference and complement. The last three have not been previously implemented and they increase the expressive power beyond context-free languages. The pattern matching actions are augmented with three options: trace, prefix and suffix. Comparisons with a SNOBOL4 implementation are also presented. This experiment demonstrates that Pascal with pattern matching is a useful tool for string processing applications.     

A power-set construction for reducing Büchi automata to non-determinism degree two

Büchi automata are finite automata that accept languages of infinitely long strings, so-called ω-languages. It is well known that, unlike in the finite-string case, deterministic and non-deterministic Büchi automata accept different ω-language classes, i.e., that determination of a non-deterministic Büchi automaton using the classical power-set construction will yield in general a deterministic Büchi automaton which accepts a superset of the ω-language accepted by the given non-deterministic automaton.In this paper, a power-set construction to a given Büchi automaton is presented, which reduces the degree of non-determinism of the automaton to at most two, meaning that to each state and input symbol, there exist at most two distinct successor states. The constructed Büchi automaton of non-determinism degree two and the given Büchi automaton of arbitrary non-determinism degree will accept the same ω-language.     

A note on cooperating distributed grammar systems working in combined modes

We investigate the generative power of cooperating distributed grammar systems with context-free rules working in the full-competence mode in combination with another derivation mode, combined sf-mode, for short. A combined sf-mode as, for example, (sf∧?k) restricts the valid derivations such that both properties have to be satisfied. If erasing rules are allowed, then except for the (sf∧?1)-, (sf∧=1)-, and (sf∧t)-modes, it is shown that the family of recursively enumerable languages is characterized. The former two exceptions characterize the family of linear context-free languages, while the latter mode describes the family of context-free languages.     

A note on a proposed LALR parser for extended context-free grammars

The lemma in “An improved LALR(k) parser generation for regular right part grammars” [Inform. Process. Lett. 47 (1993) 123-129] to test the applicability of the method is shown to be false by means of a counter-example grammar.     

A framework to visualize equivalences between computational models of regular languages

We discuss how to increase and simplify the understanding of the equivalence relations between machine models and/or language representations of formal languages by means of the animation tool SAGEMoLiC. Our new educational tool permits the simulation of the execution of models of computation, as many other animation systems do, but its philosophy goes further than these of the usual systems since it allows for a true visualization of the key notions involved in the formal proofs of these equivalences. In contrast with the proposal of previous systems, our approach to visualize equivalence theorems is not a simple “step by step animation” of specific conversion algorithms between computational models and/or grammatical representations of formal languages, because we make emphasis on the key theoretical notions involved in the formal proofs of these equivalences.     

Partial words and a theorem of Fine and Wilf revisited

A word of length n over a finite alphabet A is a map from {0,…,n−1} into A. A partial word of length n over A is a partial map from {0,…,n−1} into A. In the latter case, elements of {0,…,n−1} without image are called holes (a word is just a partial word without holes). In this paper, we extend a fundamental periodicity result on words due to Fine and Wilf to partial words with two or three holes. This study was initiated by Berstel and Boasson for partial words with one hole. Partial words are motivated by molecular biology.     

A formal approach to object-oriented databases

Object-oriented database systems are the focus of current research and development efforts. Yet, there is no commonly accepted object model, nor is it clear whether such a model can be developed. This paper reports on efforts to develop a formal framework that contains most features found in current object oriented database systems. The framework contains two parts. The first is a structural object model, including concepts such as structured objects, identity, and some form of inheritance. For this model, we explain the distinction between values and (abstract) objects, describe a system as a directed graph, and discuss declarative languages. The second part deals with higher-order concepts, such as classes and functions as data, methods, and inheritance. This part is a sketch, and leaves many issues unresolved. Throughout the paper, the emphasis is on logic-oriented modeling.     

Bounded regular path queries in view-based data integration

In this paper we study the problem of deciding boundedness of (recursive) regular path queries over views in data integration systems, that is, whether a query can be re-expressed without recursion. This problem becomes challenging when the views contain recursion, thereby potentially making recursion in the query unnecessary. We define and solve two related problems of boundedness of regular path queries. One of the problems asks for the existence of a bound, and the other, more restricted one, asks if the query is bounded within a given parameter. For the more restricted version we show it PSPACE complete, and obtain a constructive method for optimizing the queries. For the existential version of boundedness, we show it PTIME reducible to the notorious problem of limitedness in distance automata. This problem has received a lot attention in the formal language community, but only exponential time algorithms are currently known.     

Constants and label-equivalence: A decision procedure for reflexive regular splicing languages

A structural characterization of reflexive splicing languages has been recently given in [P. Bonizzoni, C. De Felice, R. Zizza, The structure of reflexive regular splicing languages via Schützenberger constants, Theoretical Computer Science 334 (2005) 71-98] and [P. Bonizzoni, G. Mauri, Regular splicing languages and subclasses, Theoretical Computer Science 340 (2005) 349-363] showing surprising connections between long standing notions in formal language theory, the syntactic monoid and Schützenberger constant and the splicing operation.In this paper, we provide a procedure to decide whether a regular language is a reflexive splicing language, based on the above-mentioned characterization that is given in terms of a finite set of constants for the language. The procedure relies on the notion of label-equivalence that induces a finite refinement of the syntactic monoid of a regular language L. A finite set of representatives for label-equivalent classes of constant words in L is defined and it is proved that such a finite set provides the splice sites of splicing rules generating language L.