The Infona portal uses cookies, i.e. strings of text saved by a browser on the user's device. The portal can access those files and use them to remember the user's data, such as their chosen settings (screen view, interface language, etc.), or their login data. By using the Infona portal the user accepts automatic saving and using this information for portal operation purposes. More information on the subject can be found in the Privacy Policy and Terms of Service. By closing this window the user confirms that they have read the information on cookie usage, and they accept the privacy policy and the way cookies are used by the portal. You can change the cookie settings in your browser.
We state that the minimal space measurement requirements for the recognition of non-regular languages are: 1) in the case of two-way alternating Turing machines O(logloglogn), 2) in the case of two-way nondeterministic Turing machines O(loglogn), 3) in the case of one-way alternating Turing machines O(loglogn). In the cases 2) and 3) the bound O(loglogn) is tight.
A unified single proof is given which implies theorems in such diverse fields as continuous algebras of algebraic semantics, dynamic algebras of logics of programs and program verification methods for total correctness. The proof concerns ultraproducts and diagonalization.
Non-uniform complexity measures arising in Automata and Formal Language Theory are characterized in terms of well-known uniform complexity classes. The initial index of languages is introduced by means of several computational models. It is shown to be closely related to context-free cost, boolean circuits, straight line programs, and Turing machines with sparse oracles and time or space bounds.
A fast parallel algorithm that computes a vertex colouring with a constant number of colours is presented. The algorithm works for a wide class of graphs, including graphs of fixed degree or of fixed genus. It can be realized simultaneously within uniform Boolean depth O( log2n) and polynomial size. An application of this colouring algorithm yields an O( log2n ) depth computation of...
We prove that the family Rec(ωAω) of regular sets of bi-infinite words is equal to the family of sets recognized by a deterministic Muller automaton. That extends a theorem of Mc Naughton for one sided infinite words to the case of bi-infinite words.
In previous papers [BT 83] [BT 84] [BT 85], it was indicated how a probabilistic parameter, namely the Bernoullian density, could be computed by means of an explicit formula or numerically with a given precision for several structural types of formal Languages L. We present here two general methods for this computing, a deterministic one and a Monte-Carlo method, using the generating function of the...
Permutation graphs are known as a useful class of perfect graphs for which the NP-complete graph problems GRAPH k-COLORABILITY, PARTITION INTO CLIQUES, CLIQUE and INDEPENDENT SET (VERTEX COVER) (terminology from /8/) are solvable in polynomial time (/7/), in fact all four by the same algorithm (see /10/ for a presentation of these results). In this paper we show that FEEDBACK VERTEX SET, MINIMUM...
Al gorithms recognizing solvable path systems are presented and their time complexity is investigated. Among them there is an algorithm with a constant expected behaviour.
It is well known that confluence (which is equivalent to Church-Rosser property) is undecidable for arbitrary term rewriting systems. We prove here decidability of confluence for ground term rewriting systems. To obtain this result, we construct a special class of finite state tree transducers that we code in recognizable tree languages. Our work illustrates how tree language theory is useful in term...
This paper presents some preliminary observations relating in many cases structural definitions of combinatorial structures to statistical properties of their characteristic parameters. The developments are based on two observations: (i) for a large family of classes of combinatorial structures, one can compile structural descriptions into functional equations over counting generating functions;...
The paper deals with the oscilation complexity OSC introduced in [W 79] for context-free languages. It is known that CF $$CF \subseteq OSC\left( {log} \right)$$ OSC(log), but it was an open question whether there exist context-free languages requiring logarithmic oscilation. We exhibit a language L ∈ CF for which a logarithmic lower bound on its oscilation complexity is established. ...
We present depth efficient transformations of arithmetic into boolean circuits. Any arithmetic circuit Cn over the integers can be converted to an O(d(n)·log*n) depth bounded boolean circuit, where d(n) is the depth of Cn. Furthermore, given any arithmetic circuit Cn over the integers with depth d(n) and f(n) bounded fan-in we can construct a boolean circuit simulating Cn within depth O(d(n)·logf(n)·(log*n−log*f(n)))...
The paper presents a general approach to the computation of the expected value of various additive cost measures of a tree belonging to a simply generated family of trees. On the basis of these results, the behaviour of two refined cost measures is analyzed. This leads to surprising invariants which are valid for a tree in an arbitrary simply generated family of trees.
Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.