Nondeterminism versus determinism of finite automata over directed acyclic graphs.
Displaying 481 – 500 of 893
Note on decipherability of three-word codes.
Blanchet-Sadri, F., Howell, T. (2002)
International Journal of Mathematics and Mathematical Sciences
Nowhere continuous solutions to elliptic systems
Oldřich John, Jan Malý, Jana Stará (1988)
Commentationes Mathematicae Universitatis Carolinae
NP-completeness of minimal width unordered tree layout.
Marriott, Kim, Stuckey, Peter J. (2004)
Journal of Graph Algorithms and Applications
NP-completeness of the planar separator problems.
Fukuyama, Junichiro (2006)
Journal of Graph Algorithms and Applications
NP-completeness results for minimum planar spanners.
Brandes, Ulrik, Handke, Dagmar (1998)
Discrete Mathematics and Theoretical Computer Science. DMTCS [electronic only]
NP-hardness results for intersection graphs
Jan Kratochvíl, Jiří Matoušek (1989)
Commentationes Mathematicae Universitatis Carolinae
Numbering action vertices in workflow graphs
Zoltán Ádám Mann (2010)
International Journal of Applied Mathematics and Computer Science
Workflow graphs, consisting of actions, events, and logical switches, are used to model business processes. In order to easily identify the actions within a workflow graph, it is useful to number them in such a way that the numbering reflects the structure of the workflow. However, available tools offer only rudimental numbering schemes. In the paper, a set of natural requirements is defined that a logical numbering should fulfill. It is investigated under what conditions there is an appropriate...
Numerical studies of the asymptotic height distribution in binary search trees.
Knessl, Charles (2003)
Discrete Mathematics and Theoretical Computer Science. DMTCS [electronic only]
On a characteristic property of Arnoux–Rauzy sequences
Jacques Justin, Giuseppe Pirillo (2002)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Here we give a characterization of Arnoux–Rauzy sequences by the way of the lexicographic orderings of their alphabet.
On a characteristic property of ARNOUX–RAUZY sequences
Jacques Justin, Giuseppe Pirillo (2010)
RAIRO - Theoretical Informatics and Applications
Here we give a characterization of Arnoux–Rauzy sequences by the way of the lexicographic orderings of their alphabet.
On a class of Thue-Morse type sequences.
Astudillo, Ricardo (2003)
Journal of Integer Sequences [electronic only]
On a code problem concerning planar acyclic graphs
F. Bossut, B. Warin (1991)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
On a devil’s staircase associated to the joint spectral radii of a family of pairs of matrices
Ian D. Morris, Nikita Sidorov (2013)
Journal of the European Mathematical Society
The joint spectral radius of a finite set of real matrices is defined to be the maximum possible exponential rate of growth of products of matrices drawn from that set. In previous work with K. G. Hare and J. Theys we showed that for a certain one-parameter family of pairs of matrices, this maximum possible rate of growth is attained along Sturmian sequences with a certain characteristic ratio which depends continuously upon the parameter. In this note we answer some open questions from that paper...
On a generalization of perfect -matching
Ľubica Šándorová, Marián Trenkler (1991)
Mathematica Bohemica
The paper is concerned with the existence of non-negative or positive solutions to , where is the vertex-edge incidence matrix of an undirected graph. The paper gives necessary and sufficient conditions for the existence of such a solution.
On a paper by Castelli, Mignosi, Restivo
Jacques Justin (2000)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
On a paper by Castelli, Mignosi, Restivo
Jacques Justin (2010)
RAIRO - Theoretical Informatics and Applications
Fine and Wilf's theorem has recently been extended to words having three periods. Following the method of the authors we extend it to an arbitrary number of periods and deduce from that a characterization of generalized Arnoux-Rauzy sequences or episturmian infinite words.
On abelian repetition threshold
Alexey V. Samsonov, Arseny M. Shur (2012)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
We study the avoidance of Abelian powers of words and consider three reasonable generalizations of the notion of Abelian power to fractional powers. Our main goal is to find an Abelian analogue of the repetition threshold, i.e., a numerical value separating k-avoidable and k-unavoidable Abelian powers for each size k of the alphabet. We prove lower bounds for the Abelian repetition threshold for large alphabets and all definitions of Abelian fractional power. We develop a method estimating the exponential...
On Abelian repetition threshold
Alexey V. Samsonov, Arseny M. Shur (2012)
RAIRO - Theoretical Informatics and Applications
We study the avoidance of Abelian powers of words and consider three reasonable generalizations of the notion of Abelian power to fractional powers. Our main goal is to find an Abelian analogue of the repetition threshold, i.e., a numerical value separating k-avoidable and k-unavoidable Abelian powers for each size k of the alphabet. We prove lower bounds for the Abelian repetition threshold for large alphabets and all definitions of Abelian fractional ...
On abelian versions of critical factorization theorem
Sergey Avgustinovich, Juhani Karhumäki, Svetlana Puzynina (2012)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
In the paper we study abelian versions of the critical factorization theorem. We investigate both similarities and differences between the abelian powers and the usual powers. The results we obtained show that the constraints for abelian powers implying periodicity should be quite strong, but still natural analogies exist.