« first day (191 days earlier)      last day (3438 days later) » 

Dave Lang
Dave Lang
13:15
@vzn: Sorry, I didn't have time to answer your chat request for question [Generalized sequential machine synthesis subject to language equivalence/inclusion and reachability][1] until now. A pragmatic approach would be to bound the problem, i.e. does there exist a GSM $X$ with at most $n$ states such that ... holds. In this case, I conjecture that this problem is in PSPACE. Still it would be interesting to know if there is an upper bound for $n$ in the sense that if there is no realization of $X$ with at most $n$ states then there is none.
 
4 hours later…
vzn
vzn
16:46
@DaveLang hi no worries about timing. this chat room stays open over longer periods of time. just wanted to write some extended comments.
there seems to be some discrepancy in the statement. std FSM transducers can work with infinite size languages, but not infinite (size) words.
every word in the input/output set is finite size.
as mentioned in the comments this problem I posed awhile back has some superficial similarity
2
Q: Finding self-similar homomorphisms of a FSM transducer

vznConsider a special case of homomorphisms of FSM transducers (or "generalized sequential machines" in [1]). Let $F$ be a transducer accepting a language $L$, and let $h(x)$ be a homomorphism function which maps from $\Sigma \to \Sigma^*$. (Here, $h(x)$ is extended in the standard way to strings, $...

ds.algorithms reference-request automata-theory regular-language dfa
the basic parallel is that the problem is to construct a transducer that fulfills a set of critiera. have been interested in a problem similar to this for a long time.
have long conjectured that maybe there is an algorithm based on enumerating all transducers in some canonical order.
the enumeration would have some kind of branching structure.
ie, a tree of enumerations.
certain branches of the "tree" can be pruned early and not further enumerated/grown/expanded/traversed based on provably not fulfilling the criteria.
wondering, are you a student? what university are you at? is this for post undergraduate research?
if you could provide some more motivation/background on the problem it would be helpful/informative.
anyway, have surveyed the theory somewhat and have not found existing theory that goes in this direction. as you mention, some of these questions are close to, or inside, the undecidable-in-general region.
think that a useful way to study this would be empirically with small (random?) problem instances and an enumeration algorithm.
if the enumeration succeeds in some cases, maybe some more general theory could be built out of insights/observed patterns.
have you seen any related/nearby theory?
I also conjecture there may be some analog or generalization of krohn-rhodes theory/decomposition for transducers.
Krohn–Rhodes theory
In mathematics and computer science, the Krohn–Rhodes theory (or algebraic automata theory) is an approach to the study of finite semigroups and automata that seeks to decompose them in terms of elementary components. These components correspond to finite aperiodic semigroups and finite simple groups that are combined together in a feedback-free manner (called a "wreath product" or "cascade"). Krohn and Rhodes found a general decomposition for finite automata. In doing their research, though, the authors discovered and proved an unexpected major result in finite semigroup theory, revealing...
it might help in constructing particular transducers fulfilling conditions as in our particular problem case(s).
another direction. it seems these problems have some superficial syntactical similarity to eigenvalue/eigenvector-like constructions from linear algebra.
suspect there maybe some analog in this theory (of FSM transducers).
the krohn-rhodes theory is a neat case where a TCS perspective led to major insight/result in the math/semigroup theory. two separate lines of research unified by remarkable bridge theorem(s).
 
1 hour later…
Dave Lang
Dave Lang
18:23
@vzn You are right that FSM transducers are defined over finite words. This is why I changed the question to generalized sequential machines. However, I don't think it is crucial as I suspect that the result will hold both for finite and infinite words as in many other cases (see e.g. fmindia.cmi.ac.in/update2013/presentations/Ashutosh-Trivedi.pdf).
@vzn: It is good to hear that you are also interested in this type of problem. I was not aware of the parallels you mentioned. Recently, I got interested in automata again because of some interesting Microsoft papers such as research.microsoft.com/pubs/151730/paper.pdf
@vzn: I have to think more about your proposals. As base problem I am now considering the following. Given two GSMs A and B does there exist a GSM X such that A o X = B.
@vzn: Regarding related work there are some Buchi automata synthesis papers such as cgi.csc.liv.ac.uk/~sven/atva07b.pdf where the general (unbounded) synthesis problem is undecidable. This may as well hold in this case. I have to review the arguments again.
vzn
vzn
18:43
hi. I have heard that problems relating to transducers with epsilon transitions are harder. there is some discussion of this in hopcroft & ullman, intro to automata, languages, computation theory.
to me there is not much difference from GSMs and transducers afaict/afaik. (hopcroft/ullman refer to GSMs).
acc to the slide 9 of the slideshow:
Alur and Cerny introduced  streaming string transducers (SSTs) to model
and analyze single-pass list processing programs [Alur and Cerny, 2010]
SSTs are not the same as FSM transducers. suggest you be very careful in formulating your problems.
to me, these questions are simpler to study on FSMs 1st (and are basically open questions afaik/ct). SSTs are more recent. much of the theory would likely carry over.
infinite words allowed in SSTs but not F -SMs.
vzn
vzn
19:01
comparison of FSM transducers/GSMs in slides, 15/16
transformation of infinite strings slide 23-
Sage module for FSMs/transducers
also have used this library, useful
AT&T FSM Library
The AT&T FSM Library is a collection of Unix software tools for creating and manipulating finite state machines, specifically weighted finite-state acceptors and transducers. While completely general, the library was designed for and is being used in speech processing applications, such as speech recognition and speech synthesis. It is available under non-commercial (binary only) and commercial licenses from AT&T Labs. The Library consists of three sets of component: * User program level components that are stand-alone programs and read/write data from files or pipes. * A hierarchy o...
it has some transducer-related utilities/algorithms
re the schewe paper. a rare case where they seem to construct transducers fulfilling certain critieria/constraints...?
@DaveLang looks like a good place to start. yes that seems to be similar to a "division" or "quotient"-like problem for GSMs where composition seems to be similar to multiplication in some ways.
have never seen it considered in the literature... similar to what Ive sought...

« first day (191 days earlier)      last day (3438 days later) »