17 results on '"Shallit, Jeffrey"'
Search Results
2. Sums of Palindromes: an Approach via Automata
- Author
-
Rajasekaran, Aayush, Shallit, Jeffrey, and Smith, Tim
- Subjects
FOS: Computer and information sciences ,000 Computer science, knowledge, general works ,Mathematics - Number Theory ,Formal Languages and Automata Theory (cs.FL) ,010102 general mathematics ,Computer Science - Formal Languages and Automata Theory ,02 engineering and technology ,01 natural sciences ,Computer Science ,FOS: Mathematics ,0202 electrical engineering, electronic engineering, information engineering ,Mathematics - Combinatorics ,020201 artificial intelligence & image processing ,Combinatorics (math.CO) ,Number Theory (math.NT) ,0101 mathematics - Abstract
Recently, Cilleruelo, Luca, & Baxter proved, for all bases b >= 5, that every natural number is the sum of at most 3 natural numbers whose base-b representation is a palindrome. However, the cases b = 2, 3, 4 were left unresolved. We prove, using a decision procedure based on automata, that every natural number is the sum of at most 4 natural numbers whose base-2 representation is a palindrome. Here the constant 4 is optimal. We obtain similar results for bases 3 and 4, thus completely resolving the problem. We consider some other variations on this problem, and prove similar results. We argue that heavily case-based proofs are a good signal that a decision procedure may help to automate the proof.
- Published
- 2018
- Full Text
- View/download PDF
3. Rollercoasters and Caterpillars
- Author
-
Biedl, Therese, Biniaz, Ahmad, Cummings, Robert, Lubiw, Anna, Manea, Florin, Nowotka, Dirk, and Shallit, Jeffrey
- Subjects
Computational Geometry (cs.CG) ,FOS: Computer and information sciences ,000 Computer science, knowledge, general works ,Discrete Mathematics (cs.DM) ,Computer Science - Data Structures and Algorithms ,Computer Science ,Computer Science - Computational Geometry ,Data Structures and Algorithms (cs.DS) ,Computer Science - Discrete Mathematics - Abstract
A rollercoaster is a sequence of real numbers for which every maximal contiguous subsequence, that is increasing or decreasing, has length at least three. By translating this sequence to a set of points in the plane, a rollercoaster can be defined as a polygonal path for which every maximal sub-path, with positive- or negative-slope edges, has at least three points. Given a sequence of distinct real numbers, the rollercoaster problem asks for a maximum-length subsequence that is a rollercoaster. It was conjectured that every sequence of $n$ distinct real numbers contains a rollercoaster of length at least $\lceil n/2\rceil$ for $n>7$, while the best known lower bound is $\Omega(n/\log n)$. In this paper we prove this conjecture. Our proof is constructive and implies a linear-time algorithm for computing a rollercoaster of this length. Extending the $O(n\log n)$-time algorithm for computing a longest increasing subsequence, we show how to compute a maximum-length rollercoaster within the same time bound. A maximum-length rollercoaster in a permutation of $\{1,\dots,n\}$ can be computed in $O(n \log \log n)$ time. The search for rollercoasters was motivated by orthogeodesic point-set embedding of caterpillars. A caterpillar is a tree such that deleting the leaves gives a path, called the spine. A top-view caterpillar is one of degree 4 such that the two leaves adjacent to each vertex lie on opposite sides of the spine. As an application of our result on rollercoasters, we are able to find a planar drawing of every $n$-node top-view caterpillar on every set of $\frac{25}{3}n$ points in the plane, such that each edge is an orthogonal path with one bend. This improves the previous best known upper bound on the number of required points, which is $O(n \log n)$. We also show that such a drawing can be obtained in linear time, provided that the points are given in sorted order., Comment: 17 pages
- Published
- 2018
- Full Text
- View/download PDF
4. Lagrange's Theorem for Binary Squares
- Author
-
Madhusudan, Parthasarathy, Nowotka, Dirk, Rajasekaran, Aayush, and Shallit, Jeffrey
- Subjects
FOS: Computer and information sciences ,000 Computer science, knowledge, general works ,Mathematics - Number Theory ,Formal Languages and Automata Theory (cs.FL) ,010201 computation theory & mathematics ,010102 general mathematics ,Computer Science ,FOS: Mathematics ,Computer Science - Formal Languages and Automata Theory ,Number Theory (math.NT) ,0102 computer and information sciences ,0101 mathematics ,01 natural sciences - Abstract
We show how to prove theorems in additive number theory using a decision procedure based on finite automata. Among other things, we obtain the following analogue of Lagrange's theorem: every natural number > 686 is the sum of at most 4 natural numbers whose canonical base-2 representation is a binary square, that is, a string of the form xx for some block of bits x. Here the number 4 is optimal. While we cannot embed this theorem itself in a decidable theory, we show that stronger lemmas that imply that the theorem can be embedded in decidable theories, and show how automated methods can be used to search for these stronger lemmas.
- Published
- 2018
- Full Text
- View/download PDF
5. Fractional coverings, greedy coverings, and rectifier networks
- Author
-
Chistikov, Dmitry, Iván, Szabolcs, Lubiw, Anna, and Shallit, Jeffrey
- Subjects
FOS: Computer and information sciences ,Computer Science - Computational Complexity ,000 Computer science, knowledge, general works ,Formal Languages and Automata Theory (cs.FL) ,Computer Science ,FOS: Mathematics ,Mathematics - Combinatorics ,Computer Science - Formal Languages and Automata Theory ,Combinatorics (math.CO) ,Computational Complexity (cs.CC) ,QA76 - Abstract
A rectifier network is a directed acyclic graph with distinguished sources and sinks; it is said to compute a Boolean matrix $M$ that has a $1$ in the entry $(i,j)$ iff there is a path from the $j$th source to the $i$th sink. The smallest number of edges in a rectifier network computing $M$ is a classic complexity measure on matrices, which has been studied for more than half a century. We explore two well-known techniques that have hitherto found little to no applications in this theory. Both of them build on a basic fact that depth-$2$ rectifier networks are essentially weighted coverings of Boolean matrices with rectangles. We obtain new results by using fractional and greedy coverings (defined in the standard way). First, we show that all fractional coverings of the so-called full triangular matrix have cost at least $n\log n$. This provides (a fortiori) a new proof of the tight lower bound on its depth-$2$ complexity (the exact value has been known since 1965, but previous proofs are based on different arguments). Second, we show that the greedy heuristic is instrumental in tightening the upper bound on the depth-$2$ complexity of the Kneser-Sierpi\'nski (disjointness) matrix. The previous upper bound is $O(n^{1.28})$, and we improve it to $O(n^{1.17})$, while the best known lower bound is $\Omega(n^{1.16})$. Third, using fractional coverings, we obtain a form of direct product theorem that gives a lower bound on unbounded-depth complexity of Kronecker (tensor) products of matrices. In this case, the greedy heuristic shows (by an argument due to Lov\'asz) that our result is only a logarithmic factor away from the "full" direct product theorem. Our second and third results constitute progress on open problem 7.3 and resolve, up to a logarithmic factor, open problem 7.5 from a recent book by Jukna and Sergeev (in Foundations and Trends in Theoretical Computer Science (2013)).
- Published
- 2017
6. Open problems about regular languages, 35 years later
- Author
-
Konstantinidis, Stavros, Moreira, Nelma, Reis, Rogério, Shallit, Jeffrey, Pin, Jean-Éric, Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Stavros Konstantinidis, Nelma Moreira, Rogério Reis, and Jeffrey Shallit
- Subjects
Computer science ,010102 general mathematics ,ACM: F.: Theory of Computation/F.4: MATHEMATICAL LOGIC AND FORMAL LANGUAGES/F.4.3: Formal Languages ,Open problems ,0102 computer and information sciences ,Regular languages ,01 natural sciences ,Linguistics ,ACM: F.: Theory of Computation/F.4: MATHEMATICAL LOGIC AND FORMAL LANGUAGES/F.4.3: Formal Languages/F.4.3.0: Algebraic language theory ,Regular language ,010201 computation theory & mathematics ,Automata theory ,[INFO]Computer Science [cs] ,State (computer science) ,0101 mathematics ,[MATH]Mathematics [math] ,Selection (genetic algorithm) - Abstract
International audience; In 1980, Janusz A. Brzozowski presented a selection of six open problems about regular languages and mentioned two other problems in the conclusion of his article. These problems have been the source of some of the greatest breakthroughs in automata theory over the past 35 years. This survey article summarizes the state of the art on these questions and the hopes for the next 35 years.; En 1980, Janusz A. Brzozowski a présenté une sélection de six problèmes ouverts sur les langues réguliers et mentionné également deux autres problèmes dans la conclusion de son article. Ces problèmes ont été à l'origine de quelques-unes des plus grandes percées dans la théorie des automates cours des dernières 35 années. Cet article de synthèse résume l'état de l'art sur ces questions et les espoirs pour les 35 prochaines années.
- Published
- 2017
7. The Frobenius Problem in a Free Monoid
- Author
-
Kao, Jui-Yi, Shallit, Jeffrey, Xu, Zhi, Weil, Pascal, and Susanne Albers, Pascal Weil
- Subjects
Frobenius problem ,FOS: Computer and information sciences ,000 Computer science, knowledge, general works ,Discrete Mathematics (cs.DM) ,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM] ,Computer Science ,F.4.3 ,FOS: Mathematics ,Mathematics - Combinatorics ,Computer Science::Symbolic Computation ,combinatorics on words ,Combinatorics (math.CO) ,free monoid ,Computer Science - Discrete Mathematics - Abstract
The classical Frobenius problem is to compute the largest number g not representable as a non-negative integer linear combination of non-negative integers x_1, x_2, ..., x_k, where gcd(x_1, x_2, ..., x_k) = 1. In this paper we consider generalizations of the Frobenius problem to the noncommutative setting of a free monoid. Unlike the commutative case, where the bound on g is quadratic, we are able to show exponential or subexponential behavior for an analogue of g, depending on the particular measure chosen., Comment: 19 pages; preliminary announcement
- Published
- 2007
- Full Text
- View/download PDF
8. A generalization of automatic sequences
- Author
-
Shallit, Jeffrey
- Subjects
Theorem Proving ,Scientific Research ,Computer Science ,Automata ,Mathematical Proofs - Published
- 1988
9. Efficient Enumeration of Regular Languages.
- Author
-
Hutchison, David, Kanade, Takeo, Kittler, Josef, Kleinberg, Jon M., Mattern, Friedemann, Mitchell, John C., Naor, Moni, Nierstrasz, Oscar, Pandu Rangan, C., Steffen, Bernhard, Sudan, Madhu, Terzopoulos, Demetri, Tygar, Doug, Vardi, Moshe Y., Weikum, Gerhard, Holub, Jan, Žďárek, Jan, Ackerman, Margareta, and Shallit, Jeffrey
- Abstract
The cross-section enumeration problem is to list all words of length n in a regular language L in lexicographical order. The enumeration problem is to list the first m words in L according to radix order. We present an algorithm for the cross-section enumeration problem that is linear in n. We provide a detailed analysis of the asymptotic running time of our algorithm and that of known algorithms for both enumeration problems. We discuss some shortcomings of the enumeration algorithm found in the Grail computation package. In the practical domain, we modify Mäkinen's enumeration algorithm to get an algorithm that is usually the most efficient in practice. We performed an extensive performance analysis of the new and previously known enumeration and cross-section enumeration algorithms and found when each algorithm is preferable. [ABSTRACT FROM AUTHOR]
- Published
- 2007
- Full Text
- View/download PDF
10. AVOIDING APPROXIMATE SQUARES.
- Author
-
OCHEM, PASCAL, RAMPERSAD, NARAD, and SHALLIT, JEFFREY
- Subjects
MORPHISMS (Mathematics) ,SQUARE ,APPROXIMATE identities (Algebra) ,COMPUTER science ,ALGORITHMS ,ALPHABETS - Abstract
As is well-known, Axel Thue constructed an infinite word over a 3-letter alphabet that contains no squares, that is, no nonempty subwords of the form xx. In this paper we consider a variation on this problem, where we try to avoid approximate squares, that is, subwords of the form xx' where |x| = |x'| and x and x' are "nearly" identical. [ABSTRACT FROM AUTHOR]
- Published
- 2008
- Full Text
- View/download PDF
11. acm forum.
- Author
-
Munakata, Toshinori, Lehman, M. H., and Shallit, Jeffrey
- Subjects
COMPUTER training ,CURRICULUM ,COMPUTER science ,EDUCATIONAL technology - Abstract
Discusses the introduction of the first computer science course in Japan. Comparison of computer science course curricula found in the United States and Japan; Discussion about the overall quality of computer science education in Japan; Plan for the development and application of advanced software methodology, technology, and tools as an integral part of corporate policy of the Japanese government; Introduction of an undergraduate course in Japan leading to a first degree in software engineering.
- Published
- 1981
12. Periods and Borders of Random Words
- Author
-
Holub, Tepán and Shallit, Jeffrey
- Subjects
000 Computer science, knowledge, general works ,010201 computation theory & mathematics ,Computer Science ,0202 electrical engineering, electronic engineering, information engineering ,020206 networking & telecommunications ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,Computer Science::Formal Languages and Automata Theory - Abstract
We investigate the behavior of the periods and border lengths of random words over a fixed alphabet. We show that the asymptotic probability that a random word has a given maximal border length k is a constant, depending only on k and the alphabet size l. We give a recurrence that allows us to determine these constants with any required precision. This also allows us to evaluate the expected period of a random word. For the binary case, the expected period is asymptotically about n-1.641. We also give explicit formulas for the probability that a random word is unbordered or has maximum border length one.
13. On NFAs where all states are final, initial, or both
- Author
-
Kao, Jui-Yi, Rampersad, Narad, and Shallit, Jeffrey
- Subjects
- *
SEQUENTIAL machine theory , *PROGRAMMING languages , *COMPUTATIONAL complexity , *COMPUTER science , *MATHEMATICAL analysis , *MACHINE learning - Abstract
Abstract: We examine questions involving nondeterministic finite automata where all states are final, initial, or both initial and final. First, we prove hardness results for the nonuniversality and inequivalence problems for these NFAs. Next, we characterize the languages accepted. Finally, we discuss some state complexity problems involving such automata. [Copyright &y& Elsevier]
- Published
- 2009
- Full Text
- View/download PDF
14. State complexity of unique rational operations
- Author
-
Rampersad, Narad, Santean, Nicolae, Shallit, Jeffrey, and Ravikumar, Bala
- Subjects
- *
COMPUTATIONAL complexity , *MATHEMATICAL analysis , *LANGUAGE & languages , *METHODOLOGY , *COMPUTER science , *ELECTRONIC data processing - Abstract
Abstract: For each basic language operation we define its “unique” counterpart as being the operation that results in a language whose words can be obtained uniquely through the given operation. These unique operations can arguably be viewed as combined basic operations, placing this work in the popular area of state complexity of combined operations on regular languages. We study the state complexity of unique rational operations and we provide upper bounds and empirical results meant to cast light into this matter. Equally important, we hope to have provided a generic methodology for estimating their state complexity. [Copyright &y& Elsevier]
- Published
- 2009
- Full Text
- View/download PDF
15. Words avoiding repetitions in arithmetic progressions
- Author
-
Kao, Jui-Yi, Rampersad, Narad, Shallit, Jeffrey, and Silva, Manuel
- Subjects
- *
MATHEMATICS , *COMPUTER science , *COMPUTER logic , *SYSTEMS development , *INFORMATION science - Abstract
Abstract: Carpi constructed an infinite word over a 4-letter alphabet that avoids squares in all subsequences indexed by arithmetic progressions of odd difference. We show a connection between Carpi’s construction and the paperfolding words. We extend Carpi’s result by constructing uncountably many words that avoid squares in arithmetic progressions of odd difference. We also construct infinite words avoiding overlaps and infinite words avoiding all sufficiently large squares in arithmetic progressions of odd difference. We use these words to construct labelings of the 2-dimensional integer lattice such that any line through the lattice encounters a squarefree (resp. overlapfree) sequence of labels. [Copyright &y& Elsevier]
- Published
- 2008
- Full Text
- View/download PDF
16. Reviewing the Early Days of Computing [Book Review].
- Author
-
Shallit, Jeffrey
- Subjects
COMPUTER science ,NONFICTION - Abstract
Here, Jeffrey Shallit reviews the book It Began with Babbage: The Genesis of Computer Science by Subrata Dasgupta, assessing its contents, organization, and the audience for which it's suitable. [ABSTRACT FROM AUTHOR]
- Published
- 2014
- Full Text
- View/download PDF
17. Decimations of languages and state complexity
- Author
-
Krieger, Dalia, Miller, Avery, Rampersad, Narad, Ravikumar, Bala, and Shallit, Jeffrey
- Subjects
- *
SIGNAL processing , *LANGUAGE & languages , *FORMAL languages , *COMPUTATIONAL complexity , *ARITHMETIC , *MATHEMATICAL analysis , *COMPUTER science - Abstract
Abstract: Let the words of a language be arranged in increasing radix order: . We consider transformations that extract terms from in an arithmetic progression. For example, two such transformations are and . Lecomte and Rigo observed that if is regular, then so are , , and analogous transformations of . We find good upper and lower bounds on the state complexity of this transformation. We also give an example of a context-free language such that is not context-free. [Copyright &y& Elsevier]
- Published
- 2009
- Full Text
- View/download PDF
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.