Representation and uniformization of algebraic transductions

This paper explores different means of representation for algebraic transductions, i.e., word relations realized by pushdown transducers. The relevance of this work lies more in its point of view rather than any particular result. We are aiming at giving specific techniques for obtaining, or perhaps explaining, decompositions of algebraic (and incidentally, rational) relations, relying solely on their “machine” definition rather than some complex algebraic apparatus. From this point of view, we are hoping to have demystified the heavy formalism employed in the present literature. Some of the novelties of our work are: the use of “stack languages” and “embeddings,” which eliminate the need of arbitrary context-free languages in our characterizations, the study of uniformizations for algebraic transductions and the use of the so-called stack transductions for exposing the anatomy of pushdown transducers.This work was supported by the Natural Science and Engineering Research Council of Canada grants R220259 and OGP0041630.     

Tree-stack automata

We introduce a new model of stack automata, the “tree-stack automata,” extending the linear stack to a tree-stack. A main subject of our investigations is to explore the relationship between tree-stack automata and stack automata. The main result of this paper is that tree-stack have the same recognition power as stack-pushdown automata, another (well-known) extension of stack automata. Therefore we obtain that the class of languages accepted by the one-way (linear) stack automata is a proper subset of the class of languages accepted by the one-way tree-stack automata and that two-way tree-stack automata have the same recognition power as two-way (linear) stack automata. As a special case of tree-stack automata we consider tree-pushdown automata. As opposed to stack automata the tree-pushdown storage does not extend the recognition power of one-way (resp. two-way) pushdown automata.     

Leaf languages and string compression

Tight connections between leaf languages and strings compressed by straight-line programs (SLPs) are established. It is shown that the compressed membership problem for a language L is complete for the leaf language class defined by L via logspace machines. A more difficult variant of the compressed membership problem for L is shown to be complete for the leaf language class defined by L via polynomial time machines. As a corollary, it is shown that there exists a fixed linear visibly pushdown language for which the compressed membership problem is PSPACE-complete. For XML languages, it is shown that the compressed membership problem is coNP-complete.Furthermore it is shown that the embedding problem for SLP-compressed strings is hard for PP (probabilistic polynomial time).     

A neural networks approach to minority game

The minority game (MG) comes from the so-called “El Farol bar” problem by W.B. Arthur. The underlying idea is competition for limited resources and it can be applied to different fields such as: stock markets, alternative roads between two locations and in general problems in which the players in the “minority” win. Players in this game use a window of the global history for making their decisions, we propose a neural networks approach with learning algorithms in order to determine players strategies. We use three different algorithms to generate the sequence of minority decisions and consider the prediction power of a neural network that uses the Hebbian algorithm. The case of sequences randomly generated is also studied. Research supported by Local Project 2004–2006 (EX 40%) Università di Foggia. A. Sfrecola is a researcher financially supported by Dipartimento di Scienze Economiche, Matematiche e Statistiche, Università degli Studi di Foggia, Foggia, Italy.     

Periodic Plus Smooth Image Decomposition

When the Discrete Fourier Transform of an image is computed, the image is implicitly assumed to be periodic. Since there is no reason for opposite borders to be alike, the “periodic” image generally presents strong discontinuities across the frame border. These edge effects cause several artifacts in the Fourier Transform, in particular a well-known “cross” structure made of high energy coefficients along the axes, which can have strong consequences on image processing or image analysis techniques based on the image spectrum (including interpolation, texture analysis, image quality assessment, etc.). In this paper, we show that an image can be decomposed into a sum of a “periodic component” and a “smooth component”, which brings a simple and computationally efficient answer to this problem. We discuss the interest of such a decomposition on several applications.     

Partial Functions in ACL2

We describe a method for introducing “partial functions” into ACL2, that is, functions not defined everywhere. The function “definitions” are actually admitted via the encapsulation principle: the new function symbol is constrained to satisfy the appropriate equation. This is permitted only when a witness function can be exhibited, establishing that the constraint is satisfiable. Of particular interest is the observation that every tail recursive definition can be witnessed in ACL2. We describe a macro that allows the convenient introduction of arbitrary tail recursive functions, and we discuss how such functions can be used to prove theorems about state machine models without reasoning about “clocks” or counting the number of steps until termination. Our macro for introducing “partial functions” also permits a variety of other recursive schemes, and we briefly illustrate some of them. This revised version was published online in August 2006 with corrections to the Cover Date.     

The complexity of computing maximal word functions

Maximal word functions occur in data retrieval applications and have connections with ranking problems, which in turn were first investigated in relation to data compression [21]. By the maximal word function of a languageL ^*, we mean the problem of finding, on inputx, the lexicographically largest word belonging toL that is smaller than or equal tox.In this paper we present a parallel algorithm for computing maximal word functions for languages recognized by one-way nondeterministic auxiliary pushdown automata (and hence for the class of context-free languages).This paper is a continuation of a stream of research focusing on the problem of identifying properties others than membership which are easily computable for certain classes of languages. For a survey, see [24].     

Fuzzy linear regression model based on fuzzy scalar product

The new concept and method of imposing imprecise (fuzzy) input and output data upon the conventional linear regression model is proposed in this paper. We introduce the fuzzy scalar (inner) product to formulate the fuzzy linear regression model. In order to invoke the conventional approach of linear regression analysis for real-valued data, we transact the α-level linear regression models of the fuzzy linear regression model. We construct the membership functions of fuzzy least squares estimators via the form of “Resolution Identity” which is a well-known formula in fuzzy sets theory. In order to obtain the membership value of any given least squares estimate taken from the fuzzy least squares estimator, we transform the original problem into the optimization problems. We also provide two computational procedures to solve the optimization problems.     

Simulation analysis of decision-making policy for on-demand transport systems

In recent years, on-demand transport systems (such as a demand-bus system) are focused as a new transport service in Japan. An on-demand vehicle visits pick-up and delivery points by door-to-door according to the occurrences of requests. This service can be regarded as a cooperative (or competitive) profit problem among transport vehicles. Thus, a decision-making for the problem is an important factor for the profits of vehicles (i.e., drivers). However, it is difficult to find an optimal solution of the problem, because there are some uncertain risks, e.g., the occurrence probability of requests and the selfishness of other rival vehicles. Therefore, this paper proposes a transport policy for on-demand vehicles to control the uncertain risks. First, we classify the profit of vehicles as “assured profit” and “potential profit”. Second, we propose a “profit policy” and “selection policy” based on the classification of the profits. Moreover, the selection policy can be classified into “greed”, “mixed”, “competitive”, and “cooperative”. These selection policies are represented by selection probabilities of the next visit points to cooperate or compete with other vehicles. Finally, we report simulation results and analyze the effectiveness of our proposal policies.     

The complexity of ranking simple languages

Ranking is the problem of computing for an input string its lexicographic index in a given (fixed) language. This paper concerns the complexity of ranking. We show that ranking languages accepted by 1-way unambiguous auxiliary pushdown automata operating in polynomial time is inNC ⁽²⁾. We also prove negative results about ranking for several classes of simple languages.C is rankable in deterministic polynomial time iffP=P ^#P , whereC is any of the following six classes of languages: (1) languages accepted by logtime-bounded nondeterministic Turing machines, (2) languages accepted by (uniform) families of unbounded fan-in circuits of constant depth and polynomial size, (3) languages accepted by 2-way deterministic pushdown automata, (4) languages accepted by multihead deterministic finite automata, (5) languages accepted by 1-way nondeterministic logspace-bounded Turing machines, and (6) finitely ambiguous linear context-free languages.This research was partially supported by the National Science Foundation under Grant DCR-8696097. A preliminary version of this paper was presented at the 3rd Annual Structure in Complexity Theory Conference, Washington, DC, June 1988.     

Expressing uniformity via oracles

We study under what circumstances different uniformity notions for Boolean circuits of logarithmic depth lead to the same complexity class. Our investigations are based on a characterization of uniformity in terms of oracle access to tally sets that is proved in the present paper:A-uniform circuits of logarithmic depth are of the same computational power asDLOGTIME-uniform circuits of logarithmic depth with oracle access to tally sets inA. This characterization does not only apply to classesA such as logarithmic space or polynomial time, but to all in some sense “well-behaved” classes and especially to all standard complexity classes. We present many applications for this characterization, among them upward separations, depth-uniformity tradeoffs, and inclusion-completeness results for tally languages. The first two authors were partially supported by DFG-La 618/1-1 and the third author was supported by DFG-SFB 0342 “KLARA.”     

Lemma and cut strategies for propositional model elimination

This paper describes new “lemma” and “cut” strategies that are efficient to apply in the setting of propositional Model Elimination. Previous strategies for managing lemmas and C-literals in Model Elimination were oriented toward first-order theorem proving. The original “cumulative” strategy remembers lemmas forever, and was found to be too inefficient. The previously reported C-literal and unit-lemma strategies, such as “strong regularity”, forget them unnecessarily soon in the propositional domain. An intermediate strategy, called “quasi-persistent” lemmas, is introduced. Supplementing this strategy, methods for “eager” lemmas and two forms of controlled “cut” provide further efficiencies. The techniques have been incorporated into “Modoc”, which is an implementation of Model Elimination, extended with a new pruning method that is designed to eliminate certain refutation attempts that cannot succeed. Experimental data show that on random 3CNF formulas at the “hard” ratio of 4.27 clauses per variable, Modoc is not as effective as recently reported model-searching methods. However, on more structured formulas from applications, such as circuit-fault detection, it is superior. This revised version was published online in June 2006 with corrections to the Cover Date.     

Measuring nondeterminism in pushdown automata

The amount of nondeterminism that a pushdown automaton requires to recognize an input string can be measured by the minimum number of guesses that it must make to accept the string, where guesses are measured in bits of information. When this quantity is unbounded, the rate at which it grows as the length of the string increases serves as a measure of the pushdown automaton's “rate of consumption” of nondeterminism. We show that this measure is similar to other complexity measures in that it gives rise to an infinite hierarchy of complexity classes of context-free languages differing in the amount of the resource (in this case, nondeterminism) that they require. In addition, we show that there are context-free languages that can only be recognized by a pushdown automaton whose nondeterminism grows linearly, resolving an open problem in the literature. In particular, the set of palindromes is such a language.     

Some formal properties of stratified feature grammars

In this paper, we investigate the formal expressive properties of Stratified Feature Grammar (SFG), a new logic-based linguistic framework motivated by relational grammar and metagraph grammar, as well as by Kasper-Rounds logic. The driving force behind SFG is the generalization of the conceptfeature from an unanalyzable atomic one to a sequence of so-called R-signs. The linguistic interpretation of thesestratified features is that each R-sign in such a sequence denotes a primitive grammatical relation such as subject or direct object in different syntactic “strata”. This generalization permits the specification of a rigorous feature-structure-based formalism for natural-language grammars based on the view that syntax is “multistratal” and “relational”. The introduction of stratified features leads to several other innovations, two of which might have utility in other frameworks. One is the idea of imposing a partial order on features. The other is the concept of(data) justification: essentially, this is a stipulation that for an S-graph to be well-formed with respect to some grammarG it must, in addition to satisfying the rules ofG, have each of its “core” data (each feature occurrence, each node-label occurrence and each instance of so-called structure-sharing) justified in a formally precise manner by some rule of Justification ensures that. Justification ensures that satisfying S-graphs do not have more structure than absolutely necessary and so makes it appealing to a notion of “minimal model” otiose. Justification plays a key role in a number of our proofs. The formal results presented here include the following. First, it is proved that in the unrestricted SFG framework, every type 0 (r.e.) language is generated by some SFG. Then, we restrict the framework to so-calledbounded SFG with two linguistically motivated principles: Lexical Anchoring and Boundedness. Anchoring requires, in essence, that each core datum of an S-graph be justified by aword in its yield. Boundedness insures that S-graph features are short. Although these restrictions together put the class of bounded SFG languages well within the class of recursive languages, we go on to demonstrate that the recognition problem for bounded SFG is NP-hard. Further, we establish that a bounded SFG language need not be semi-linear. On the matter of upper bounds, we show that every bounded SFL can be recognized by a nondeterministic Turing machine inn logn space and polynomial time and that the recognition problem for bounded SFL's is NP-complete.     

Pushdown tree automata

We define topdown pushdown tree automata (PDTA's) which extend the usual string pushdown automata by allowing trees instead of strings in both the input and the stack. We prove that PDTA's recognize the class of context-free tree languages. (Quasi)realtime and deterministic PDTA's accept the classes of Greibach and deterministic tree languages, respectively. Finally, PDTA's are shown to be equivalent to restricted PDTA's, whose stack is linear: this both yields a more operational way of recognizing context-free tree languages and connects them with the class of indexed languages.     

Concept of inductive programming supporting anthropomorphic information technology

A new original approach to the formalization and implementation methods for the problem of inductive programming is described. This approach makes it possible for the first time to describe a wide range of problems within the given formalization based on examples from the implementation of problem-oriented languages to the development of applied systems with the help of these languages. Methods for passing on “procedure knowledge” that are accepted in information technologies and human communication are discussed and the concept of an “anthropomorphic information technology” is formulated. The general scheme for constructing this system based on the given technology is described. The fundamental role played by the mechanism of partial evaluation in providing the efficiency of implementation and maintenance of the extension mode for inductively specified languages is stressed. An example of inductive specification of a simple programming language and discuss the prospects of using the concept proposed is presented.     

Structured large margin machines: sensitive to data distributions

This paper proposes a new large margin classifier—the structured large margin machine (SLMM)—that is sensitive to the structure of the data distribution. The SLMM approach incorporates the merits of “structured” learning models, such as radial basis function networks and Gaussian mixture models, with the advantages of “unstructured” large margin learning schemes, such as support vector machines and maxi-min margin machines. We derive the SLMM model from the concepts of “structured degree” and “homospace”, based on an analysis of existing structured and unstructured learning models. Then, by using Ward’s agglomerative hierarchical clustering on input data (or data mappings in the kernel space) to extract the underlying data structure, we formulate SLMM training as a sequential second order cone programming. Many promising features of the SLMM approach are illustrated, including its accuracy, scalability, extensibility, and noise tolerance. We also demonstrate the theoretical importance of the SLMM model by showing that it generalizes existing approaches, such as SVMs and M⁴s, provides novel insight into learning models, and lays a foundation for conceiving other “structured” classifiers. Editor: Dale Schuurmans. This work was supported by the Hong Kong Research Grant Council under Grants G-T891 and B-Q519.     

Probabilistic asynchronous automata

Asynchronous automata were introduced by W. Zielonka as an algebraic model of distributed systems, showing that the class of trace languages recognizable by automata over free partially commutative monoids coincides with the class of trace languages recognizable by deterministic asynchronous automata. In this paper we extend the notion of asynchronous automata to the probabilistic case. Our main result is a nontrivial generalization to Zielonka's theorem: we prove that the sets of behaviors of probabilistic automata and of probabilistic asynchronous automata coincide in the case of concurrent alphabets with acyclic dependency graphs. This research has been supported by European Projects EBRA Nos. 3148 (DEMON), 3166 (ASMICS), and 6317 (ASMICS2), by MURST 40%, and by the CNR Project “Modelli di Computazione Parallela.”