Semirings and formal power series: Their relevance to formal languages and automata
W Kuich - Handbook of Formal Languages: Volume 1 Word …, 2013 - Springer
The purpose of Chapter 9 is to develop some classical results on formal languages and
automata by an algebraic treatment using semirings, formal power series and matrices. The …
automata by an algebraic treatment using semirings, formal power series and matrices. The …
Division in logspace-uniform NC1
A Chiu, G Davida, B Litow - RAIRO-Theoretical Informatics and …, 2001 - rairo-ita.org
Beame, Cook and Hoover were the first to exhibit a log-depth, polynomial size circuit family
for integer division. However, the family was not logspace-uniform. In this paper we describe …
for integer division. However, the family was not logspace-uniform. In this paper we describe …
Applications of time-bounded Kolmogorov complexity in complexity theory
E Allender - Kolmogorov complexity and computational complexity, 1992 - Springer
This paper presents one method of using time-bounded Kolmogorov complexity as a
measure of the complexity of sets, and outlines a number of applications of this approach to …
measure of the complexity of sets, and outlines a number of applications of this approach to …
Generalized langton's ant: Dynamical behavior and complexity
Langton's ant is a simple discrete dynamical system, with a surprisingly complex behavior.
We study its extension to general pla-nar graphs. First we give some relations between …
We study its extension to general pla-nar graphs. First we give some relations between …
[PDF][PDF] Holonomic functions and their relation to linearly constrained languages
P Massazza - RAIRO-Theoretical Informatics and Applications, 1993 - numdam.org
Holonomic functions and their relation to linearly constrained languages Page 1
INFORMATIQUE THÉORIQUE ET APPLICATIONS P. MASSAZZA Holonomic functions and …
INFORMATIQUE THÉORIQUE ET APPLICATIONS P. MASSAZZA Holonomic functions and …
[PDF][PDF] NC1 division
A Chiu, G Davida, B Litow - Preliminary version, 2000 - Citeseer
1 Parallel complexity of division Page 1 NC1 Division A. Chiu x, G. Davida {, and B. Litow k
November 22, 1999 Abstract It is shown that integer division is in NC1. This fact and known …
November 22, 1999 Abstract It is shown that integer division is in NC1. This fact and known …
Ranking and formal power series
A Bertoni, D Bruschi, M Goldwurm - Theoretical computer science, 1991 - Elsevier
We prove that the ranking problem for unambiguous context-free languages is NC 1-
reducible to the value problem for algebraic formal power series in noncommuting variables …
reducible to the value problem for algebraic formal power series in noncommuting variables …
On the circuit complexity of random generation problems for regular and context-free languages
M Goldwurm, B Palano, M Santini - … February 15–17, 2001 Proceedings 18, 2001 - Springer
We study the circuit complexity of generating at random a word of length n from a given
language under uniform distribution. We prove that, for every language accepted in …
language under uniform distribution. We prove that, for every language accepted in …
[PDF][PDF] On ranking 1-way finitely ambiguous NL languages and-complete census functions
A Bertoni, M Goldwurm - RAIRO-Theoretical Informatics and …, 1993 - numdam.org
We show that the ranking problem for languages accepted by one-way fïnitely ambiguous
nondeterministic log-space bounded Turing machines (l-FANL) belongs to the class DET …
nondeterministic log-space bounded Turing machines (l-FANL) belongs to the class DET …
Computing a context-free grammar-generating series
B Litow - Information and Computation, 2001 - Elsevier
The parallel complexity of computing context-free grammar generating series is investigated.
It is known that this problem is in DIV, but in terms of nσ rather than n, where n is the index of …
It is known that this problem is in DIV, but in terms of nσ rather than n, where n is the index of …