Search

Your search keyword '"Zantema, H."' showing total 21 results
Start Over Author "Zantema, H." Publication Year Range Last 10 years
21 results on '"Zantema, H."'

2. Complexity of automatic sequences

Author

Zantema, H., Bosma, W., Zantema, H., and Bosma, W.

Abstract

Contains fulltext : 282948.pdf (Publisher’s version ) (Open Access)

Published
2022

3. Passive Automata Learning: DFAs and NFAs

Author

Jansen, N., Stoelinga, M., Bos, P. van den, Zantema, H., Jansen, N., Stoelinga, M., Bos, P. van den, and Zantema, H.

Abstract

Item does not contain fulltext, It is a natural question to find a DFA or NFA for which a given set of words should be accepted and another given set should not be accepted. In this short note we investigate how to find a smallest automaton for both types by means of SMT solving, and compare the results.

Published
2022

5. Complexity of automatic sequences

Author

Zantema, H., Leporati, A., and Leporati, A.

Subjects
Software Science, Article
Abstract

Automatic sequences can be defined by DFAs with output (DFAO) in two natural ways. We propose to consider the minimal size of a corresponding DFAO as the complexity measure of the automatic sequence, for both variants. This paper compares these complexity measures and investigates their properties like the relationships with kernel and morphic sequences. There exist automatic sequences for which the one complexity is exponentially greater than the other one, in both directions. For both complexity measures we investigate the effect of taking basic operations on sequences like removing or adding an element in front, and observe that these operations may increase the complexity by at most a quadratic factor.

Published
2020

6. Complexity of automatic sequences

Author

Leporati, A., Zantema, H., Leporati, A., and Zantema, H.

Abstract

Language and Automata Theory and Applications: 14th International Conference, LATA 2020, Milan, Italy, March 4–6, 2020, Contains fulltext : 216825.pdf (publisher's version ) (Closed access)

Published
2020

7. Finding DFAs with Maximal Shortest Synchronizing Word Length

Author

Zantema, H., Don, H., Drewes, Frank, Martín-Vide, Carlos, Truthe, Bianca, Drewes, F., Martín-Vide, C., Truthe, B., and Formal System Analysis

Subjects
Discrete mathematics, Sequence, Conjecture, Short path length, Synchronizing, Synchronizing word, Computer support, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Combinatorics, 010201 computation theory & mathematics, 0202 electrical engineering, electronic engineering, information engineering, Software Science, 020201 artificial intelligence & image processing, Regular expression, Alphabet, Stochastics, Mathematics
Abstract

It was conjectured by Černý in 1964 that a synchronizing DFA on n states always has a shortest synchronizing word of length at most (n−1) 2 (n−1)2, and he gave a sequence of DFAs for which this bound is reached. In 2006 Trahtman conjectured that apart from Černý’s sequence only 8 DFAs exist attaining the bound. He gave an investigation of all DFAs up to certain size for which the bound is reached, and which do not contain other synchronizing DFAs. Here we extend this analysis in two ways: we drop this latter condition, and we drop limits on alphabet size. For n≤4 n≤4 we do the full analysis yielding 19 new DFAs with smallest synchronizing word length (n−1) 2 (n−1)2, refuting Trahtman’s conjecture. All these new DFAs are extensions of DFAs that were known before. For n≥5 n≥5 we prove that none of the DFAs in Trahtman’s analysis can be extended similarly. In particular, as a main result we prove that the Černý examples C n Cn do not admit non-trivial extensions keeping the same smallest synchronizing word length (n−1) 2 (n−1)2.

Published
2017

9. Finding small counter examples for abstract rewriting properties

Author

Zantema, H. and Zantema, H.

Abstract

Rewriting notions like termination, normal forms and confluence can be described in an abstract way referring to rewriting only as a binary relation. Several theorems on rewriting, like Newman's lemma, can be proved in this abstract setting. For investigating possible generalizations of such theorems, it is fruitful to have counterexamples showing that particular generalizations do not hold. In this paper, we develop a technique to find such counterexamples fully automatically, and we describe our tool Carpa that follows this technique. The basic idea is to fix the number of objects of the abstract rewrite system, and to express the conditions and the negation of the conclusion in a satisfiability (SAT) formula, and then call a current SAT solver. In case the formula turns out to be satisfiable, the resulting satisfying assignment yields a counterexample to the encoded property. We give several examples of finite abstract rewrite systems having remarkable properties that are found in this way fully automatically.

Published
2018

10. Classifying non-periodic sequences by permutation transducers

Author

Zantema, H., Bosma, W., Charlier, É., Leroy, J., Rigo, M., Formal System Analysis, Charlier, É., Leroy, J., Rigo, M., and Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands

Subjects
Hierarchy (mathematics), 010102 general mathematics, Order (ring theory), 02 engineering and technology, 01 natural sciences, Combinatorics, Permutation, Transducer, Simple function, 0202 electrical engineering, electronic engineering, information engineering, Software Science, 020201 artificial intelligence & image processing, 0101 mathematics, Mathematics
Abstract

Transducers order infinite sequences into natural classes, but permutation transducers provide a finer classification, respecting certain changes to finite segments. We investigate this hierarchy for non-periodic sequences over \(\{0,1\}\) in which the groups of 0s and 1s grow according to simple functions like polynomials. In this hierarchy we find infinite strictly ascending chains of sequences, all being equivalent with respect to ordinary transducers.

Published
2017

11. DFAs and PFAs with long shortest synchronizing word length

Author

de Bondt, M., Don, H., Zantema, H., Charlier, E., Leroy, J., Rigo, M., Mathematics, Charlier, É., Leroy, J., Rigo, M., and Formal System Analysis

Subjects
Discrete mathematics, FOS: Computer and information sciences, Sequence, Formal Languages and Automata Theory (cs.FL), Synchronizing, Computer Science - Formal Languages and Automata Theory, Synchronizing word, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Combinatorics, 010201 computation theory & mathematics, 0202 electrical engineering, electronic engineering, information engineering, Software Science, FOS: Mathematics, Mathematics - Combinatorics, 020201 artificial intelligence & image processing, Combinatorics (math.CO), Mathematics, Computer Science::Formal Languages and Automata Theory
Abstract

It was conjectured by \v{C}ern\'y in 1964, that a synchronizing DFA on $n$ states always has a shortest synchronizing word of length at most $(n-1)^2$, and he gave a sequence of DFAs for which this bound is reached. Until now a full analysis of all DFAs reaching this bound was only given for $n \leq 4$, and with bounds on the number of symbols for $n \leq 10$. Here we give the full analysis for $n \leq 6$, without bounds on the number of symbols. For PFAs the bound is much higher. For $n \leq 6$ we do a similar analysis as for DFAs and find the maximal shortest synchronizing word lengths, exceeding $(n-1)^2$ for $n =4,5,6$. For arbitrary n we give a construction of a PFA on three symbols with exponential shortest synchronizing word length, giving significantly better bounds than earlier exponential constructions. We give a transformation of this PFA to a PFA on two symbols keeping exponential shortest synchronizing word length, yielding a better bound than applying a similar known transformation., Comment: 16 pages, 2 figures source code added

Published
2017
Full Text
View/download PDF

13. Classifying Non-periodic Sequences by Permutation Transducers

Author

Charlier, É., Leroy, J., Rigo, M., Zantema, H., Bosma, W., Charlier, É., Leroy, J., Rigo, M., Zantema, H., and Bosma, W.

Abstract

"null", Contains fulltext : 176554.pdf (publisher's version ) (Closed access) Contains fulltext : 176554pre.pdf (preprint version ) (Open Access)

Published
2017

14. Ordering sequences by permutation transducers

Author

Bosma, W., Zantema, H., Bosma, W., and Zantema, H.

Abstract

Contains fulltext : 168713.pdf (preprint version ) (Open Access) Contains fulltext : 168713pub.pdf (publisher's version ) (Closed access)

Published
2017

15. Finding DFAs with Maximal Shortest Synchronizing Word Length

Author

Drewes, F., Martín-Vide, C., Truthe, B., Don, H., Zantema, H., Drewes, F., Martín-Vide, C., Truthe, B., Don, H., and Zantema, H.

Abstract

"null", Contains fulltext : 173189.pdf (preprint version ) (Open Access) Contains fulltext : 173189pub.pdf (publisher's version ) (Closed access)

Published
2017

16. DFAs and PFAs with Long Shortest Synchronizing Word Length

Author

Charlier, É., Leroy, J., Rigo, M., Bondt, M. de, Don, H., Zantema, H., Charlier, É., Leroy, J., Rigo, M., Bondt, M. de, Don, H., and Zantema, H.

Abstract

"null", Contains fulltext : 176563.pdf (publisher's version ) (Closed access) Contains fulltext : 176563pre.pdf (preprint version ) (Open Access)

Published
2017

18. Classifying non-periodic sequences by permutation transducers

Author

Zantema, H. (Hans), Bosma, W. (Wieb), Zantema, H. (Hans), and Bosma, W. (Wieb)

Abstract

Transducers order infinite sequences into natural classes, but permutation transducers provide a finer classification, respecting certain changes to finite segments. We investigate this hierarchy for non-periodic sequences over {0, 1} in which the groups of 0s and 1s grow according to simple functions like polynomials. In this hierarchy we find infinite strictly ascending chains of sequences, all being equivalent with respect to ordinary transducers.

Published
2017
Full Text
View/download PDF

19. Ordering sequences by permutation transducers

Author

Bosma, W. (Wieb), Zantema, H. (Hans), Bosma, W. (Wieb), and Zantema, H. (Hans)

Abstract

To extend a natural concept of equivalence of sequences to two-sided infinite sequences, the notion of permutation transducer is introduced. Requiring the underlying automaton to be deterministic in two directions, it provides the means to rewrite bi-infinite sequences. The first steps in studying the ensuing hierarchy of equivalence classes of bi-infinite sequences are taken, by describing the classes of ultimately periodic two-sided infinite sequences. It is important to make a distinction between unpointed and pointed sequences, that is, whether or not sequences are considered equivalent up to shifts. While one-sided ultimately periodic sequences form a single equivalence class under ordinary transductions, which is shown to split into two under permutation transductions, in the two-sided case there are three unpointed and seven pointed equivalence classes under permutation transduction.

Published
2017
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results