BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Gareth Davies

Gareth Davies appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Formal Languages and Automata Theorymath.DSmath.GN

Catalog footprint

What is connected

4works
3topics
3close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

4 published item(s)

preprint2014arXiv

Maximally Atomic Languages

The atoms of a regular language are non-empty intersections of complemented and uncomplemented quotients of the language. Tight upper bounds on the number of atoms of a language and on the quotient complexities of atoms are known. We introduce a new class of regular languages, called the maximally atomic languages, consisting of all languages meeting these bounds. We prove the following result: If L is a regular language of quotient complexity n and G is the subgroup of permutations in the transition semigroup T of the minimal DFA of L, then L is maximally atomic if and only if G is transitive on k-subsets of 1,...,n for 0 <= k <= n and T contains a transformation of rank n-1.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Maximal Syntactic Complexity of Regular Languages Implies Maximal Quotient Complexities of Atoms

We relate two measures of complexity of regular languages. The first is syntactic complexity, that is, the cardinality of the syntactic semigroup of the language. That semigroup is isomorphic to the semigroup of transformations of states induced by non-empty words in the minimal deterministic finite automaton accepting the language. If the language has n left quotients (its minimal automaton has n states), then its syntactic complexity is at most n^n and this bound is tight. The second measure consists of the quotient (state) complexities of the atoms of the language, where atoms are non-empty intersections of complemented and uncomplemented quotients. A regular language has at most 2^n atoms and this bound is tight. The maximal quotient complexity of any atom with r complemented quotients is 2^n-1, if r=0 or r=n, and 1+\sum_{k=1}^{r} \sum_{h=k+1}^{k+n-r} \binom{h}{n} \binom{k}{h}, otherwise. We prove that if a language has maximal syntactic complexity, then it has 2^n atoms and each atom has maximal quotient complexity, but the converse is false.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Most Complex Regular Right-Ideal Languages

A right ideal is a language L over an alphabet A that satisfies L = LA*. We show that there exists a stream (sequence) (R_n : n \ge 3) of regular right ideal languages, where R_n has n left quotients and is most complex under the following measures of complexity: the state complexities of the left quotients, the number of atoms (intersections of complemented and uncomplemented left quotients), the state complexities of the atoms, the size of the syntactic semigroup, the state complexities of the operations of reversal, star, and product, and the state complexities of all binary boolean operations. In that sense, this stream of right ideals is a universal witness.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

On the omega-limit sets of tent maps

For a continuous map f on a compact metric space (X,d), a subset D of X is internally chain transitive if for every x and y in D and every delta > 0 there is a sequence of points {x=x_0,x_1, ...,x_n=y} such that d(f(x_i),x_{i+1}) < delta for i=0,1, ...,n-1. It is known that every omega-limit set is internally chain transitive; in earlier work it was shown that for X a shift of finite type, a closed subset D of X is internally chain transitive if and only if D is an omega-limit set for some point in X, and that the same is also true for the tent map with slope equal to 2. In this paper, we prove that for tent maps whose critical point c=1/2 is periodic, every closed, internally chain transitive set is necessarily an omega-limit set. Furthermore, we show that there are at least countably many tent maps with non-recurrent critical point for which there is a closed, internally chain transitive set which is not an omega-limit set. Together, these results lead us to conjecture that for those tent maps with shadowing (or pseudo-orbit tracing), the omega-limit sets are precisely those sets having internal chain transitivity.

0 citations0 reviewsNo code linkedOpen access