Titlebook: Developments in Language Theory; 20th International C Srečko Brlek,Christophe Reutenauer Conference proceedings 2016 Springer-Verlag Berlin

思想上升

Aperiodic String Transducers,. to copyless ., and (.) from .-bounded to 1-bounded .. We give the complexity of each construction and also prove that they preserve the aperiodicity of transducers. As corollaries, we obtain that . definable string-to-string functions are equivalent to . whose transition monoid is finite and aperiodic, and to aperiodic copyless ..

ACRID

Alternating Demon Space Is Closed Under Complement and Other Simulations for Sublogarithmic Space,nown inclusion, stating that .. . ., i.e., the alternating space is closed under complement. This simulation does not depend on whether .(.) is above . nor on whether the original machine gets into infinite loops, which solves a long-standing open problem.

AUGUR

APEX

我们的面粉

,-Abelian Equivalence and Rationality,nce by rewriting, so-called .-switching. We show that the set of lexicographically least representatives of equivalence classes is a regular language. From this we infer that the sequence of the numbers of equivalence classes is .-rational. We also show that the set of words defining .-abelian singleton classes is regular.

偶像

,Schützenberger Products in a Category,er), ordered monoids (Pin), idempotent semirings (Klíma and Polák), and algebras over a field (Reutenauer). In addition, assuming that . is part of a Stone-type duality, we derive a characterization of the languages recognized by Schützenberger products.

拥挤前

Both Ways Rational Functions,rational relations, while those of the latter define an a priori really different family. We characterize the partial functions that are in the intersection of the two families. We state a conjecture for the intersection for general, nonfunctional, relations.

变形

Degrees of Infinite Words, Polynomials and Atoms,ges are well-understood, very little is known about the power of automata to transform infinite words..We use methods from linear algebra and analysis to show that there is an infinite number of atoms in the transducer degrees, that is, minimal non-trivial degrees.

舰旗

Non-regular Maximal Prefix-Free Subsets of Regular Languages,ntext-free, it has a MPFS which is recursive but not context-sensitive, and it has a MPFS which is not recursively enumerable..We show that no regular language has a MPFS which is recursively enumerable but not recursive. Finally, for any regular language we can decide whether or not it has a context-free non-regular MPFS.

谁在削木头

https://doi.org/10.1007/978-3-662-66651-7new class called bounded-balance MPDAs. These MPDAs allow for infinitely deep nesting/nesting intersection, as long as the nesting depth differences within each scope stay within the balance bound. We compare our contributions to various related MPDAs and ambiguity detection methods.